| 作者 |
| （美）迈克尔·西普塞（Michael Sipser） |
| 丛书名 |
| 经典原版书库 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9787111602057 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 本书由计算理论领域的知名学者MichaelSipser所撰写。他以独特的视角，系统地介绍了计算理论的三大主要内容：自动机与语言，可计算性理论，计算复杂性理论。全书以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为研究人员的参考书。 |
| 目录 |
| PrefacetotheFirstEdition.........................iv To the student...........................iv To the educator..........................v The frst edition..........................vi Feedback to the author......................vi Acknowledgments.........................vii Preface to the Second Edition.........................ix Preface to the Third Edition.........................xi 0 Introduction.........................1 0.1 Automata, Computability, and Complexity.............1 Complexity theory.........................2 Computability theory.......................3 Automata theory..........................3 0.2 Mathematical Notions and Terminology..............3 Sets.................................3 Sequences and tuples.......................6 Functions and relations......................7 Graphs...............................10 Strings and languages.......................13 Boolean logic............................14 Summary of mathematical terms.................16 0.3 Defnitions, Theorems, and Proofs.................17 Finding proofs...........................17 0.4 Typesof Proof............................21 Proof by construction.......................21 Proof by contradiction.......................21 Proof by induction.........................22 Exercises, Problems, and Solutions...................25 PartOne: AutomataandLanguages...................29 1 RegularLanguages...................31 1.1 Finite Automata...........................31 Formal defnition of afnite automaton.............35 Examples of fnite automata....................37 Formal defnition of computation................40 Designing fnite automata.....................41 The regular operations......................44 1.2 Nondeterminism...........................47 Formal defnition of a nondeterministic fnite automaton....53 Equivalence of NFAs and DFAs.................54 Closure under the regular operations...............58 1.3 Regular Expressions.........................63 Formal defnition of a regular expression............64 Equivalence with fnite automata.................66 1.4 Nonregular Languages........................77 The pumping lemma for regular languages...........77 Exercises, Problems, and Solutions...................83 2 Context-Free Languages...................101 2.1 Context-Free Grammars.......................102 Formal defnition of acontext-free grammar..........104 Examples of context-free grammars...............105 Designing context-free grammars................106 Ambiguity.............................107 Chomsky normal form......................108 2.2 Pushdown Automata.........................111 Formal defnition of a pushdown automaton...........113 Example of pushdow automata.................114 Equivalence with context-free grammars.............117 2.3Non-Context-Free Languages....................125 The pumping lemma for context-free languages.........125 2.4 Deterministic Context-Free Languages...............130 Properties of DCFLs.......................133 Deterministic context-free grammars..............135 Relationship of DPDAs and DCFGs...............146 Parsing and LR(k) grammars...................151 Exercises, Problems, and Solutions...................154 PartTwo: Computability Theory...................163 3 The Church–Turing Thesis...................165 3.1 Turing Machines...........................165 Formal defnition of a Turing machine..............167 Examples of Turing machines...................170 3.2 Variants of Turing Machines.....................176 Multitape Turing machines....................176 Nondeterministic Turing machines................178 Enumerators............................180 Equivalence with other models..................181 3.3 The Defnition of Algorithm....................182 Hilbert’s problems.........................182 Terminology for describing Turing machines..........184 Exercises, Problems, and Solutions...................187 4 Decidability...................193 4.1 Decidable Languages.........................194 Decidable problems concerning regular languages.......194 Decidable problems concerning context-free languages.....198 4.2 Undecidability............................201 The diagonalization method...................202 An undecidable language.....................207 A Turing-unrecognizable language................209 Exercises, Problems, and Solutions...................210 5 Reducibility...................215 5.1 Undecidable Problems from Language Theory..........216 Reductions via computation histories...............220 5.2 A Simple Undecidable Problem...................227 5.3 Mapping Reducibility........................234 Computable functions.......................234 Formal defnition of mapping reducibility............235 Exercises, Problems, and Solutions...................239 6 Advanced Topicsin Computability Theory...................245 6.1 The Recursion Theorem.......................245 Self-reference...........................246 Terminology for the recursion theorem.............249 Applications............................250 6.2 Decidability of logical theories...................252 A decidable theory.........................255 An undecidable theory.......................257 6.3 Turing Reducibility..........................260 6.4 A Defnition of Information.....................261 Minimal length descriptions...................262 Optimality of the defnition....................266 Incompressible strings and randomness.............267 Exercises, Problems, and Solutions...................270 Part Three: Complexity Theory...................273 7 Time Complexity...................275 7.1 Measuring Complexity........................275 Big-O and small-o notation....................276 Analyzing algorithms.......................279 Complexity relationships among models.............282 7.2 The Class P..............................284 Polynomial time..........................284 Examples of problems in P....................286 7.3 The Class NP.............................292 Examples of problemsin NP...................295 The Pversus NP question....................297 7.4 NP-completeness...........................299 Polynomial time reducibility...................300 Defnition of NP-completeness..................304 The Cook–Levin Theorem....................304 7.5 Additional NP-complete Problems.................311 The vertex cover problem.....................312 The Hamiltonian path problem.................314 The subset sum problem.....................319 Exercises, Problems, and Solutions...................322 8 Space Complexity...................331 8.1 Savitch’s Theorem..........................333 8.2 The Class PSPACE.........................336 8.3 PSPACE-completeness.......................337 The TQBF problem........................338 Winning strategies for games...................341 Generalized geography......................343 8.4 The Classes L and NL........................348 8.5 NL-completeness..........................351 Searching in graphs........................353 8.6 NL equals coNL...........................354 Exercises, Problems, and Solutions...................357 9 Intractability...................363 9.1 Hierarchy Theorems.........................364 Exponential space completeness.................371 9.2 Relativization.............................376 Limits of the diagonalization method..............377 9.3 Circuit Complexity..........................379 Exercises, Problems, and Solutions...................38 10 Advanced Topicsin Complexity Theory...................393 10.1 Approximation Algorithms.....................393 10.2 Probabilistic Algorithms.......................396 The class BPP...........................396 Primality..............................399 Read-once branching programs..................404 10.3 Alternation..............................408 Alternating time and space....................410 The Polynomial time hierarchy..................414 10.4 Interactive Proof Systems......................415 Graph nonisomorphism......................415 Defnition of the model......................416 IP=PSPACE...........................418 10.5 Parallel Computation........................427 Uniform Boolean circuits.....................428 The class NC...........................430 P-completeness..........................432 10.6 Cryptography.............................433 Secret keys.............................433 Public-key cryptosystems.....................435 One-way functions.........................435 Trapdoor functions........................437 Exercises, Problems, and Solutions...................439 Selected Bibliography...................443 Index...................448 |