计算理论导引（原书第3版）

Introduction to the Theory of Computation,3e

出版者的话

译者序

第3版前言

第2版前言

第1版前言

第0章绪论

0 1自动机、可计算性与复杂性

0 1 1计算复杂性理论

0 1 2可计算性理论

0 1 3自动机理论

0 2数学概念和术语

0 2 1集合

0 2 2序列和多元组

0 2 3函数和关系

0 2 4图

0 2 5字符串和语言

0 2 6布尔逻辑

0 2 7数学名词汇总

0 3定义、定理和证明

0 4证明的类型

0 4 1构造性证明

0 4 2反证法

0 4 3归纳法

练习

问题

习题选解

部分自动机与语言

第1章正则语言

1 1有穷自动机

1 1 1有穷自动机的形式化定义

1 1 2有穷自动机举例

1 1 3计算的形式化定义

1 1 4设计有穷自动机

1 1 5正则运算

1 2非确定性

1 2 1非确定型有穷自动机的形式化定义

1 2 2NFA与DFA的等价性

1 2 3在正则运算下的封闭性

1 3正则表达式

1 3 1正则表达式的形式化定义

1 3 2与有穷自动机的等价性

1 4非正则语言

练习

问题

习题选解

第2章上下文无关文法

2 1上下文无关文法概述

2 1 1上下文无关文法的形式化定义

2 1 2上下文无关文法举例

2 1 3设计上下文无关文法

2 1 4歧义性

2 1 5乔姆斯基范式

2 2下推自动机

2 2 1下推自动机的形式化定义

2 2 2下推自动机举例

2 2 3与上下文无关文法的等价性

2 3非上下文无关语言

2 4确定型上下文无关语言

2 4 1DCFL的性质

2 4 2确定型上下文无关文法

2 4 3DPDA和DCFG的关系

2 4 4语法分析和LR(k)文法

练习

问题

习题选解

第二部分可计算性理论

第3章丘奇图灵论题

3 1图灵机

3 1 1图灵机的形式化定义

3 1 2图灵机的例子

3 2图灵机的变形

3 2 1多带图灵机

3 2 2非确定型图灵机

3 2 3枚举器

3 2 4与其他模型的等价性

3 3算法的定义

3 3 1希尔伯特问题

3 3 2描述图灵机的术语

练习

问题

习题选解

第4章可判定性

4 1可判定语言

4 1 1与正则语言相关的可判定性问题

4 1 2与上下文无关语言相关的可判定性问题

4 2不可判定性

4 2 1对角化方法

4 2 2不可判定语言

4 2 3一个图灵不可识别语言

练习

问题

习题选解

第5章可归约性

5 1语言理论中的不可判定问题

5 2一个简单的不可判定问题

5 3映射可归约性

5 3 1可计算函数

5 3 2映射可归约性的形式化定义

练习

问题

习题选解

第6章可计算性理论的高级专题

6 1递归定理

6 1 1自引用

6 1 2递归定理的术语

6 1 3应用

6 2逻辑理论的可判定性

6 2 1一个可判定的理论

6 2 2一个不可判定的理论

6 3图灵可归约性

6 4信息的定义

6 4 1极小长度的描述

6 4 2定义的优化

6 4 3不可压缩的串和随机性

练习

问题

习题选解

第三部分复杂性理论

第7章时间复杂性

7 1度量复杂性

7 1 1大O和小o记法

7 1 2分析算法

7 1 3模型间的复杂性关系

7 2P类

7 2 1多项式时间

7 2 2P中的问题举例

7 3NP类

7 3 1NP中的问题举例

7 3 2P与NP问题

7 4NP完全性

7 4 1多项式时间可归约性

7 4 2NP完全性的定义

7 4 3库克列文定理

7 5几个NP完全问题

7 5 1顶点覆盖问题

7 5 2哈密顿路径问题

7 5 3子集和问题

练习

问题

习题选解

第8章空间复杂性

8 1萨维奇定理

8 2PSPACE类

8 3PSPACE完全性

8 3 1TQBF问题

8 3 2博弈的必胜策略

8 3 3广义地理学

8 4L类和NL类

8 5NL完全性

8 6NL等于coNL

练习

问题

习题选解

第9章难解性

9 1层次定理

9 2相对化

9 3电路复杂性

练习

问题

习题选解

第10章复杂性理论高级专题

10 1近似算法

10 2概率算法

10 2 1BPP类

10 2 2素数性

10 2 3只读一次的分支程序

10 3交错式

10 3 1交错式时间与交错式空间

10 3 2多项式时间层次

10 4交互式证明系统

10 4 1图的非同构

10 4 2模型的定义

10 4 3IP=PSPACE

10 5并行计算

10 5 1一致布尔电路

10 5 2NC类

10 5 3P完全性

10 6密码学

10 6 1密钥

10 6 2公钥密码系统

10 6 3单向函数

10 6 4天窗函数

练习

问题

习题选解

参考文献

索引