Models of Computation: Exploring the Power of Computing
Free
Description
Contents
Reviews
Language
English
ISBN
Unknown
Cover Page
Title Page
Preface
Table Of Contents
I Overview of the Book
The Role of Theory in Computer Science
A Brief History of Theoretical Computer Science
Early Years
1950s
1960s
1970s
1980s and 1990s
Mathematical Preliminaries
Sets
Number Systems
Languages and Strings
Relations
Graphs
Matrices
Functions
Rate of Growth of Functions
Methods of Proof
Computational Models
Logic Circuits
Finite-State Machines
Random-Access Machine
Other Models
Formal Languages
Computational Complexity
A Computational Inequality
Tradeoffs in Space, Time, and I/O Operations
Complexity Classes
Circuit Complexity
Parallel Computation
Problems
Chapter Notes
II General Computational Models
Logic Circuits
Designing Circuits
Straight-Line Programs and Circuits
Functions Computed by Circuits
Circuits That Compute Functions
Circuit Complexity Measures
Algebraic Properties of Boolean Functions
Normal-Form Expansions of Boolean Functions
Disjunctive Normal Form
Conjunctive Normal Form
SOPE and POSE Normal Forms
Ring-Sum Expansion
Comparison of Normal Forms
Reductions Between Functions
Specialized Circuits
Logical Operations
Shifting Functions
Encoder
Decoder
Multiplexer
Demultiplexer
Prefix Computations
An Efficient Parallel Prefix Circuit
Addition
Carry-Lookahead Addition
Subtraction
Multiplication
Carry-Save Multiplication
Divide-and-Conquer Multiplication
Fast Multiplication
Very Fast Multiplication
Reductions to Multiplication
Reciprocal and Division
Reductions to the Reciprocal
Symmetric Functions
Most Boolean Functions Are Complex
Upper Bounds on Circuit Size
Problems
Chapter Notes
Machines with Memory
Finite-State Machines
Functions Computed by FSMs
Computational Inequalities for the FSM
Circuits Are Universal for Bounded FSM Computations
Interconnections of Finite-State Machines
Nondeterministic Finite-State Machines
Simulating FSMs with Shallow Circuits*
A Shallow Circuit Simulating Addition
Designing Sequential Circuits
Binary Memory Devices
Random-Access Machines
The RAM Architecture
The Bounded-Memory RAM as FSM
Unbounded-Memory RAM Programs
Universality of the Unbounded-Memory RAM
Random-Access Memory Design
Computational Inequalities for the RAM
Turing Machines
Nondeterministic Turing Machines
Universality of the Turing Machine
Turing Machine Circuit Simulations
A Simple Circuit Simulation of TM Computations
Computational Inequalities for Turing Machines
Reductions from Turing to Circuit Computations
Definitions of P-Complete and NP-Complete Languages
Reductions to P-Complete Languages
Reductions to NP-Complete Languages
An Efficient Circuit Simulation of TM Computations*
Design of a Simple CPU
The Register Set
The Fetch-and-Execute Cycle
The Instruction Set
Assembly-Language Programming
Timing and Control
CPU Circuit Size and Depth
Emulation
Problems
Chapter Notes
Finite-State Machines and Pushdown Automata
Finite-State Machine Models
Equivalence of DFSMs and NFSMs
Regular Expressions
Regular Expressions and FSMs
Recognition of Regular Expressions by FSMs
Regular Expressions Describing FSM Languages
grep---Searching for Strings in Files
The Pumping Lemma for FSMs
Properties of Regular Languages
State Minimization*
Equivalence Relations on Languages and States
The Myhill-Nerode Theorem
A State Minimization Algorithm
Pushdown Automata
Formal Languages
Phrase-Structure Languages
Context-Sensitive Languages
Context-Free Languages
Regular Languages
Regular Language Recognition
Parsing Context-Free Languages
CFL Acceptance with Pushdown Automata*
Properties of Context-Free Languages
CFL Pumping Lemma
CFL Closure Properties
Problems
Chapter Notes
Computability
The Standard Turing Machine Model
Programming the Turing Machine
Extensions to the Standard Turing Machine Model
Multi-Tape Turing Machines
Nondeterministic Turing Machines
Oracle Turing Machines
Representing Restricted Models of Computation
Configuration Graphs
Phrase-Structure Languages and Turing Machines
Universal Turing Machines
Encodings of Strings and Turing Machines
Limits on Language Acceptance
Decidable Languages
A Language That Is Not Recursively Enumerable
Recursively Enumerable but Not Decidable Languages
Reducibility and Unsolvability
Reducibility
Unsolvable Problems
Functions Computed by Turing Machines
Primitive Recursive Functions
Partial Recursive Functions
Partial Recursive Functions are RAM-Computable
Problems
Chapter Notes
Algebraic and Combinatorial Circuits
Straight-Line Programs
Mathematical Preliminaries
Rings and Fields
Matrices
Matrix Multiplication
Strassen's Algorithm
Transitive Closure
Matrix Inversion
Symmetric Positive Definite Matrices
Schur Factorization
Inversion of Triangular Matrices
LDLT Factorization of SPD Matrices
Fast Matrix Inversion*
Solving Linear Systems
Convolution and the FFT Algorithm
Commutative Rings*
The Discrete Fourier Transform
Fast Fourier Transform
Convolution Theorem
Merging and Sorting Networks
Sorting Via Bitonic Merging
Fast Sorting Networks
Problems
Chapter Notes
Parallel Computation
Parallel Computational Models
Memoryless Parallel Computers
Parallel Computers with Memory
Flynn's Taxonomy
The Data-Parallel Model
Networked Computers
The Performance of Parallel Algorithms
Amdahl's Law
Brent's Principle
Multidimensional Meshes
Matrix-Vector Multiplication on a Linear Array
Sorting on Linear Arrays
Matrix Multiplication on a 2D Mesh
Embedding of 1D Arrays in 2D Meshes
Hypercube-Based Machines
Embedding Arrays in Hypercubes
Cube-Connected Cycles
Normal Algorithms
Summing on the Hypercube
Broadcasting on the Hypercube
Shifting on the Hypercube
Shuffle and Unshuffle Permutations on Linear Arrays
Fully Normal Algorithms on Two-Dimensional Arrays
Normal Algorithms on Cube-Connected Cycles
Fast Matrix Multiplication on the Hypercube
Routing in Networks
Local Routing Networks
Global Routing Networks
The PRAM Model
Simulating Trees, Arrays, and Hypercubes on the PRAM
The Power of Concurrency
Simulating the PRAM on a Hypercube Network
Circuits and the CREW PRAM
The BSP and LogP Models
Problems
Chapter Notes
III Computational Complexity
Complexity Classes
Introduction
Languages and Problems
Complements of Languages and Decision Problems
Resource Bounds
Serial Computational Models
The Random-Access Machine
Turing Machine Models
Classification of Decision Problems
Space and Time Hierarchies
Time-Bounded Complexity Classes
Space-Bounded Complexity Classes
Relations Between Time- and Space-Bounded Classes
Space-Bounded Functions
Complements of Complexity Classes
The Complement of NP
Reductions
Hard and Complete Problems
P-Complete Problems
NP-Complete Problems
NP-Complete Satisfiability Problems
Other NP-Complete Problems
The Boundary Between P and NP
PSPACE-Complete Problems
A First PSPACE-Complete Problem
Other PSPACE-Complete Problems
The Circuit Model of Computation
Uniform Families of Circuits
Uniform Circuits Are Equivalent to Turing Machines
The Parallel Random-Access Machine Model
Equivalence of the CREW PRAM and Circuits
The Parallel Computation Thesis
Circuit Complexity Classes
Efficiently Parallelizable Languages
Circuits of Polynomial Size
Problems
Chapter Notes
Circuit Complexity
Circuit Models and Measures
Circuit Models
Complexity Measures
Relationships Among Complexity Measures
Effect of Fan-Out on Circuit Size
Effect of Basis Change on Circuit Size and Depth
Formula Size Versus Circuit Depth
Lower-Bound Methods for General Circuits
Simple Lower Bounds
The Gate-Elimination Method for Circuit Size
Lower-Bound Methods for Formula Size
The Neciporuk Lower Bound
The Krapchenko Lower Bound
The Power of Negation
Lower-Bound Methods for Monotone Circuits
The Path-Elimination Method
The Function Replacement Method
The Approximation Method
Slice Functions
Circuit Depth
Communication Complexity
General Depth and Communication Complexity
Monotone Depth and Communication Complexity
The Monotone Depth of the Clique Function
Bounded-Depth Circuits
Problems
Chapter Notes
Space--Time Tradeoffs
The Pebble Game
The Pebble Game Versus the Branching Program
Playing the Pebble Game
Space Lower Bounds
Extreme Tradeoffs
Grigoriev's Lower-Bound Method
Flow Properties of Functions
The Lower-Bound Method in the Basic Pebble Game
First Matrix Multiplication Bound
Applications of Grigoriev's Method
Convolution
Cyclic Shifting
Integer Multiplication
Matrix Multiplication
Discrete Fourier Transform
Merging Networks
Worst-Case Tradeoffs for Pebble Games*
Upper Bounds on Space*
Lower Bound on Space for General Graphs*
Branching Programs
Branching Programs and Other Models
Straight-Line Versus Branching Programs
Efficient Branching Programs for Cyclic Shift
Efficient Branching Programs for Merging
The Borodin-Cook Lower-Bound Method
Properties of ``nice'' and ``ok'' Matrices*
Applications of the Borodin-Cook Method
Convolution
Integer Multiplication
Matrix-Vector Product
Matrix Multiplication*
Matrix Inversion
Discrete Fourier Transform
Unique Elements
Sorting
Problems
Chapter Notes
Memory-Hierarchy Tradeoffs
The Red-Blue Pebble Game
Playing the Red-Blue Pebble Game
Balanced Computer Systems
The Memory-Hierarchy Pebble Game
Playing the MHG
I/O-Time Relationships
The Hong-Kung Lower-Bound Method
Tradeoffs Between Space and I/O Time
Matrix-Vector Product
Matrix-Matrix Multiplication
The Fast Fourier Transform
Convolution
Block I/O in the MHG
Simulating a Fast Memory in the MHG
RAM-Based I/O Models
The Block-Transfer Model
The Hierarchical Memory Model
Lower Bounds for the HMM
Upper Bounds for the HMM
Competitive Memory Management
Two-Level Memory-Management Algorithms
Problems
Chapter Notes
VLSI Models of Computation
The VSLI Challenge
Chip Fabrication
Design and Layout
VLSI Physical Models
VLSI Computational Models
VLSI Performance Criteria
Chip Layout
The H-Tree Layout
Multi-dimensional Mesh Layouts
Layout of the CCC Network
Area--Time Tradeoffs
Planar Circuit Size
Computational Inequalities
The Planar Separator Theorem
The Performance of VLSI Algorithms
The Performance of VLSI Algorithms on Functions
The Performance of VLSI Algorithms on Predicates
Area Bounds
Problems
Chapter Notes
Bibliography
Index
The book hasn't received reviews yet.
