计算理论导引 原书第3版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序列和多元组 4

0.2.3函数和关系 4

0.2.4图 6

0.2.5字符串和语言 8

0.2.6布尔逻辑 9

0.2.7数学名词汇总 10

0.3定义、定理和证明 11

0.4证明的类型 13

0.4.1构造性证明 13

0.4.2反证法 14

0.4.3归纳法 15

练习 16

问题 17

习题选解 18

第一部分 自动机与语言 20

第1章 正则语言 20

1.1有穷自动机 20

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

1.1.2有穷自动机举例 23

1.1.3计算的形式化定义 25

1.1.4设计有穷自动机 25

1.1.5正则运算 27

1.2非确定性 29

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

1.2.2 NFA与DFA的等价性 33

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

1.3正则表达式 38

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

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

1.4非正则语言 46

练习 50

问题 54

习题选解 58

第2章 上下文无关文法 62

2.1上下文无关文法概述 62

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

2.1.2上下文无关文法举例 64

2.1.3设计上下文无关文法 65

2.1.4歧义性 66

2.1.5乔姆斯基范式 67

2.2下推自动机 68

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

2.2.2下推自动机举例 70

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

2.3非上下文无关语言 77

2.4确定型上下文无关语言 79

2.4.1 DCFL的性质 82

2.4.2确定型上下文无关文法 83

2.4.3 DPDA和DCFG的关系 91

2.4.4语法分析和LR（k）文法 94

练习 96

问题 98

习题选解 100

第二部分 可计算性理论 104

第3章 丘奇-图灵论题 104

3.1图灵机 104

3.1.1图灵机的形式化定义 105

3.1.2图灵机的例子 107

3.2图灵机的变形 110

3.2.1多带图灵机 111

3.2.2非确定型图灵机 112

3.2.3枚举器 113

3.2.4与其他模型的等价性 114

3.3算法的定义 114

3.3.1希尔伯特问题 115

3.3.2描述图灵机的术语 116

练习 118

问题 119

习题选解 120

第4章 可判定性 122

4.1可判定语言 122

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

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

4.2不可判定性 126

4.2.1对角化方法 127

4.2.2不可判定语言 130

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

练习 132

问题 133

习题选解 134

第5章 可归约性 136

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

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

5.3映射可归约性 148

5.3.1可计算函数 148

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

练习 151

问题 151

习题选解 153

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

6.1递归定理 155

6.1.1自引用 155

6.1.2递归定理的术语 157

6.1.3应用 158

6.2逻辑理论的可判定性 159

6.2.1一个可判定的理论 161

6.2.2一个不可判定的理论 163

6.3图灵可归约性 164

6.4信息的定义 165

6.4.1极小长度的描述 166

6.4.2定义的优化 168

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

练习 170

问题 170

习题选解 171

第三部分 复杂性理论 174

第7章 时间复杂性 174

7.1度量复杂性 174

7.1.1大O和小o记法 174

7.1.2分析算法 176

7.1.3模型间的复杂性关系 178

7.2 P类 180

7.2.1多项式时间 180

7.2.2 P中的问题举例 181

7.3 NP类 184

7.3.1 NP中的问题举例 187

7.3.2 P与NP问题 188

7.4 NP完全性 188

7.4.1多项式时间可归约性 189

7.4.2 NP完全性的定义 191

7.4.3库克-列文定理 192

7.5几个NP完全问题 196

7.5.1顶点覆盖问题 196

7.5.2哈密顿路径问题 198

7.5.3子集和问题 201

练习 202

问题 203

习题选解 207

第8章 空间复杂性 208

8.1萨维奇定理 209

8.2 PSPACE类 210

8.3 PSPACE完全性 211

8.3.1 TQBF问题 212

8.3.2博弈的必胜策略 214

8.3.3广义地理学 215

8.4 L类和NL类 219

8.5 N L完全性 220

8.6 NL等于coNL 222

练习 224

问题 224

习题选解 226

第9章 难解性 228

9.1层次定理 228

9.2相对化 236

9.3电路复杂性 238

练习 244

问题 245

习题选解 245

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

10.1近似算法 247

10.2概率算法 248

10.2.1 BPP类 249

10.2.2素数性 250

10.2.3只读一次的分支程序 254

10.3交错式 257

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

10.3.2多项式时间层次 260

10.4交互式证明系统 260

10.4.1图的非同构 261

10.4.2模型的定义 261

10.4.3 IP= PSPACE 263

10.5并行计算 270

10.5.1一致布尔电路 270

10.5.2 NC类 272

10.5.3 P完全性 273

10.6密码学 273

10.6.1密钥 274

10.6.2公钥密码系统 275

10.6.3单向函数 275

10.6.4天窗函数 277

练习 277

问题 278

习题选解 278

参考文献 280

索引 284