- 作 者：（美）Michael Sipser著
- 出 版 社：北京：机械工业出版社
- 出版年份：2002
- ISBN：711110840X
- 标注页数：396 页
- PDF页数：411 页
请阅读订购服务说明与试读!
订购服务说明
1、本站所有的书默认都是PDF格式，该格式图书只能阅读和打印，不能再次编辑。
2、除分上下册或者多册的情况下，一般PDF页数一定要大于标注页数才建议下单购买。【本资源411 ≥396页】
图书下载及付费说明
1、所有的电子图书为PDF格式，支持电脑、手机、平板等各类电子设备阅读；可以任意拷贝文件到不同的阅读设备里进行阅读。
2、电子图书在提交订单后一般半小时内处理完成,最晚48小时内处理完成。(非工作日购买会延迟)
3、所有的电子图书都是原书直接扫描方式制作而成。
0 Introduction 1
0.1 Automata,Computability,and Complexity 1
Complexity theory 2
Computability theory 2
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 Definitions,Theorems,and Proofs 17
Finding proofs 17
0.4 Types of Proof 21
Proof by construction 21
Proof by contradiction 21
Proof by induction 23
Exercises and Problems 25
Part One:Automata and Languages 29
1 Regular Languages 31
1.1 Finite Automata 31
Formal definition of a finite automaton 35
Examples of finite automata 37
Formal definition of computation 40
Designing finite automata 41
The regular operations 44
1.2 Nondeterminism 47
Formal definition of a nondeterministic finite automaton 53
Equivalence of NFAs and DFAs 54
Closure under the regular operations 58
1.3 Regular Expressions 63
Formal definition ofa regular expression 64
Equivalence with finite automata 66
1.4 Nonregular Languages 77
Thepumping lemma for regular languages 77
Exercises and Problems 83
2 Context-Free Languages 91
2.1 Context-free Grammars 92
Formal definition of a context-free grammar 94
Examples of context-free grammars 95
Designing context-free grammars 96
Ambiguity 97
Chomsky normal form 98
2.2 Pushdown Automata 101
Formal definition of a pushdown automaton 103
Examples of pushdown automata 104
Equivalence with context-free grammars 106
The pumping lemma for context-free languages 115
2.3 Non-context-free Languages 115
Exercises and Problems 119
Part Two：Computability Theory 123
3 The Church-Turing Thesis 125
3.1 Turing Machines 125
Formal definition of a Turing machine 127
Examples of Turing machines 130
3.2 Variants of Turing Machines 136
Multitape Turing machines 136
Nondeterministic Turing machines 138
Enumerators 140
Equivalence with other models 141
3.3 The Definition of Algorithm 142
Hilbert's problems 142
Terminology for describing Turing machines 144
Exercises and Problems 147
4 Decidability 151
4.1 Decidable Languages 152
Decidable problems concerning regular languages 152
Decidable problems concerning context-free languages 156
4.2 The Halting Problem 159
The diagonalization method 160
The halting problem is undecidable 165
ATuring-unrecognizable language 167
Exercises and Problems 168
5 Reducibility 171
5.1 Undecidable Problems from Language Theory 172
Reductions via computation histories 176
5.2 A Simple Undecidable Problem 183
5.3 Mapping Reducibility 189
Computable functions 190
Formal definition ofmapping reducibility 191
Exercises and Problems 195
6 Advanced Topics in Computability Theory 197
6.1 The Recursion Theorem 197
Self-reference 198
Terminology for the recursion theorem 201
Applications 202
6.2 Decidability of logical theories 204
A decidable theory 206
An undecidable theory 209
6.3 Turing Reducibility 211
6.4 A Definition of Information 213
Minimal length descriptions 214
Optimality of the definition 217
Incompressible strings and randomness 217
Exercises and Problems 220
Part Three:Complexity Theory 223
7 Time Complexity 225
7.1 Measuring Complexity 225
Big-O and small-o notation 226
Analyzing algorithms 229
Complexity relationships among models 231
7.2 The Class P 234
Polynomial time 234
Examples of problems in P 236
7.3 The Class NP 241
Examples of problemsin NP 245
The P versus NP question 247
7.4 NP-completeness 248
Polynomial time reducibility 249
Definition of NP-completeness 253
The Cook-Levin Theorem 254
7.5 Additional NP-complete Problems 260
The vertex cover problem 261
The Hamiltonian path problem 262
The subset sum problem 268
Exercises and Problems 271
8 Space Complexity 277
8.1 Savitch's Theorem 279
8.2 The Class PSPACE 281
The TQBF problem 283
8.3 PSPACE-completeness 283
Winning strategies for games 287
Generalized geography 289
8.4 The Classes L and NL 294
8.5 NL-completeness 297
Searching in graphs 298
8.6 NL equals coNL 300
Exercises and Problems 302
9 Intractability 305
9.1 Hierarchy Theorems 306
Exponential space completeness 313
9.2 Relativization 318
Limits of the diagonalization method 319
9.3 Circuit Complexity 321
Exercises and Problems 330
10 Advanced topics in complexity theory 333
10.1 Approximation Algorithms 333
10.2 Probabilistic Algorithms 335
The class BPP 336
Primality 339
Read-once branching programs 343
10.3 Alternation 348
Alternating time and space 349
The Polynomial time hierarchy 353
10.4 Interactive Proof Systems 354
Graph nonisomorphism 355
Definition of the model 355
IP=PSPACE 357
10.5 Parallel Computation 366
Uniform Boolean circuits 367
The class NC 369
P-completeness 371
10.6 Cryptography 372
Secret keys 372
Public-key cryptosystems 374
One-way functions 374
Trapdoor functions 376
Exercises and Problems 378
Selected Bibliography 381
Index 387