计算理论导引2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

计算理论导引PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

译者序1

前言1

第1章 导引1

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

1.1.1 计算复杂性理论1

1.1.2 可计算性理论2

1.1.3 自动机理论2

1.2 数学概念和术语2

1.2.1 集合2

1.2.2 序列和多元组3

1.2.3 函数和关系4

1.2.4 图6

1.2.5 字符串和语言8

1.2.6 布尔逻辑8

1.2.7 数学名词汇总9

1.3 定义、定理和证明10

1.4 证明和类型13

1.4.1 构造性证明13

1.4.2 反证法13

1.4.3 归纳法14

练习16

问题17

第一部分 自动机与语言19

第2章 正则语言19

2.1 有穷自动机19

2.1.1 有穷自动机的形式定义21

2.1.2 有穷自动机举例22

2.1.3 计算的形式定义24

2.1.4 设计有穷自动机24

2.1.5 正则运算26

2.2 非确定性28

2.2.1 非确定型有穷自动机的形式定义32

2.2.2 NFA与DFA的等价性33

2.2.3 在正则运算下的封闭性35

2.3 正则表达式38

2.3.1 正则表达式的形式定义39

2.3.2 与有穷自动机的等价性40

2.4 非正则语言47

练习51

问题55

3.1 上下文无关文法59

第3章 上下文无关语言59

3.1.1 上下文无关文法的形式定义61

3.1.2 上下文无关文法举例61

3.1.3 设计上下文无关文法62

3.1.4 歧义性63

3.1.5 乔姆斯基范式64

3.2 下推自动机66

3.2.1 下推自动机的形式定义67

3.2.2 下推自动机举例67

3.2.3 与上下文无关文法的等价性69

3.3 非上下文无关语言74

练习77

问题79

第二部分 可计算性理论81

第4章 丘奇--图灵论题81

4.1 图灵机81

4.1.1 图灵机的形式定义82

4.1.2 图灵机的例子84

4.2 图灵机的变形88

4.2.1 多带图灵机88

4.2.2 非确定型图灵机89

4.2.3 枚举器91

4.3 算法的定义92

4.3.1 希尔伯特问题92

4.2.4 与其他模型的等价性92

4.3.2 描述图灵机的术语94

练习96

问题97

第5章 可判定性99

5.1 可判定语言99

5.1.1 与正则语言相关的可判定性问题99

5.1.2 与上下文无关语言相关的可判定问题101

5.2.1 对角化方法104

5.2 停机问题104

5.2.2 停机问题是不可判定的107

5.2.3 一个图灵不可识别语言109

练习110

问题111

第6章 可归约性112

6.1 语言理论中的不可判定问题112

6.2 一个简单的不可判定问题119

6.3 映射可归约性123

6.3.2 映射可归约性的形式定义124

6.3.1 可计算函数124

练习127

问题127

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

7.1 递归定理129

7.1.1 自引用129

7.1.2 应用递归定理的术语131

7.1.3 应用132

7.2 逻辑理论的可判定性133

7.2.1 一个可判定的理论135

7.2.2 一个不可判定的理论137

7.3 图灵可归约性138

7.4 信息的定义139

7.4.1 极小长度的描述140

7.4.2 定义的优化142

7.4.3 不可压缩的串和随机性142

练习144

问题144

8.1 度量复杂性147

8.1.1 大O和小o记法147

第8章 时间复杂性147

第三部分 复杂性理论147

8.1.2 分析算法149

8.1.3 模型间的复杂性关系151

8.2 P类153

8.2.1 多项式时间153

8.2.2 P中的问题举例154

8.3 NP类157

8.3.1 NP中的问题举例160

8.4 NP完全性161

8.3.2 P与NP问题161

8.4.1 多项式时间可归约性162

8.4.2 NP完全性的定义164

8.4.3 库克--列文定理165

8.5 几个NP完全问题169

8.5.1 顶点覆盖问题169

8.5.2 哈密顿路径问题170

8.5.3 子集和问题174

练习176

问题177

第9章 空间复杂性181

9.1 萨维奇定理182

9.2 PSPACE类183

9.3 PSPACE完全性184

9.3.1 问题TQBF185

9.3.2 博奕的必胜策略187

9.3.3 广义地理学188

9.4 L类和NL类192

9.5 NL完全性193

9.6 NL等于coNL195

练习197

问题197

10.1 层次定理200

第10章 难解性200

10.2 相对化208

10.3 电路复杂性211

练习216

问题217

第11章 复杂性理论中的高级专题219

11.1 近似算法219

11.2 概率算法220

11.2.1 BPP类220

11.2.2 素数性223

11.2.3 只读一次的分支程序226

11.3 交错式229

11.3.1 交错式时间与交错式空间229

11.3.2 多项式时间层次232

11.4 交互式证明系统232

11.4.1 图的非同构233

11.4.2 模型的定义233

11.4.3 IP=PSPACE234

11.5 并行计算242

11.5.1 一致布尔电路242

11.5.2 NC类243

11.5.3 P完全性245

11.6 密码学245

11.6.1 密钥245

11.6.2 公钥密码系统247

11.6.3 单向函数247

11.6.4 天窗函数248

练习249

问题249

参考文献251

索引255