What Computing Is All About

Cover......Page 1
What Computing Is All About......Page 4
ISBN 0387940219 ISBN 3540940219......Page 5
Preface......Page 6
Contents......Page 10
1 What Is Computing All About?......Page 14
2.1 Strings and Languages......Page 23
2.2 Grammars......Page 24
2.3 The Language Defined by a Grammar......Page 28
2.5 Exercises......Page 31
3.1 Introduction......Page 34
3.2 The Simple Statements......Page 37
3.3 The Conditional Statement......Page 40
3.4 The Iterative Statement......Page 42
3.5 Procedures......Page 47
3.6 Recursion......Page 51
3.8 Exercises......Page 53
4.1 Right-Linear Grammars......Page 63
4.2 Transition Graphs......Page 64
4.3 Regular Expressions......Page 66
4.4 The Relation Between the Three Formalisms......Page 69
4.5 Equivalence Relations and Finite-State Automata......Page 74
4.6 Bridling Nondeterminism......Page 76
4.8 Exercises......Page 80
5 Integrated Circuits......Page 84
5.1 Semiconductor Physics......Page 85
5.2 Semiconductor Junctions......Page 88
5.3 MOS Transistors......Page 92
5.4 Combinational Circuits......Page 95
5.5 State-Holding Devices......Page 99
5.6 Sequential Circuits......Page 102
5.7 Variations......Page 105
5.9 Exercises......Page 107
6.1 Top-Down Parsing......Page 109
6.2 Recursive Descent Parsing......Page 115
6.3 Limitations......Page 121
6.4 Lexical Analysis......Page 124
6.5 LR(k) Parsing......Page 126
6.7 Exercises......Page 127
7.1 The Halting Problem......Page 129
7.2 Logic and Boolean Expressions......Page 132
7.3 Gödel\'s Incompleteness Result......Page 134
7.4 Cantor\'s Diagonal Argument......Page 136
7.5 Calculating with Boolean Expressions......Page 137
7.6 Formal and Informal Mathematics......Page 142
7.7 Bibliographic Notes......Page 144
7.8 Exercises......Page 145
8 Some Programming Heuristics......Page 147
8.1 Omit a Conjunct......Page 148
8.2 Replace a Constant by a Variable......Page 151
8.3 Enlarge the Range of a Variable......Page 161
8.4 Reduce the Problem Size......Page 164
8.5 Random Examples......Page 171
8.6 Conclusion......Page 174
8.7 Bibliographic Notes......Page 175
8.8 Exercises......Page 176
9 Efficiency of Programs......Page 181
9.1 A Lower Bound for Searching......Page 183
9.2 Analysis of Nested Loops......Page 184
9.3 The Constant Factor......Page 186
9.4 Conclusion......Page 188
9.6 Exercises......Page 189
10.1 LISP......Page 191
10.2 Weil-Founded Definitions......Page 196
10.3 More Examples of LISP Programs......Page 198
10.4 A LISP Interpreter Written in LISP......Page 208
10.5 A LISP Interpreter Written in Pascal......Page 211
10.6 Discussion......Page 219
10.8 Exercises......Page 220
11.1 Inversion of Programs......Page 227
11.2 Reversible Computations......Page 241
11.3 Circuits Built from Reversible Gates......Page 244
11.4 Reversible Gates Built from Billiard Balls......Page 246
11.5 DNA and Turing Machines......Page 250
11.6 Hot-Clock nMOS......Page 252
11.7 Bibliographic Notes......Page 256
11.8 Exercises......Page 257
12.1 Bresenham\'s Algorithm......Page 260
12.2 Computing the Transitive Closure......Page 263
12.3 Recording Equivalence Classes......Page 265
12.4 Minimization of Finite Automata......Page 269
12.5 Oil-Spread Algorithms......Page 274
12.6 Figure 6......Page 278
12.7 Huffman\'s Algorithm......Page 279
12.8 Bibliographic Notes......Page 281
12.9 Exercises......Page 282
13.1 Mutual Exclusion......Page 288
13.2 A Subtle Mistake......Page 297
13.3 Communication via Channels......Page 298
13.4 Buffers......Page 301
13.5 Merging Two Streams......Page 303
13.6 Data Structures......Page 304
13.7 Matrix Multiplication......Page 306
13.8 Algorithms that Scale......Page 311
13.10 Exercises......Page 316
14.1 Translating from One Notation to Another......Page 322
14.2 Expressions......Page 324
14.3.1 Blocks......Page 328
14.3.2 Procedures......Page 329
14.5 Parameters......Page 334
14.6 Flow of Control......Page 336
14.7 A Word About Big and Small......Page 339
14.8 Arrays......Page 341
14.9 Side Effects......Page 343
14.10 Peephole Optimization......Page 345
14.11 From Stack Machine to Register Machine......Page 347
14.12 Range Analysis......Page 352
14.13 Concurrency......Page 353
14.14 Assembly......Page 358
14.16 Exercises......Page 360
15.1 The Program Notation Pascal-S......Page 364
15.2 The Stack Machine......Page 365
15.3 The Compiler......Page 368
15.4 Bootstrapping......Page 388
15.6 Exercises......Page 389
16.1 Processor Organization......Page 392
16.2 The ALU......Page 395
16.3 The Controller......Page 399
16.4 Multicomputers......Page 402
16.5 Bibliographic Notes......Page 406
16.6 Exercises......Page 407
A Answers to Some of the Exercises......Page 410
B Bibliography......Page 475
Index......Page 483