The focus of this book is on finite problems and concrete computational models. It covers the traditional topics of formal languages, automata and complexity classes, as well as an introduction to the more modern topics of space-time tradeoffs, memory hierarchies, parallel computation, the VLSI model, and circuit complexity. These topics are integrated throughout the book as illustrated by the early introduction of P-complete and NP-complete problems. Models of Computation provides the first textbook treatment of space-time tradeoffs and memory hierarchies. It gives a comprehensive introduction to computational complexity as well as a brief but modern coverage of circuit complexity. Parallelism is integrated throughout the book.
Sprache
Verlagsort
Verlagsgruppe
Zielgruppe
Für höhere Schule und Studium
Maße
Höhe: 241 mm
Breite: 197 mm
Dicke: 36 mm
Gewicht
ISBN-13
978-0-201-89539-1 (9780201895391)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Klassifikation
John E. Savage is a professor of Computer Science at Brown University. He is a Guggenheim Fellow, a Fellow of the IEEE, ACM, and the AAAS, and a recipient of a Fulbright-Hayes grant. Professor Savage is also the author of The Complexity of Computing (Wiley and Sons, 1976) and a co-author of The Mystical Machine (Addison-Wesley, 1986).
0201895390AB04062001
(NOTE: Each chapter concludes with "Problems" and "Chapter Notes".)I. OVERVIEW OF THE BOOK.
1. The Role of Theory In Computer Science.
A Brief History of Theoretical Computer Science.
Mathematical Preliminaries.
Methods of Proof.
Computational Models.
Computational Complexity.
Parallel Computation.
II. GENERAL COMPUTATIONAL MODELS.
2. Logic Circuits.
Designing Circuits.
Straight-Line Programs and Circuits.
Normal-Form Expansions of Boolean Functions.
Reductions Between Functions.
Specialized Circuits.
Prefix Computations.
Addition.
Subtraction.
Multiplication.
Reciprocal and Division.
Symmetric Functions.
Most Boolean Functions are Complex.
Upper Bounds on Circuit Size.
3. Machines With Memory.
Finite-State Machines.
Simulating FSMs with Shallow Circuits.
Designing Sequential Circuits.
Random-Access Machines.
Random-Access Memory Design.
Computational Inequalities for the RAM.
Turing Machines.
Universality of the Turing Machine.
Turning Machine Circuit Simulations.
Design of a Simple CPU.
Circuits.
4. Finite-State Machines and Pushdown Automata.
Finite-State Machine Models.
Equivalence of DFSMs and NFSMs.
Regular Expressions.
Regular Expressions and FSMs.
The Pumping Lemma for FSMs.
Properties of Regular Languages.
State Minimization.
Pushdown Automata.
Formal Languages.
Regular Language Recognition.
Parsing Context-Free Languages.
CFL Acceptance with Pushdown Automata.
Properties of Context-Free Languages.
5. Computability.
The Standard Turing Machine Model.
Extensions to the Standard Turing Machine Model.
Configuration Graphs.
Phase-Structure Languages and Turing Machines.
Universal Turing Machines.
Encodings of Strings and Turing Machines.
Limits on Language Recognition.
Reducibility and Unsolvability.
Functions Computed by Turing Machines.
6. Algebraic and Combinatorial Circuits.
Straight-Line Programs.
Mathematical Preliminaries.
Matrix Multiplication.
Transitive Closure.
Matrix Inversion.
Solving Linear Systems.
Convolution and the FFT Algorithm.
Merging and Sorting Networks.
7. Parallel Computation.
Parallel Computational Models.
Memoryless Parallel Computers.
Parallel Computers with Memory.
The Performance of Parallel Algorithms.
Multidimensional Meshes.
Hypercube-Based Machines.
Normal Algorithms.
Routing in Networks.
The PRAM Model.
The BSP and LogP Models.
III. COMPUTATIONAL COMPLEXITY.
8. Complexity Classes.
Introduction.
Languages and Problems.
Resource Bounds.
Serial Computational Models.
Classification of Decision Problems.
Complements of Complexity Classes.
Reductions.
Hard and Complete Problems.
P-Complete Problems.
NP-Complete Problems.
The Boundary Between P and NP.
PSPACE-Complete Problems.
The Circuit Model of Computation.
The Parallel Random-Access Machine Model.
Circuit Complexity Classes.
9. Circuit Complexity.
Circuit Models and Measures.
Relationships Among Complexity Measures.
Lower-Bound Methods for General Circuits.
Lower-Bound Methods for Formula Size.
The Power of Negation.
Lower-Bound Methods for Monotone Circuits.
Circuit Depth.
10. Space-Time Tradeoffs.
The Pebble Game.
Space Lower Bounds.
Extreme Tradeoffs.
Grigoriev's Lower-Bound Method.
Applications of Grigoriev's Method.
Worst-Case Tradeoffs for Pebble Games.
Upper Bounds on Space.
Lower Bound on Space for General Graphs.
Branching Programs.
Straight-Line Versus Branching Programs.
The Borodin-Cook Lower-Bound Method.
Properties of "nice" and "ok" Matrices.
Applications of the Borodin-Cook Method.
11. Memory-Hierarchy Tradeoffs.
The Red-Blue Pebble Game.
The Memory-Hierarchy Pebble Game.
I/O Time Relationships.
The Hong-Kung Lower-Bound Method.
Tradeoffs Between Space and I/O Time.
Block I/O in the MHG.
Simulating a Fast Memory in the MHG.
RAM-Based I/O Models.
The Hierarchical Memory Model.
Competitive Memory Management.
12. Vlsi Models of Computation.
The VLSI Challenge.
VLSI Physical Models.
VLSI Computational Models.
VLSI Performance Criteria.
Chip Layout.
Area-Time Tradeoffs.
The Performance of VLSI Algorithms.
Area Bounds. 0201895390T04062001
