Foundations of Programming

Description

Contents......Page 3 Preface......Page 8 List of Programs......Page 18 Notation......Page 21 Intro......Page 24 Incorrect Program......Page 26 Assignment Instruction......Page 27 Assertions & Instructions......Page 29 Interpretation of Program......Page 34 Recurrent Construction of Iterative Programs......Page 36 Partial Correctness......Page 38 Strengthening the Recurrence Hypothesis......Page 41 Effect of Choice of Recurrence Hypothesis......Page 42 Heap Sort......Page 47 Exercises......Page 49 Recursivity recalled......Page 52 Construction of Recursive Definitions......Page 53 Computation of recursively defined Function......Page 57 Nature of Recursive Definition......Page 59 Properties of recursively defined Function......Page 60 Choice of Recursive Form......Page 64 Transformation of Recursive Definitions......Page 66 Proper Use of Recursion......Page 68 Functional Programming......Page 71 Exercises......Page 74 Direct Algorithms......Page 76 Construction of Algorithms......Page 78 Precedence Relation......Page 80 Transformation into Program......Page 81 Lazy Evaluation......Page 83 Recurrent Algorithm......Page 85 Execution of Recurrent Algorithm......Page 90 Transformation into Iterative Program......Page 92 Use of Recurrence......Page 95 Giving a Meaning to Program......Page 101 Recurrent Form associated with Recursive Scheme......Page 105 Stack......Page 109 Programs without Stacks......Page 114 Program with only 1 Loop......Page 116 Other Simplifications......Page 117 Degenerate Form of Recursive Scheme......Page 120 Special Cases......Page 123 Exercises......Page 128 Example of Direct Transformation......Page 129 Extension......Page 131 Examples......Page 132 Program Synthesis......Page 137 Complex Recursion......Page 140 Happy Numbers......Page 142 Haming Sequence......Page 149 Exercises......Page 151 Intuitive Presentation of the Idea of Action......Page 153 Systems of Regular Actions......Page 155 Interpretation of System of Regular Actions......Page 157 Graph of System of Actions......Page 161 Substitution......Page 162 Transformation from Terminal Recursion to Iteration......Page 164 Structure of System of Regular Actions......Page 168 Identification......Page 174 Exercises......Page 180 Definitions & Notations......Page 182 Simple Absorption & Simple Expansion......Page 184 Double Iteration & Loop Absorption......Page 186 Proper Inversion......Page 190 Local Semantic Transformations......Page 193 Development of more Complex Transformations......Page 198 Application to Problem of Termination......Page 205 Change of Strategy......Page 207 Exercises......Page 216 Generalised Actions......Page 218 Regularisation......Page 223 Example......Page 226 Schemes of Irlik......Page 228 Formal Parameters & Global Variables......Page 233 Known Recursive Scheme......Page 234 Exercises......Page 240 Analytical Programming......Page 243 Old Friend......Page 245 Problem of Permutations......Page 252 Towers of Hanoi......Page 264 General Result......Page 272 Towers of Hanoi 2......Page 274 Remarks on 2 Solutions of the Towers of Hanoi......Page 277 Exercises......Page 280 Biblio......Page 283 Index......Page 285