导语

  

内容提要

  

    迈克尔·西普塞著的《计算理论导引(英文版第3版)》由计算理论领域的知名学者Michael Sipser所撰写。他以独特的视角，系统地介绍了计算理论的三大主要内容：自动机与语言，可计算性理论，计算复杂性理论。书中大部分内容是基础的，同时也讨论了可计算性和计算复杂性理论中的某些高级内容。
    在讲解数学原理时，笔触清新、语言生动，不拘泥于某些低层次的细节；在证明问题时，均先给出“证明思路”，帮助读者理解数学形式下蕴涵的概念；在分析算法时，用直观文字而非伪代码进行描述，从而将注意力集中于算法本身。而不是某些模型。
    新版根据多年来使用本书的教师和学生的建议进行了改进，并用一节的篇幅对确定型上下文无关语言进行了简洁而不失严谨的介绍。此外，对练习和问题进行了全面更新，每章末均有习题选答。

    迈克尔·西普塞 Michael Sipser　美国麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作三十多年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。

Preface to the First Edition
  To the student
  To the educator
  The first edition
  Feedback to the author
  Acknowledgments
Preface to the Second Edition
Preface to the Third Edition
0 Introduction
0.1 Automata, Computability, and Complexity
  Complexity theory
  Computability theory
  Automata theory
0.2 Mathematical Notions and Terminology
  Sets
  Sequences and tuples
  Functions and relations
  Graphs
  Strings and languages
  Boolean logic
  Summary of mathematical terms
0.3 Definitions, Theorems, and Proofs
  Finding proofs
0.4 Types of Proof
  Proof by construction
  Proof by contradiction
  Proof by induction
  Exercises, Problems, and Solutions
Part One: Automata and Languages
Regular Languages
1.1 Finite Automata
  Formal definition of a finite automaton
  Examples of finite automata
  Formal definition of computation
  Designing finite automata
  The regular operations
1.2 Nondeterminism
  Formal definition of a nondeterministic finite automaton.
  Equivalence of NFAs and DFAs
  Closure under the regular operations
1.3 Regular Expressions
  Formal definition of a regular expression
  Equivalence with finite automata
1.4 Nonregular Languages
  The pumping lemma for regular languages
  Exercises, Problems, and Solutions
Context-Free Languages
2.1 Context-Free Grammars
  Formal definition of a context-free grammar
  Examples of context-free grammars
  Designing context-free grammars
  Ambiguity
  Chomsky normal form
2.2 Pushdown Automata
  Formal definition of a p ushdown automaton
  Examples of pushdownautomata
  Equivalence with context-free grammars
2.3 Non-Context-Free Languages
  The pumping lemma for context-free languages
2.4 Deterministic Context-Free Languages
  Properties of DCFLs
  Deterministic context-free grammars
  Relationship of DPDAs and DCFGs
  Parsing and LR(k) grammars
  Exercises, Problems, and Solutions
Part Two: Computability Theory
The Church-Turing Thesis
3.1 Turing Machines
  Formal definition of a Turing machine
  Examples of Turing machines
3.2 Variants of Turing Machines
  Multitape Turing machines
  Nondeterministic Turing machines
  Enumerators
  Equivalence with other models
3.3 The Definition of Algorithm
  Hilbert's problems
  Terminology for describing Turing machines
  Exercises, Problems, and Solutions
Decidability
4.1 Decidable Languages
  Decidable problems concerning regular languages
  Decidable problems concerning context-free languages
4.2 Undecidability
  The diagonalization method
  An undecidable language
  A Turing-unrecognizable language
  Exercises, Problems, and Solutions
Reducibility
5.1 Undecidable Problems from Language Theory
  Reductions via computation histories
5.2 A Simple Undecidable Problem
5.3 Mapping Reducibility
  Computable fimctions
  Formal definition of mapping reducibility
  Exercises, Problems, and Solutions
6 Advanced Topics in Computability Theory
6.1 The Recursion Theorem
  Self-reference
  Terminology for the recursion theorem
  Applications
6.2 Decidability of logical theories
  A decidable theory
  An undecidable theory
6.3 Turing Reducibility
6.4 A Definition of Information
  Minimal length descriptions
  Optimality of the definition
  Incompressible strings and randomness
  Exercises, Problems, and Solutions
Part Three: Complexity Theory
7 Time Complexity
7.1 Measuring Complexity
  Big-O and small-o notation
  Analyzing algorithms
  Complexity relationships among models
7.2 The Class P
  Polynomial time
  Examples of problems in P
7.3 The Class NP
  Examples of problems in NP
  The P versus NP question
7.4 NP-completeness
  Polynomial time reducibility
  Definition of NP-completeness
  The Cook-Levin Theorem
7.5 Additional NP-complete Problems
  The vertex cover problem
  The Hamiltonian path problem
  The subset sum problem
  Exercises, Problems, and Solutions
8 Space Complexity
8.1 Savitch's Theorem
8.2 The Class PSPACE
8.3 PSPACE-completeness
  The TQBF problem
  Winning strategies for games
  Generalized geography
8.4 The Classes L and NL
8.5 NL-completeness
  Searching in graphs
8.6 NL equals coNL
  Exercises, Problems, and Solutions
9 Intractability
9.1 Hierarchy Theorems
  Exponential space completeness
9.2 Relativization
  Limits of the diagonalization method
9.3 Circuit Complexity
  Exercises, Problems, and Solutions
10 Advanced Topics in Complexity Theory
10.1 Approximation Algorithms
10.2 Probabilistic Algorithms
  The class BPP
  Primality
  Read-once branching programs
10.3 Alternation
  Alternating time and space
  The Polynomial time hierarchy
10.4 Interactive Proof Systems .
  Graph nonisomorphism
  Definition of the model
  IP = PSPACE
10.5 Parallel Computation
  Uniform Boolean circuits
  The class NC
  P-completeness
10.6 Cryptography
  Secret keys
  Public-key cryptosystems
  One-way functions
  Trapdoor functions
  Exercises, Problems, and Solutions
Selected Bibliography
Index