ISBN-10:
0201895390
ISBN-13:
9780201895391
Pub. Date:
10/16/1997
Publisher:
Addison-Wesley
Models of Computation: Exploring the Power of Computing / Edition 1

Models of Computation: Exploring the Power of Computing / Edition 1

by John E. Savage

Paperback

Current price is , Original price is $80.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

This item is available online through Marketplace sellers.

Product Details

ISBN-13: 9780201895391
Publisher: Addison-Wesley
Publication date: 10/16/1997
Pages: 600
Product dimensions: 7.75(w) x 9.51(h) x 1.49(d)

Table of Contents

Preface vii
I Overview of the Book 1(32)
1 The Role of Theory in Computer Science
3(30)
1.1 A Brief History of Theoretical Computer Science
4(3)
1.1.1 Early Years
4(1)
1.1.2 1950s
5(1)
1.1.3 1960s
5(1)
1.1.4 1970s
5(1)
1.1.5 1980s and 1990s
6(1)
1.2 Mathematical Preliminaries
7(7)
1.2.1 Sets
7(1)
1.2.2 Number Systems
8(1)
1.2.3 Languages and Strings
9(1)
1.2.4 Relations
9(1)
1.2.5 Graphs
10(1)
1.2.6 Matrices
11(1)
1.2.7 Functions
11(2)
1.2.8 Rate of Growth of Functions
13(1)
1.3 Methods of Proof
14(2)
1.4 Computational Models
16(7)
1.4.1 Logic Circuits
16(2)
1.4.2 Finite-State Machines
18(1)
1.4.3 Random-Access Machine
19(1)
1.4.4 Other Models
20(1)
1.4.5 Formal Languages
21(2)
1.5 Computational Complexity
23(4)
1.5.1 A Computational Inequality
23(1)
1.5.2 Tradeoffs in Space, Time, and I O Operations
24(2)
1.5.3 Complexity Classes
26(1)
1.5.4 Circuit Complexity
27(1)
1.6 Parallel Computation
27(2)
Problems
29(3)
Chapter Notes
32(1)
II General Computational Models 33(292)
2 Logic Circuits
35(56)
2.1 Designing Circuits
36(1)
2.2 Straight-Line Programs and Circuits
36(6)
2.2.1 Functions Computed by Circuits
38(1)
2.2.2 Circuits That Compute Functions
39(1)
2.2.3 Circuit Complexity Measures
40(1)
2.2.4 Algebraic Properties of Boolean Functions
40(2)
2.3 Normal-Form Expansions of Boolean Functions
42(4)
2.3.1 Disjunctive Normal Form
42(1)
2.3.2 Conjunctive Normal Form
43(1)
2.3.3 SOPE and POSE Normal Forms
44(1)
2.3.4 Ring-Sum Expansion
45(1)
2.3.5 Comparison of Normal Forms
45(1)
2.4 Reductions Between Functions
46(1)
2.5 Specialized Circuits
47(8)
2.5.1 Logical Operations
48(1)
2.5.2 Shifting Functions
48(3)
2.5.3 Encoder
51(2)
2.5.4 Decoder
53(1)
2.5.5 Multiplexer
54(1)
2.5.6 Demultiplexer
55(1)
2.6 Prefix Computations
55(3)
2.6.1 An Efficient Parallel Prefix Circuit
57(1)
2.7 Addition
58(3)
2.7.1 Carry-Lookahead Addition
60(1)
2.8 Subtraction
61(1)
2.9 Multiplication
62(6)
2.9.1 Carry-Save Multiplication
64(2)
2.9.2 Divide-and-Conquer Multiplication
66(1)
2.9.3 Fast Multiplication
67(1)
2.9.4 Very Fast Multiplication
67(1)
2.9.5 Reductions to Multiplication
68(1)
2.10 Reciprocal and Division
68(6)
2.10.1 Reductions to the Reciprocal
72(2)
2.11 Symmetric Functions
74(3)
2.12 Most Boolean Functions Are Complex
77(2)
2.13 Upper Bounds on Circuit Size
79(3)
Problems
82(6)
Chapter Notes
88(3)
3 Machines with Memory
91(62)
3.1 Finite-State Machines
92(8)
3.1.1 Functions Computed by FSMs
94(1)
3.1.2 Computational Inequalities for the FSM
95(1)
3.1.3 Circuits Are Universal for Bounded FSM Computations
96(1)
3.1.4 Interconnections of Finite-State Machines
97(1)
3.1.5 Nondeterministic Finite-State Machines
98(2)
3.2 Simulating FSMs with Shallow Circuits(*)
100(6)
3.2.1 A Shallow Circuit Simulating Addition
105(1)
3.3 Designing Sequential Circuits
106(4)
3.3.1 Binary Memory Devices
109(1)
3.4 Random-Access Machines
110(5)
3.4.1 The RAM Architecture
110(1)
3.4.2 The RAM as FSM
111(1)
3.4.3 RAM Programs
112(2)
3.4.4 Universality of the RAM
114(1)
3.5 Random-Access Memory Design
115(2)
3.6 Computational Inequalities for the RAM
117(1)
3.7 Turing Machines
118(3)
3.7.1 Nondeterministic Turing Machines
120(1)
3.8 Universality of the Turing Machine
121(3)
3.9 Turing Machine Circuit Simulations
124(13)
3.9.1 A Simple Circuit Simulation of TM Computations
124(3)
3.9.2 Computational Inequalities for Turing Machines
127(1)
3.9.3 Reductions from Turing to Circuit Computations
128(2)
3.9.4 Definitions of P-Complete and NP-Complete Languages
130(1)
3.9.5 Reductions to P-Complete Languages
130(2)
3.9.6 Reductions to NP-Complete Languages
132(2)
3.9.7 An Efficient Circuit Simulation of TM Computations(*)
134(3)
3.10 Design of a Simple CPU
137(10)
3.10.1 The Register Set
138(1)
3.10.2 The Fetch-and-Execute Cycle
139(1)
3.10.3 The Instruction Set
139(1)
3.10.4 Assembly-Language Programming
140(2)
3.10.5 Timing and Control
142(4)
3.10.6 CPU Circuit Size and Depth
146(1)
3.10.7 Emulation
147(1)
Problems
147(5)
Chapter Notes
152(1)
4 Finite-State Machines and Pushdown Automata
153(56)
4.1 Finite-State Machine Models
154(2)
4.2 Equivalence of DFSMs and NFSMs
156(2)
4.3 Regular Expressions
158(2)
4.4 Regular Expressions and FSMs
160(8)
4.4.1 Recognition of Regular Expressions by FSMs
160(4)
4.4.2 Regular Expressions Describing FSM Languages
164(4)
4.4.3 grep--Searching for Strings in Files
168(1)
4.5 The Pumping Lemma for FSMs
168(2)
4.6 Properties of Regular Languages
170(1)
4.7 State Minimization(*)
171(6)
4.7.1 Equivalence Relations on Languages and States
171(3)
4.7.2 The Myhill-Nerode Theorem
174(1)
4.7.3 A State Minimization Algorithm
175(2)
4.8 Pushdown Automata
177(4)
4.9 Formal Languages
181(3)
4.9.1 Phrase-Structure Languages
182(1)
4.9.2 Context-Sensitive Languages
183(1)
4.9.3 Context-Free Languages
183(1)
4.9.4 Regular Languages
184(1)
4.10 Regular Language Recognition
184(2)
4.11 Parsing Context-Free languages
186(6)
4.12 CFL Acceptance with Pushdown Automata(*)
192(5)
4.13 Properties of Context-Free Languages
197(3)
4.13.1 CFL Pumping Lemma
197(1)
4.13.2 CFL Closure Properties
198(2)
Problems
200(7)
Chapter Notes
207(2)
5 Computability
209(28)
5.1 The Standard Turing Machine Model
210(3)
5.1.1 Programming the Turing Machine
211(2)
5.2 Extensions to the Standard Turing Machine Model
213(5)
5.2.1 Multi-Tape Turing Machines
213(1)
5.2.2 Nondeterministic Turing Machines
214(2)
5.2.3 Oracle Turing Machines
216(1)
5.2.4 Representing Restricted Models of Computation
217(1)
5.3 Configuration Graphs
218(1)
5.4 Phrase-Structure Languages and Turing Machines
219(1)
5.5 Universal Turing Machines
220(2)
5.6 Encodings of Strings and Turing Machines
222(1)
5.7 Limits on Language Acceptance
223(3)
5.7.1 Decidable Languages
223(1)
5.7.2 A Language That Is Not Recursively Enumerable
224(1)
5.7.3 Recursively Enumerable but Not Decidable Languages
225(1)
5.8 Reducibility and Unsolvability
226(4)
5.8.1 Reducibility
226(1)
5.8.2 Unsolvable Problems
227(3)
5.9 Functions Computed by Turing Machines
230(3)
5.9.1 Primitive Recursive Functions
231(1)
5.9.2 Partial Recursive Functions
232(1)
5.9.3 Partial Recursive Functions are RAM-Computable
233(1)
Problems
233(3)
Chapter Notes
236(1)
6 Algebraic and Combinatorial Circuits
237(44)
6.1 Straight-Line Programs
238(1)
6.2 Mathematical Preliminaries
239(5)
6.2.1 Rings
239(1)
6.2.2 Matrices
240(4)
6.3 Matrix Multiplication
244(4)
6.3.1 Strassen's Algorithm
245(3)
6.4 Transitive Closure
248(4)
6.5 Matrix Inversion
252(10)
6.5.1 Symmetric Positive Definite Matrices
253(1)
6.5.2 Schur Factorization
254(1)
6.5.3 Inversion of Triangular Matrices
255(2)
6.5.4 LDL(T) Factorization of SPD Matrices
257(3)
6.5.5 Fast Matrix Inversion(*)
260(2)
6.6 Solving Linear Systems
262(1)
6.7 Convolution and the FFT Algorithm
263(7)
6.7.1 Commutative Rings(*)
264(1)
6.7.2 The Discrete Fourier Transform
264(2)
6.7.3 Fast Fourier Transform
266(2)
6.7.4 Convolution Theorem
268(2)
6.8 Merging and Sorting Networks
270(4)
6.8.1 Sorting Via Odd-Even Merging
271(3)
6.8.2 Fast Sorting Networks
274(1)
Problems
274(4)
Chapter Notes
278(3)
7 Parallel Computation
281(44)
7.1 Parallel Computational Models
282(1)
7.2 Memoryless Parallel Computers
282(1)
7.3 Parallel Computers with Memory
283(6)
7.3.1 Flynn's Taxonomy
285(1)
7.3.2 The Data-Parallel Model
286(1)
7.3.3 Networked Computers
287(2)
7.4 The Performance of Parallel Algorithms
289(3)
7.4.1 Amdahl's Law
290(1)
7.4.2 Brent's Principle
291(1)
7.5 Multidimensional Meshes
292(6)
7.5.1 Matrix-Vector Multiplication on a Linear Array
293(1)
7.5.2 Sorting on Linear Arrays
294(1)
7.5.3 Matrix Multiplication on a 2D Mesh
295(2)
7.5.4 Embedding of 1D Arrays in 2D Meshes
297(1)
7.6 Hypercube-Based Machines
298(3)
7.6.1 Embedding Arrays in Hypercubes
299(1)
7.6.2 Cube-Connected Cycles
300(1)
7.7 Normal Algorithms
301(8)
7.7.1 Summing on the Hypercube
302(1)
7.7.2 Broadcasting on the Hypercube
303(1)
7.7.3 Shifting on the Hypercube
303(1)
7.7.4 Shuffle and Unshuffle Permutations on Linear Arrays
304(2)
7.7.5 Fully Normal Algorithms on Two-Dimensional Arrays
306(1)
7.7.6 Normal Algorithms on Cube-Connected Cycles
307(1)
7.7.7 Fast Matrix Multiplication on the Hypercube
308(1)
7.8 Routing in Networks
309(2)
7.8.1 Local Routing Networks
309(1)
7.8.2 Global Routing Networks
310(1)
7.9 The PRAM Model
311(6)
7.9.1 Simulating Trees, Arrays, and Hypercubes on the PRAM
313(1)
7.9.2 The Power of Concurrency
314(1)
7.9.3 Simulating the PRAM on a Hypercube Network
315(2)
7.9.4 Circuits and the CREW PRAM
317(1)
7.10 The BSP and LogP Models
317(1)
Problems
318(4)
Chapter Notes
322(3)
III Computational Complexity 325(280)
8 Complexity Classes
327(64)
8.1 Introduction
328(1)
8.2 Languages and Problems
328(2)
8.2.1 Complements of Languages and Decision Problems
329(1)
8.3 Resource Bounds
330(1)
8.4 Serial Computational Models
331(3)
8.4.1 The Random-Access Machine
331(1)
8.4.2 Turing Machine Models
332(2)
8.5 Classification of Decision Problems
334(9)
8.5.1 Space and Time Hierarchies
336(1)
8.5.2 Time-Bounded Complexity Classes
337(1)
8.5.3 Space-Bounded Complexity Classes
338(3)
8.5.4 Relations Between Time- and Space-Bounded Classes
341(1)
8.5.5 Space-Bounded Functions
342(1)
8.6 Complements of Complexity Classes
343(6)
8.6.1 The Complement of NP
347(2)
8.7 Reductions
349(1)
8.8 Hard and Complete Problems
350(2)
8.9 P-Complete Problems
352(3)
8.10 NP-Complete Problems
355(8)
8.10.1 NP-Complete Satisfiability Problems
356(1)
8.10.2 Other NP-Complete Problems
357(6)
8.11 The Boundary Between P and NP
363(2)
8.12 PSPACE-Complete Problems
365(7)
8.12.1 A First PSPACE-Complete Problem
365(4)
8.12.2 Other PSPACE-Complete Problems
369(3)
8.13 The Circuit Model of Computation
372(4)
8.13.1 Uniform Families of Circuits
373(1)
8.13.2 Uniform Circuits Are Equivalent to Turing Machines
374(2)
8.14 The Parallel Random-Access Machine Model
376(4)
8.14.1 Equivalence of the CREW PRAM and Circuits
376(3)
8.14.2 The Parallel Computation Thesis
379(1)
8.15 Circuit Complexity Classes
380(3)
8.15.1 Efficiently Parallelizable Languages
380(2)
8.15.2 Circuits of Polynomial Size
382(1)
Problems
383(5)
Chapter Notes
388(3)
9 Circuit Complexity
391(70)
9.1 Circuit Models and Measures
392(2)
9.1.1 Circuit Models
392(1)
9.1.2 Complexity Measures
393(1)
9.2 Relationships Among Complexity Measures
394(5)
9.2.1 Effect of Fan-Out on Circuit Size
394(2)
9.2.2 Effect of Basis Change on Circuit Size and Depth
396(1)
9.2.3 Formula Size Versus Circuit Depth
396(3)
9.3 Lower-Bound Methods for General Circuits
399(5)
9.3.1 Simple Lower Bounds
399(1)
9.3.2 The Gate-Elimination Method for Circuit Size
400(4)
9.4 Lower-Bound Methods for Formula Size
404(5)
9.4.1 The Neciporuk Lower Bound
405(2)
9.4.2 The Krapchenko Lower Bound
407(2)
9.5 The Power of Negation
409(3)
9.6 Lower-Bound Methods for Monotone Circuits
412(24)
9.6.1 The Path-Elimination Method
413(4)
9.6.2 The Function Replacement Method
417(7)
9.6.3 The Approximation Method
424(7)
9.6.4 Slice Functions
431(5)
9.7 Circuit Depth
436(14)
9.7.1 Communication Complexity
437(1)
9.7.2 General Depth and Communication Complexity
438(2)
9.7.3 Monotone Depth and Communication Complexity
440(2)
9.7.4 The Monotone Depth of the Clique Function
442(5)
9.7.5 Bounded-Depth Circuits
447(3)
Problems
450(5)
Chapter Notes
455(6)
10 Space--Time Tradeoffs
461(68)
10.1 The Pebble Game
462(2)
10.1.1 The Pebble Game Versus the Branching Program
462(1)
10.1.2 Playing the Pebble Game
463(1)
10.2 Space Lower Bounds
464(2)
10.3 Extreme Tradeoffs
466(2)
10.4 Grigoriev's Lower-Bound Method
468(4)
10.4.1 Flow Properties of Functions
468(2)
10.4.2 The Lower-Bound Method in the Basic Pebble Game
470(2)
10.4.3 First Matrix Multiplication Bound
472(1)
10.5 Applications of Grigoriev's Method
472(10)
10.5.1 Convolution
473(1)
10.5.2 Cyclic Shifting
474(1)
10.5.3 Integer Multiplication
475(1)
10.5.4 Matrix Multiplication
476(3)
10.5.5 Discrete Fourier Transform
479(2)
10.5.6 Merging Networks
481(1)
10.6 Worst-Case Tradeoffs for Pebble Games(*)
482(1)
10.7 Upper Bounds on Space(*)
483(1)
10.8 Lower Bound on Space for General Graphs(*)
484(4)
10.9 Branching Programs
488(7)
10.9.1 Branching Programs and Other Models
493(2)
10.10 Straight-Line Versus Branching Programs
495(2)
10.10.1 Efficient Branching Programs for Cyclic Shift
496(1)
10.10.2 Efficient Branching Programs for Merging
496(1)
10.11 The Borodin-Cook Lower-Bound Method
497(4)
10.12 Properties of "nice" and "ok" Matrices(*)
501(3)
10.13 Applications of the Borodin-Cook Method
504(15)
10.13.1 Convolution
505(1)
10.13.2 Integer Multiplication
506(1)
10.13.3 Matrix-Vector Product
507(2)
10.13.4 Matrix Multiplication(*)
509(2)
10.13.5 Matrix Inversion
511(2)
10.13.6 Discrete Fourier Transform
513(1)
10.13.7 Unique Elements
514(3)
10.13.8 Sorting
517(2)
Problems
519(7)
Chapter Notes
526(3)
11 Memory-Hierarchy Tradeoffs
529(46)
11.1 The Red-Blue Pebble Game
530(3)
11.1.1 Playing the Red-Blue Pebble Game
532(1)
11.1.2 Balanced Computer Systems
532(1)
11.2 The Memory-Hierarchy Pebble Game
533(2)
11.2.1 Playing the MHG
535(1)
11.3 I O-Time Relationships
535(2)
11.4 The Hong-Kung Lower-Bound Method
537(2)
11.5 Tradeoffs Between Space and I O Time
539(16)
11.5.1 Matrix-Vector Product
539(2)
11.5.2 Matrix-Matrix Multiplication
541(5)
11.5.3 The Fast Fourier Transform
546(6)
11.5.4 Convolution
552(3)
11.6 Block I O in the MHG
555(3)
11.7 Simulating a Fast Memory in the MHG
558(1)
11.8 RAM-Based I O Models
559(4)
11.8.1 The Block-Transfer Model
559(4)
11.9 The Hierarchical Memory Model
563(4)
11.9.1 Lower Bounds for the HMM
564(3)
11.9.2 Upper Bounds for the HMM
567(1)
11.10 Competitive Memory Management
567(2)
11.10.1 Two-Level Memory-Management Algorithms
568(1)
Problems
569(4)
Chapter Notes
573(2)
12 VLSI Models of Computation
575(30)
12.1 The VSLI Challenge
576(2)
12.1.1 Chip Fabrication
576(1)
12.1.2 Design and Layout
577(1)
12.2 VLSI Physical Models
578(1)
12.3 VLSI Computational Models
579(1)
12.4 VLSI Performance Criteria
580(1)
12.5 Chip Layout
581(5)
12.5.1 The H-Tree Layout
581(2)
12.5.2 Multi-dimensional Mesh Layouts
583(1)
12.5.3 Layout of the CCC Network
584(2)
12.6 Area-Time Tradeoffs
586(6)
12.6.1 Planar Circuit Size
586(1)
12.6.2 Computational Inequalities
587(2)
12.6.3 The Planar Separator Theorem
589(3)
12.7 The Performance of VLSI Algorithms
592(5)
12.7.1 The Performance VLSI Algorithms on Functions
593(2)
12.7.2 The Performance of VLSI Algorithms on Predicates
595(2)
12.8 Area Bounds
597(1)
Problems
598(3)
Chapter Notes
601(4)
Bibliography 605(18)
Index 623

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews