What Computing Is All About

✍ Scribed by Jan L.A.van de Snepscheut

• Publisher: Springer
• Year: 1993
• Tongue: English
• Leaves: 494
• Series: Texts and Monographs in Computer Science
• Category: Library

✦ Synopsis

This is a self-contained discussion of fundamental topics in computer science, which includes coverage of program semantics, automata theory, program and circuit design, concurrent programs and compilation. Formal proofs and practical applications are provided throughout the text.

✦ Table of Contents

Preface
......Page 6
Contents......Page 10
1 What Is Computing All About......Page 14
2.1 Strings and Languages......Page 24
2.2 Grammars......Page 25
2.3 The Language Defined by a Grammar......Page 29
2.5 Exercises......Page 32
3.1 Introduction......Page 36
3.2 The Simple Statements......Page 39
3.3 The Conditional Statement......Page 42
3.4 The Iterative Statement......Page 44
3.5 Procedures......Page 49
3.6 Recursion......Page 53
3.8 Exercises......Page 55
4.1 Right-Linear Grammars......Page 66
4.2 Transition Graphs......Page 67
4.3 Regular Expressions......Page 69
4.4 The Relation Between the Three Formalisms......Page 72
4.5 Equivalence Relations and Finite-State Automata......Page 77
4.6 Bridling Nondeterminism......Page 79
4.8 Exercises......Page 83
5 Integrated Circuits......Page 88
5.1 Semiconductor Physics......Page 89
5.2 Semiconductor Junctions......Page 92
5.3 MOS Transistors......Page 96
5.4 Combinational Circuits......Page 99
5.5 State-Holding Devices......Page 103
5.6 Sequential Circuits......Page 106
5.7 Variations......Page 109
5.9 Exercises......Page 111
6.1 Top-Down Parsing......Page 113
6.2 Recursive Descent Parsing......Page 119
6.3 Limitations......Page 125
6.4 Lexical Analysis......Page 128
6.5 LR(k) Parsing......Page 130
6.7 Exercises......Page 131
7.1 The Halting Problem......Page 133
7.2 Logic and Boolean Expressions......Page 136
7.3 Godel's Incompleteness Result......Page 138
7.4 Cantor's Diagonal Argument......Page 140
7.5 Calculating with Boolean Expressions......Page 141
7.6 Formal and Informal Mathematics......Page 146
7.7 Bibliographic Notes......Page 148
7.8 Exercises......Page 149
8 Some Programming Heuristics......Page 151
8.1 Omit a Conjunct......Page 152
8.2 Replace a Constant by a Variable......Page 155
8.3 Enlarge the Range of a Variable......Page 165
8.4 Reduce the Problem Size......Page 168
8.5 Random Examples......Page 175
8.6 Conclusion......Page 178
8.7 Bibliographic Notes......Page 179
8.8 Exercises......Page 180
9 Efficiency of Programs......Page 185
9.1 A Lower Bound for Searching......Page 187
9.2 Analysis of Nested Loops......Page 188
9.3 The Constant Factor......Page 190
9.4 Conclusion......Page 192
9.6 Exercises......Page 193
10.1 LISP......Page 195
10.2 Well-Founded Definitions......Page 200
10.3 More Examples of LISP Programs......Page 202
10.4 A LISP Interpreter Written in LISP......Page 212
10.5 A LISP Interpreter Written in Pascal......Page 215
10.6 Discussion......Page 223
10.8 Exercises......Page 224
11.1 Inversion of Programs......Page 231
11.2 Reversible Computations......Page 245
11.3 Circuits Built from Reversible Gates......Page 248
11.4 Reversible Gates Built from Billiard Balls......Page 250
11.5 DNA and turing Machines......Page 254
11.6 Hot-Clock nMOS......Page 256
11.7 Bibliographic Notes......Page 260
11.8 Exercises......Page 261
12.1 Bresenham's Algorithm......Page 265
12.2 Computing the Transitive Closure......Page 268
12.3 Recording Equivalence Classes......Page 270
12.4 Minimization of Finite Automata......Page 274
12.5 Oil-Spread Algorithms......Page 279
12.6 Figure 6......Page 283
12.7 Huffman's Algorithm......Page 284
12.8 Bibliographic Notes......Page 286
12.9 Exercises......Page 287
13.1 Mutual Exclusion......Page 293
13.2 A Subtle Mistake......Page 302
13.3 Communication via Channels......Page 303
13.4 Buffers......Page 306
13.5 Merging Two Streams......Page 308
13.6 Data Structures......Page 309
13.7 Matrix Multiplication......Page 311
13.8 Algorithms that Scale......Page 316
13.10 Exercises......Page 321
14.1 Translating from One Notation to Another......Page 327
14.2 Expressions......Page 329
14.3.1 Blocks......Page 333
14.3.2 Procedures......Page 334
14.5 Parameters......Page 339
14.6 Flow of Control......Page 341
14.7 A Word About Big and Small......Page 344
14.8 Arrays......Page 346
14.9 Side Effects......Page 348
14.10 Peephole Optimization......Page 350
14.11 From Stack Machine to Register Machine......Page 352
14.12 Range Analysis......Page 357
14.13 Concurrency......Page 358
14.14 Assembly......Page 363
14.16 Exercises......Page 365
15.1 The Program Notation Pascal-S......Page 369
15.2 The Stack Machine......Page 370
15.3 The Compiler......Page 373
15.4 Bootstrapping......Page 393
15.6 Exercises......Page 394
16.1 Processor Organization......Page 397
16.2 The ALU......Page 400
16.3 The Controller......Page 404
16.4 Multicomputers......Page 407
16.5 Bibliographic Notes......Page 411
16.6 Exercises......Page 412
Answers to Some of the Exercises......Page 415
Bibliography......Page 481
Index......Page 489