I have always been fascinated with engineering. From Roman bridges and jumbo jets to steam engines and CD players, it is the privilege of the en­ gineer to combine scientific insights and technical possibilities into useful and elegant products. Engineers get a great deal of satisfaction from the usefulness and beauty of their designs. Some of these designs have a major impact on our daily lives, others enable further scientific insights or shift limits of technology. The successful engineer is familiar with the scientific basis of the field and the technology of the components, and has an eye for the envisioned applications. For example, to build an airplane, one had better understand the physics of motion, the structural properties of alu­ minum, and the size of passengers. And the physics of motion requires a mastery of mathematics, in particular calculus. Computers are a marvel of modern engineering. They come in a wide variety and their range of applications seems endless. One of the charac­ teristics that makes computers different from other engineering products is their programmability. Dishwashers have some limited programming capa­ is not the key part of the device. Their essential part is some bility, but it enclosed space where the dishes are stored and flushed with hot water. Computers are embedded in many different environments, but in their case the programming capability is the essential part. All computers are programmed in more or less the same way.

Inhalt

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.