Jan L. A. van de Snepscheut

What Computing Is All About (eBook, PDF)

• Format: PDF

Produktbeschreibung

This book will be for a first or second year undergraduate course in computer science. Assuming that a student already has had one course in programming, the text introduces various topics of computer science, in a way that shows their application and promotes real interest.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer US
• Seitenzahl: 478
• Erscheinungstermin: 6. Dezember 2012
• Englisch
• ISBN-13: 9781461227106
• Artikelnr.: 44184139

Inhaltsangabe

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.