Foundations of Programming

✍ Scribed by Jacques Arsac

• Publisher: Academic
• Year: 1985
• Tongue: English
• Leaves: 287
• Category: Library

✦ Table of Contents

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