本書由計(jì)算理論領(lǐng)域的學(xué)者M(jìn)ichaelSipser所撰寫。他以獨(dú)特的視角，系統(tǒng)地介紹了計(jì)算理論的三大主要內(nèi)容：自動(dòng)機(jī)與語言，可計(jì)算性理論，計(jì)算復(fù)雜性理論。全書以清新的筆觸、生動(dòng)的語言給出了寬泛的數(shù)學(xué)原理，而沒有拘泥于某些低層次的細(xì)節(jié)。在證明之前，均有“證明思路”，幫助讀者理解數(shù)學(xué)形式下蘊(yùn)涵的概念。本書可作為計(jì)算機(jī)專業(yè)高年級(jí)本科生和研究生的教材，也可作為研究人員的參考書。
Michael Sipser 美國(guó)麻省理工學(xué)院應(yīng)用數(shù)學(xué)系教授，計(jì)算機(jī)科學(xué)和人工智能實(shí)驗(yàn)室（CSAIL）成員。他從事理論計(jì)算機(jī)科學(xué)與其他數(shù)學(xué)課程的教學(xué)工作三十多年，目前為數(shù)學(xué)系主任。他癡迷于復(fù)雜性理論，喜歡復(fù)雜性理論的教學(xué)工作。
加作者照片
CONTENTS
PrefacetotheFirstEdition.iv
To the student.iv
To the educatorv
The frst editionvi
Feedback to the authorvi
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 theory3
0.2 Mathematical Notions and Terminology3
Sets.3
Sequences and tuples.6
Functions and relations7
Graphs.10
Strings and languages.13
Boolean logic14
Summary of mathematical terms.16
0.3 Defnitions, Theorems, and Proofs.17
Finding proofs.17
0.4 Typesof Proof21
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 automata37
Formal defnition of computation40
Designing fnite automata.41
The regular operations44
1.2 Nondeterminism.47
Formal defnition of a nondeterministic fnite automaton53
Equivalence of NFAs and DFAs.54
Closure under the regular operations.58
1.3 Regular Expressions.63
Formal defnition of a regular expression64
Equivalence with fnite automata.66
1.4 Nonregular Languages77
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 grammar104
Examples of context-free grammars.105
Designing context-free grammars106
Ambiguity.107
Chomsky normal form108
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 Languages125
The pumping lemma for context-free languages.125
2.4 Deterministic Context-Free Languages.130
Properties of DCFLs.133
Deterministic context-free grammars135
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 machine167
Examples of Turing machines.170
3.2 Variants of Turing Machines.176
Multitape Turing machines176
Nondeterministic Turing machines178
Enumerators180
Equivalence with other models181
3.3 The Defnition of Algorithm182
Hilbert’s problems.182
Terminology for describing Turing machines184
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 Undecidability201
The diagonalization method.202
An undecidable language.207
A Turing-unrecognizable language209
Exercises, Problems, and Solutions.210
5 Reducibility.215
5.1 Undecidable Problems from Language Theory216
Reductions via computation histories.220
5.2 A Simple Undecidable Problem.227
5.3 Mapping Reducibility234
Computable functions.234
Formal defnition of mapping reducibility235
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
Applications250
6.2 Decidability of logical theories.252
A decidable theory.255
An undecidable theory.257
6.3 Turing Reducibility260
6.4 A Defnition of Information.261
Minimal length descriptions.262
Optimality of the defnition266
Incompressible strings and randomness.267
Exercises, Problems, and Solutions.270
Part Three: Complexity Theory.273
7 Time Complexity.275
7.1 Measuring Complexity275
Big-O and small-o notation276
Analyzing algorithms.279
Complexity relationships among models.282
7.2 The Class P284
Polynomial time284
Examples of problems in P286
7.3 The Class NP.292
Examples of problemsin NP.295
The Pversus NP question297
7.4 NP-completeness.299
Polynomial time reducibility.300
Defnition of NP-completeness304
The Cook–Levin Theorem304
7.5 Additional NP-complete Problems.311
The vertex cover problem.312
The Hamilto
新書資訊