Models of computation : exploring the power of computing
著者
書誌事項
Models of computation : exploring the power of computing
Addison Wesley, c1998
大学図書館所蔵 全20件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
注記
Includes bibliographical references (p. 605-622) and index
内容説明・目次
内容説明
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.
目次
(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
「Nielsen BookData」 より