具體描述
本書由計算理論領域的知名權威Michael Sipser所撰寫。他以獨特的視角，係統地介紹瞭計算理論的三個主要內容：自動機與語言、可計算性理論和計算復雜性理論。絕大部分內容是基本的，同時對可計算性和計算復雜性理論中的某些高級內容進行瞭重點介紹。作者以清新的筆觸、生動的語言給齣瞭寬泛的數學原理，而沒有拘泥於某些低層次的細節。在證明之前，均有“證明思路”，幫助讀者理解數學形式下蘊涵的概念。同樣，對於算法描述，均以直觀的文字而非僞代碼給齣，從而將注意力集中於算法本身，而不是某些模型。新版根據多年來使用本書的教師和學生的建議進行瞭改進，並用一節的篇幅對確定型上下文無關語言進行瞭直觀而不失嚴謹的介紹。此外，對練習和問題進行瞭全麵更新，每章末均有習題選答。
著者簡介
邁剋爾·西普塞（Michael Sipser） 美國麻省理工學院數學係教授，計算機科學和人工智能實驗室（CSAIL）成員。2004~2014年任數學係主任，2014年起任理學院院長。他癡迷於復雜性理論，目前從事理論計算機科學與其他數學課程的教學工作已超過30年。
圖書目錄
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
· · · · · · (收起)
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
· · · · · · (收起)
讀後感
評分
本书的作者是著名的计算理论方面专家，麻省理工学院应用数学系主任 M. Sipser。全书分为11章，并附有部分习题解答。全书思路清晰，由浅入深，内容详细，是一本零起点学习计算理论的理想教材。我是出于研究需要阅读此书的。其中第零章简要介绍了所需要的基本数学知识。第一到三...
評分 評分我觉得作者很可爱，他同很多人一样很喜欢把一个复杂的问题说的很简单很通俗。 对于这本书来说，看了第一章，就应当一成的收获。计算机中重要的数学概念被解构的如此清楚，非常的难得。 另外，要说一下，翻译的问题。翻译的很不错（话说本来英文版就很上口），但是却是看原版会...
評分我觉得作者很可爱，他同很多人一样很喜欢把一个复杂的问题说的很简单很通俗。 对于这本书来说，看了第一章，就应当一成的收获。计算机中重要的数学概念被解构的如此清楚，非常的难得。 另外，要说一下，翻译的问题。翻译的很不错（话说本来英文版就很上口），但是却是看原版会...
評分本书的作者是著名的计算理论方面专家，麻省理工学院应用数学系主任 M. Sipser。全书分为11章，并附有部分习题解答。全书思路清晰，由浅入深，内容详细，是一本零起点学习计算理论的理想教材。我是出于研究需要阅读此书的。其中第零章简要介绍了所需要的基本数学知识。第一到三...
用戶評價
评分
譯者和原作錶達上沒有很大的區彆，都很抽象。
评分譯者和原作錶達上沒有很大的區彆，都很抽象。
评分譯者和原作錶達上沒有很大的區彆，都很抽象。
评分沒有想象中的好，挺囉嗦的，而且有些地方講得不清不楚，不過圖靈機的概念和P和NP問題懂瞭些，不過似懂非懂，覺得講得不是很清楚。本來以為能好好講講計算復雜度，沒想到都隻是講瞭些概念。如果想找大O的內容，不妨看看孫智偉翻譯的silverman的數論概論的第40章，講得比較簡單清楚。
评分沒有想象中的好，挺囉嗦的，而且有些地方講得不清不楚，不過圖靈機的概念和P和NP問題懂瞭些，不過似懂非懂，覺得講得不是很清楚。本來以為能好好講講計算復雜度，沒想到都隻是講瞭些概念。如果想找大O的內容，不妨看看孫智偉翻譯的silverman的數論概論的第40章，講得比較簡單清楚。
相關圖書
本站所有內容均為互聯網搜索引擎提供的公開搜索信息，本站不存儲任何數據與內容，任何內容與數據均與本站無關，如有需要請聯繫相關搜索引擎包括但不限於百度，google,bing,sogou 等
© 2025 book.quotespace.org All Rights Reserved. 小美書屋 版权所有