本书由计算理论领域的知名权威MichaelSipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。
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天窗函数
练习
问题
习题选解
参考文献
索引
书单推荐
