Algorithmic Problem Solving - Backhouse, Roland

. .

Auteur(s) : Backhouse, Roland

Editeur : John Wiley & Sons

Langue : Anglais

Parution : 01/10/2011

Format : Moyen, de 350g à 1kg

Nombre de pages : 432

Expédition : 798

Dimensions : 23.5 x 19.1 x 2.3

ISBN : 9780470684535

Résumé :
An entertaining and captivating way to learn the fundamentals of using algorithms to solve problems

The algorithmic approach to solving problems in computer technology is an essential tool. With this unique book, algorithm?expert Roland Backhouse shares his four decades of experience to teach the fundamental principles of using algorithms to solve problems. Using fun and well-known puzzles to gradually introduce different aspects of algorithms in mathematics and computing. Backhouse presents?a readable, entertaining, and energetic book that will motivate and challenge?students to open?their minds to the algorithmic nature of problem solving.

• Provides a novel approach to the mathematics of problem solving focusing on the algorithmic nature of problem solving
• Uses popular and entertaining puzzles to teach you different aspects of using algorithms to solve mathematical and computing challenges
• Features a theory section that supports each of the puzzles presented throughout the book
• Assumes only an elementary understanding of mathematics

...

Biographie:
Roland Backhouse leads the Foundations of Programming research group at the University of Nottingham. He returned to the UK in 1999 after spending 13 years in the Netherlands, 9 of which as professor at Eindhoven University of Technology (the institution that pioneered the style of reasoning and construction of programs that forms the basis for this book)....

Sommaire:

Preface xi

PART I Algorithmic Problem Solving 1

CHAPTER 1 - Introduction 3

1.1 Algorithms 3

1.2 Algorithmic Problem Solving 4

1.3 Overview 5

1.4 Bibliographic Remarks 6

CHAPTER 2 - Invariants 7

2.1 Chocolate Bars 10

2.1.1 The Solution 10

2.1.2 The Mathematical Solution 11

2.2 Empty Boxes 16

2.2.1 Review 19

2.3 The Tumbler Problem 22

2.3.1 Non-deterministic Choice 23

2.4 Tetrominoes 24

2.5 Summary 30

2.6 Bibliographic Remarks 34

CHAPTER 3 - Crossing a River 35

3.1 Problems 36

3.2 Brute Force 37

3.2.1 Goat, Cabbage and Wolf 37

3.2.2 State-Space Explosion 39

3.2.3 Abstraction 41

3.3 Nervous Couples 42

3.3.1 What Is the Problem? 42

3.3.2 Problem Structure 43

3.3.3 Denoting States and Transitions 44

3.3.4 Problem Decomposition 45

3.3.5 A Review 48

3.4 Rule of Sequential Composition 50

3.5 The Bridge Problem 54

3.6 Conditional Statements 63

3.7 Summary 65

3.8 Bibliographic Remarks 65

CHAPTER 4 - Games 67

4.1 Matchstick Games 67

4.2 Winning Strategies 69

4.2.1 Assumptions 69

4.2.2 Labelling Positions 70

4.2.3 Formulating Requirements 72

4.3 Subtraction-Set Games 74

4.4 Sums of Games 78

4.4.1 A Simple Sum Game 79

4.4.2 Maintain Symmetry! 81

4.4.3 More Simple Sums 82

4.4.4 Evaluating Positions 83

4.4.5 Using the Mex Function 87

4.5 Summary 91

4.6 Bibliographic Remarks 92

CHAPTER 5 - Knights and Knaves 95

5.1 Logic Puzzles 95

5.2 Calculational Logic 96

5.2.1 Propositions 96

5.2.2 Knights and Knaves 97

5.2.3 Boolean Equality 98

5.2.4 Hidden Treasures 100

5.2.5 Equals for Equals 101

5.3 Equivalence and Continued Equalities 102

5.3.1 Examples of the Associativity of Equivalence 104

5.3.2 On Natural Language 105

5.4 Negation 106

5.4.1 Contraposition 109

5.4.2 Handshake Problems 112

5.4.3 Inequivalence 113

5.5 Summary 117

5.6 Bibliographic Remarks 117

CHAPTER 6 - Induction 119

6.1 Example Problems 120

6.2 Cutting the Plane 123

6.3 Triominoes 126

6.4 Looking for Patterns 128

6.5 The Need for Proof 129

6.6 From Verification to Construction 130

6.7 Summary 134

6.8 Bibliographic Remarks 134

CHAPTER 7 - Fake-Coin Detection 137

7.1 Problem Formulation 137

7.2 Problem Solution 139

7.2.1 The Basis 139

7.2.2 Induction Step 139

7.2.3 The Marked-Coin Problem 140

7.2.4 The Complete Solution 141

7.3 Summary 146

7.4 Bibliographic Remarks 146

CHAPTER 8 - The Tower of Hanoi 147

8.1 Specification and Solution 147

8.1.1 The End of the World! 147

8.1.2 Iterative Solution 148

8.1.3 Why? 149

8.2 Inductive Solution 149

8.3 The Iterative Solution 153

8.4 Summary 156

8.5 Bibliographic Remarks 156

CHAPTER 9 - Principles of Algorithm Design 157

9.1 Iteration, Invariants and Making Progress 158

9.2 A Simple Sorting Problem 160

9.3 Binary Search 163

9.4 Sam Loyd's Chicken-Chasing Problem 166

9.4.1 Cornering the Prey 170

9.4.2 Catching the Prey 174

9.4.3 Optimality 176

9.5 Projects 177

9.6 Summary 178

9.7 Bibliographic Remarks 180

CHAPTER 10 - The Bridge Problem 183

10.1 Lower and Upper Bounds 183

10.2 Outline Strategy 185

10.3 Regular Sequences 187