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. 6Exercises. - 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. 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 ProcessorOrganization. - 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. Language: English