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

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

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

第0章 绪论1

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

0.1.1 计算复杂性理论1

0.1.2 可计算性理论2

0.1.3 自动机理论2

0.2 数学概念和术语2

0.2.1 集合2

0.2.2 序列和多元组3

0.2.3 函数和关系4

0.2.4 图6

0.2.5 字符串和语言7

0.2.6 布尔逻辑8

0.2.7 数学名词汇总9

0.3 定义、定理和证明10

0.4 证明的类型12

0.4.1 构造性证明12

0.4.2 反证法13

0.4.3 归纳法13

练习15

问题16

习题选解17

第一部分 自动机与语言19

第1章 正则语言19

1.1 有穷自动机19

1.1.1 有穷自动机的形式化定义21

1.1.2 有穷自动机举例22

1.1.3 计算的形式化定义24

1.1.4 设计有穷自动机24

1.1.5 正则运算26

1.2 非确定性28

1.2.1 非确定型有穷自动机的形式化定义31

1.2.2 NFA与DFA的等价性32

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

1.3 正则表达式37

1.3.1 正则表达式的形式化定义38

1.3.2 与有穷自动机的等价性39

1.4 非正则语言46

练习50

问题54

习题选解58

第2章 上下文无关文法63

2.1 上下文无关文法概述63

2.1.1 上下文无关文法的形式化定义64

2.1.2 上下文无关文法举例65

2.1.3 设计上下文无关文法65

2.1.4 歧义性66

2.1.5 乔姆斯基范式67

2.2 下推自动机69

2.2.1 下推自动机的形式化定义70

2.2.2 下推自动机举例70

2.2.3 与上下文无关文法的等价性72

2.3 非上下文无关语言76

练习79

问题81

习题选解83

第二部分 可计算性理论87

第3章 丘奇-图灵论题87

3.1 图灵机87

3.1.1 图灵机的形式化定义88

3.1.2 图灵机的例子89

3.2 图灵机的变形93

3.2.1 多带图灵机93

3.2.2 非确定型图灵机94

3.2.3 枚举器95

3.2.4 与其他模型的等价性96

3.3 算法的定义97

3.3.1 希尔伯特问题97

3.3.2 描述图灵机的术语98

练习100

问题101

习题选解102

第4章 可判定性104

4.1 可判定语言104

4.1.1 与正则语言相关的可判定性问题104

4.1.2 与上下文无关语言相关的可判定性问题106

4.2 停机问题108

4.2.1 对角化方法109

4.2.2 停机问题是不可判定的111

4.2.3 一个图灵不可识别语言113

练习114

问题115

习题选解116

第5章 可归约性118

5.1 语言理论中的不可判定问题118

5.2 一个简单的不可判定问题124

5.3 映射可归约性129

5.3.1 可计算函数129

5.3.2 映射可归约性的形式定义129

练习132

问题132

习题选解134

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

6.1 递归定理136

6.1.1 自引用136

6.1.2 递归定理的术语138

6.1.3 应用139

6.2 逻辑理论的可判定性140

6.2.1 一个可判定的理论141

6.2.2 一个不可判定的理论143

6.3 图灵可归约性145

6.4 信息的定义146

6.4.1 极小长度的描述146

6.4.2 定义的优化148

6.4.3 不可压缩的串和随机性148

练习150

问题150

习题选解151

第三部分 复杂性理论153

第7章 时间复杂性153

7.1 度量复杂性153

7.1.1 大O和小o记法153

7.1.2 分析算法155

7.1.3 模型间的复杂性关系157

7.2 P类158

7.2.1 多项式时间158

7.2.2 P中的问题举例159

7.3 NP类163

7.3.1 NP中的问题举例165

7.3.2 P与NP问题166

7.4 NP完全性166

7.4.1 多项式时间可归约性167

7.4.2 NP完全性的定义169

7.4.3 库克-列文定理169

7.5 几个NP完全问题173

7.5.1 顶点覆盖问题174

7.5.2 哈密顿路径问题175

7.5.3 子集和问题178

练习180

问题181

习题选解185

第8章 空间复杂性187

8.1 萨维奇定理188

8.2 PSPACE类189

8.3 PSPACE完全性190

8.3.1 TQBF问题190

8.3.2 博弈的必胜策略193

8.3.3 广义地理学194

8.4 L类和NL类197

8.5 NL完全性198

8.6 NL等于coNL200

练习202

问题202

习题选解204

第9章 难解性206

9.1 层次定理206

9.2 相对化213

9.3 电路复杂性215

练习220

问题221

习题选解222

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

10.1 近似算法223

10.2 概率算法224

10.2.1 BPP类224

10.2.2 素数性226

10.2.3 只读一次的分支程序229

10.3 交错式232

10.3.1 交错式时间与交错式空间233

10.3.2 多项式时间层次235

10.4 交互式证明系统236

10.4.1 图的非同构236

10.4.2 模型的定义237

10.4.3 IP=PSPACE238

10.5 并行计算244

10.5.1 一致布尔电路245

10.5.2 NC类246

10.5.3 P完全性247

10.6 密码学247

10.6.1 密钥248

10.6.2 公钥密码系统249

10.6.3 单向函数249

10.6.4 天窗函数250

练习251

问题251

习题选解252

参考文献254

索引259