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

计算理论导引 原书第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等于coNL222

练习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= PSPACE263

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