计算理论导论：英文版

　　This book—by a nated authority and educator in the field—presents computer science theory from a uniquely intuitive，"big picture"perspective.The author grounds his clear and interesting study on broad mathematical principles，not low-level technical details：proofs are presented with a "proof idea"component that reveals the concept underlying the mathematical formalism.Similarly，algorithms are presented using prose rather than pseudocode to focus attention on the algorithms themselves，rather than on specific models.Formerly published in a Preliminary Edition，this First Edition features additional chapters on space complesity（Chapter 8），provable intractability（Chapter 9）and advanced topics in computability theory（Chapter 10）.For further information，see the World Wide Web site for the book at：http：//www-math.mit.edu/sipser/book.html

暂缺《计算理论导论：英文版》作者简介

Preface                  
 To the student                  
 To the educator                  
 The current edition                  
 Feedback to the author                  
 Acknowledgments                  
                   
 0 Introduction                  
 0. l 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                  
 O.3 Definitions, Theorems, and Proofs                  
 Finding proofs                  
 0.4 Types of Proof                  
 Proof by construction                  
 Proof by contradiction                  
 Proof by induction                  
 Exercises and Problems                  
                   
 Part One: Automata and                  
 l Regular                  
 l . l Finite Automata                  
 Formal definition of a finite automaton                  
 Examples of finite automata                  
 Formal definition of computation                  
 Designing finite automata                  
 The regular operations                  
 l .2 Nondeterminism                  
 Formal definition of a nondeterministic finite automaton                  
 Equivalence of NFAs and DFAs                  
 Closure under the regular operations                  
 l . 3 Regular Expressions                  
 Formal definition of a regular expression                  
 Equivalence with finite automata                  
 l .4 Nonregular Languages                  
 The pumping lemma for regular languages                  
 Exercises and Problems                  
                   
 2 Context-Free Languages                  
 2 . l 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 pushdown automaton                  
 Examples of pushdown automata                  
 Equivalence with context-free grammars                  
 2 . 3 Non-context-free Languages                  
 The pumping lemma for context-free languages                  
 Exercises and Problems                  
                   
 Part Two: Computability Theory                  
 3 The Church-Turing Thesis                  
 3 . l 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 and Problems                  
                   
 4 Decidability                  
 4. l Decidable Languages                  
 Decidable problems concerning regular languages                  
 Decidable problems concerning context-free languages                  
 4.2 The Halting Problem                  
 The diagonalization method                  
 The halting problem is undecidable                  
 A Turing-unrecognizable language                  
 Exercises and Problems                  
                   
 5 Reducibility                  
 5 . l Undecidable Problems from Language Theory                  
 Reductions via computation histories                  
 5.2 A Simple Undecidable Problem                  
 5 . 3 Mapping Reducibility                  
 Computable functions                  
 Formal definition of mapping reducibility                  
 Exercises and Problems                  
                   
 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 and Problems                  
                   
 Part Three: Complexity Theory                  
 7 Time Complexity                  
 7. l 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 and Problems                  
                   
 8 Space Complexity                  
 8. l 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 Land NL                  
 8. 5 NL-completeness                  
 Searching in graphs                  
 8.6 NL equals coNL                  
 Exercises and Problems                  
                   
 9 Intractability                  
 9. l Hierarchy Theorems                  
 Exponential space completeness                  
 9.2 Relativization                  
 Limits of the diagonalization method                  
 9. 3 Circuit Complexity                  
 Exercises and Problems                  
                   
 10 Advanced topics in complexity theory                  
 l0. l Approximation Algorithms                  
 l0.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                  
 l0.5 Parallel Compuation                  
 Uniform Boolean circuits                  
 The class NC                  
 P-completeness                  
 IO.6 Cryptography                  
 Secret keys                  
 Public-key cryptosystems                  
 One-way functions                  
 Trapdoor functions                  
 Exercises and Problems                  
                   
 Selected Bibliography                  
 Index