计算理论导引-原书第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天窗函数
练习
问题
习题选解
参考文献
索引