What Computing Is All About

1 What Is Computing All About? 1.- 2 Grammars 11.- 2.1 Strings and Languages.- 2.2 Grammars.- 2.3 The Language Defined by a Grammar.- 2.4 Bibliographic Notes.- 2.5 Exercises.- 3 A Program Notation.- 3.1 Introduction.- 3.2 The Simple Statements.- 3.3 The Conditional Statement.- 3.4 The Iterative Statement.- 3.5 Procedures.- 3.6 Recursion.- 3.7 Bibliographic Notes.- 3.8 Exercises.- 4 Regular Expressions.- 4.1 Right-Linear Grammars.- 4.2 Transition Graphs.- 4.3 Regular Expressions.- 4.4 The Relation Between the Three Formalisms.- 4.5 Equivalence Relations and Finite-State Automata.- 4.6 Bridling Nondeterminism.- 4.7 Bibliographic Notes.- 4.8 Exercises.- 5 Integrated Circuits.- 5.1 Semiconductor Physics.- 5.2 Semiconductor Junctions.- 5.3 MOS Transistors.- 5.4 Combinational Circuits.- 5.5 State-Holding Devices.- 5.6 Sequential Circuits.- 5.7 Variations.- 5.8 Bibliographie Notes.- 5.9 Exercises.- 6 Recursive Descent Parsing.- 6.1 Top-Down Parsing.- 6.2 Recursive Descent Parsing.- 6.3 Limitations.- 6.4 Lexical Analysis.- 6.5 LR(k) Parsing.- 6.6 Bibliographic Notes.- 6.7 Exercises.- 7 The Halting Problem and Formal Proofs.- 7.1 The Halting Problem.- 7.2 Logic and Boolean Expressions.- 7.3 Gödel’s Incompleteness Result.- 7.4 Cantor’s Diagonal Argument.- 7.5 Calculating with Boolean Expressions.- 7.6 Formal and Informal Mathematics.- 7.7 Bibliographic Notes.- 7.8 Exercises.- 8 Some Programming Heuristics.- 8.1 Omit a Conjunct.- 8.2 Replace a Constant by a Variable.- 8.3 Enlarge the Range of a Variable.- 8.4 Reduce the Problem Size.- 8.5 Random Examples.- 8.6 Conclusion.- 8.7 Bibliographic Notes.- 8.8 Exercises.- 9 Efficiency of Programs.- 9.1 A Lower Bound for Searching.- 9.2 Analysis of Nested Loops.- 9.3 The Constant Factor.- 9.4 Conclusion.- 9.5 Bibliographic Notes.- 9.6 Exercises.- 10 Functional Programming.- 10.1 LISP.- 10.2 Well-Founded Definitions.- 10.3 More Examples of LISP Programs.- 10.4 A LISP Interpreter Written in LISP.- 10.5 A LISP Interpreter Written in Pascal.- 10.6 Discussion.- 10.7 Bibliographic Notes.- 10.8 Exercises.- 11 Program Inversion.- 11.1 Inversion of Programs.- 11.2 Reversible Computations.- 11.3 Circuits Built from Reversible Gates.- 11.4 Reversible Gates Built from Billiard Balls.- 11.5 DNA and Turing Machines.- 11.6 Hot-Clock nMOS.- 11.7 Bibliographic Notes.- 11.8 Exercises.- 12 A Collection of Nice Algorithms.- 12.1 Bresenham’s Algorithm.- 12.2 Computing the Transitive Closure.- 12.3 Recording Equivalence Classes.- 12.4 Minimization of Finite Automata.- 12.5 Oil-Spread Algorithms.- 12.6 Figure 6.- 12.7 Huffman’s Algorithm.- 12.8 Bibliographic Notes.- 12.9 Exercises.- 13 Concurrent Programs.- 13.1 Mutual Exclusion.- 13.2 A Subtle Mistake.- 13.3 Communication via Channels.- 13.4 Buffers.- 13.5 Merging Two Streams.- 13.6 Data Structures.- 13.7 Matrix Multiplication.- 13.8 Algorithms that Scale.- 13.9 Bibliographic Notes.- 13.10 Exercises.- 14 Implementation Issues: Compilation.- 14.1 Translating from One Notation to Another.- 14.2 Expressions.- 14.3 Nomenclature.- 14.3.1 Blocks.- 14.3.2 Procedures.- 14.4 Assignment Statement.- 14.5 Parameters.- 14.6 Flow of Control.- 14.7 A Word About Big and Small.- 14.8 Arrays.- 14.9 Side Effects.- 14.10 Peephole Optimization.- 14.11 From Stack Machine to Register Machine.- 14.12 Range Analysis.- 14.13 Concurrency.- 14.14 Assembly.- 14.15 Bibliographic Notes.- 14.16 Exercises.- 15 An Example of a Compiler.- 15.1 The Program Notation Pascal-S.- 15.2 The Stack Machine.- 15.3 The Compiler.- 15.4 Bootstrapping.- 15.5 Bibliographic Notes.- 15.6 Exercises.- 16 The Construction of a Processor.- 16.1 Processor Organization.- 16.2 The ALU.- 16.3 The Controller.- 16.4 Multicomputers.- 16.5 Bibliographic Notes.- 16.6 Exercises.- A Answers to Some of the Exercises.- B Bibliography.