Description
Algorithms, Graphs, and Computers
Hide search box
(incl. VAT)
Net price: PLN
Purchase form
To cart
Algorithms, Graphs, and Computers
Authors: Richard Bellman, Kenneth L. Cooke Publisher: Elsevier Science Publication date: 1970 Publication language: Angielski Number of pages: 266 Publication formats: EAN: 9780080955728 ISBN: 9780080955728 Category: Mathematical foundations Kolekcja specjalna: Rok matematyki 2019 Publisher's index: S0076-5392(08)X6109-0 Bibliographic note: -
TOC
- Front Cover 2
- Algorithms Graphs and Computers 5
- Copyright Page 6
- Preface 7
- Contents 13
-
Chapter One. COMMUTING AND COMPUTING
19
- 1. Introduction 19
- 2. A Commuting Problem 21
- 3. Enumeration of Paths 22
- 4. Tree Diagrams 24
- 5. Timing and the Shortest Route 28
- 6. An Improved Map 30
- 7. The Array of Times 34
- 8. Arbitrary Starting Point 37
- 9. Minimum Time Functions 39
- Front Cover 2
- Algorithms Graphs and Computers 5
- Copyright Page 6
- Preface 7
- Contents 13
-
Chapter One. COMMUTING AND COMPUTING
19
- 1. Introduction 19
- 2. A Commuting Problem 21
- 3. Enumeration of Paths 22
- 4. Tree Diagrams 24
- 5. Timing and the Shortest Route 28
- 6. An Improved Map 30
- 7. The Array of Times 34
- 8. Arbitrary Starting Point 37
- 9. Minimum Time Functions 39
- 10. The Minimum Function 40
- 11. Equations for the fi 43
- 12. Reduced Tree 45
- 13. General Map 46
- 14. Solving the Equations 48
- 15. Why Not Enumeration Using Computers? 50
- 16. Graphs 51
- 17. The Problem of the Königsberg Bridges 53
- 18. Systems and States 57
- 19. Critical Path Analysis 61
- 20. Summing Up 64
- Bibliography and Comments 65
-
Chapter Two. THE METHOD OF SUCCESSIVE APPROXIMATIONS
67
- 1. Introduction 67
- 2. A Simple Example of Successive Approximations 68
- 3. A Simple Example of the Failure of the Method 71
- 4. Algorithms 72
- 5. Computer Programming 75
- 6. Algorithms for Solving x = f(x) 78
- 7. The Newton–Raphson Method: Square Roots 81
- 8. An Example 84
- 9. Enter the Digital Computer 85
- 11. Flow Charts for the Determination of S a 86
- 10. Stop Rules 86
- 12. What Initial Approximation? 87
- 13. An Approximation Method of Steinhaus 88
- 14. Successive Approximations for a Simple Routing Problem 89
- 15. The Map of Fig. 3 of Chapter One 91
- 16. Determination of Optimal Policy 94
- 17. A Different Initial Policy 95
- 18. Successive Approximations for a General Map 97
- 19. Computer Program 100
- 20. The Connection Matrix and A Second Programming Method 100
- 21. Fictitious Links 103
- 22. Paths With a Given Number of Junctions 104
- 23. A Labelling Algorithm 108
- 24. Working Back From the End 109
- Miscellaneous Exercises 112
- Bibliography and Comment 117
-
Chapter Three. FROM CHICAGO TO THE GRAND CANYON BY CAR AND COMPUTER : Difficulties Associated With Large Maps
119
- 1. Introduction 119
- 2. How to Plan a Vacation 120
- 3. A Particular Initial Approximation 124
- 4. The Peculiarities of Structure 124
- 5. Computer Program 127
- 6. Storage Considerations 128
- 7. Use of Tapes 128
- 8. Storage of Sparse Data 129
- 10. Transformation of Systems 130
- 9. Calculation of the tij 130
- 11. Stratification 132
- 12. Acceleration of Convergence 133
- 13. Design of Electric Power Stations 136
- Miscellaneous Exercises 138
- Bibliography and Comments 139
-
Chapter Four. PROOF OF THE VALIDITY OF THE METHOD
141
- 1. Will the Method Always Work? 141
- 2. Is There at Least One Solution? 143
- 3. How Do We Find the Desired Solution? 143
- 4. Monotonicity 144
- 5. The Upper Solution 145
- 6. The Lower Solution 146
- 8. Uniqueness of Solution 147
- 7. Experimental Proof of Uniqueness 147
- 9. Determination of Optimal Policy 149
- 10. Arbitrary Initial Approximation 150
- 11. Least Time to Move k Steps 151
- 12. Number of Iterations 153
- Miscellaneous Exercises 155
- Bibliography and Comment 159
-
Chapter Five. JUGGLING JUGS
160
- 1. A Classical Puzzle 160
- 2. Precise Formulation 160
- 3. Trial and Error 161
- 4. Tree Diagrams 161
- 5. Some Further Observations 165
- 6. Enumeration by Computer 166
- 7. A Geometrical Representation 167
- 8. Cost Matrix 170
- 9. Connection Matrix 172
- 11. Powers of the Adjacency Matrix 173
- 10. Minimum Cost Functions 173
- 12. Functional Equations 174
- 13. Successive Approximations 175
- 14. The Labelling Algorithm 176
- 15. Avoiding the Cost Matrix 178
- 17. Getting Close 179
- 16. Another Initial Policy 179
- 18. Making the Closest Approach 181
- 19. Calculation of fN(y, z ) 182
- 20. Accessible and Inaccessible States 185
- Miscellaneous Exercises 186
- Bibliography and Comment 191
-
Chapter Six. THE SAWYER GRAPH AND THE BILLIARD BALL COMPUTER
192
- 1. The Sawyer Graph 192
- 2. Analysis of the Sawyer Graph 195
- 3. Connectedness of the Sawyer Graph 198
- 4. The Spine of the Sawyer Graph 199
- 5. The Case When c is a Divisor of b 200
- 6. The General Case 201
- 7. The Case when b and c Have No Common Factor 203
- 8. The Billiard Ball Solution 205
- 9. The Billiard Ball Diagram and Sawyer Graph 206
- 10. Graphical Determination of Shortest Paths 207
- 12. Computer Assistance in Drawing State Graphs 210
- 11. Discussion 210
- Miscellaneous Exercises 211
- Bibliography and Comment 213
-
Chapter Seven. CANNIBALS AND MISSIONARIES
214
- 1. Another Classical Puzzle 214
- 2. Trees and Enumeration 215
- 3. The State Diagram 216
- 4. Existence and Uniqueness 218
- 5. Analytic Methods 222
- 6. Example 224
- Miscellaneous Exercises 227
- Bibliography and Comment 229
-
Chapter Eight. THE 'TRAVELLING SALESMAN' AND OTHER SCHEDULING PROBLEMS
231
- 1. Introduction 231
- 2. A Mathematician's Holiday 232
- 3. A Map and a Matrix 232
- 4. Enumeration 234
- 5. A Simplified Version 234
- 6. Recurrence Relations 235
- 7. Do All the Errands! 236
- 8. Feasibility 237
- 9. How Many Errands Could We Do? 237
- 10. Trading Time for Storage 238
- 11. How to Build a Tennis Court 239
- 12. Sequential Selection 240
- 13. Feasibility 241
- 14. Simplified and More Realistic Assignment Problem 242
- 15. Constraints 243
- 16. Discussion 243
- 18. A Branching Process 244
- 17. 2N 244
- 19. Recurrence Relations 245
- 20. Discussion 246
- Miscellaneous Exercises 246
- Bibliography and Comment 254
- Author lndex 257
- Subject Index 261
- Mathematics in Science and Engineering 265