计算理论基础PDF|Epub|txt|kindle电子书版本网盘下载

计算理论基础PDF格式电子书版下载

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

第1章 数学基础1

1.1 引言1

1.2 集合1

1.3 关系与图3

1.4 函数与计数7

1.5 证明技巧14

1.6 本章总结与习题22

本章习题22

第2章 正则语言26

2.1 引言26

2.2 语言基础26

本节习题29

2.3 正则表达式31

本节习题32

2.4 正则语法34

本节习题37

2.5 确定性有限自动机（DFA）38

本节习题46

2.6 非确定性有限自动机（NFA）47

本节习题52

2.7 本章总结与附加思考题54

附加思考题54

第3章 等价58

3.1 引言58

3.2 NFA到DFA58

本节习题63

3.3 有限自动机与正则语法64

本节习题65

3.4 正则表达式到NFA66

本节习题68

3.5 NFA到正则表达式69

本节习题73

3.6 本章总结与附加思考题75

附加思考题76

第4章 正则语言的结构78

4.1 引言78

4.2 闭包性质78

本节习题81

4.3 非正则语言82

本节习题86

4.4 米歇尔-尼罗德定理88

本节习题92

4.5 状态最小化92

本节习题98

4.6 本章总结与附加思考题99

附加思考题100

第5章 上下文无关语言105

5.1 引言105

5.2 上下文无关语法105

本节习题108

5.3 分析树110

本节习题114

5.4 歧义114

本节习题117

5.5 消除／删除不良生成式118

本节习题121

5.6 范式122

本节习题128

5.7 本章总结与附加思考题129

附加思考题129

第6章 上下文无关语言的结构132

6.1 引言132

6.2 叠加自动机132

本节习题138

6.3 上下文无关语法与叠加自动机140

本节习题144

6.4 泵作用引理145

本节习题150

6.5 上下文无关语言的闭包性质151

本节习题153

6.6 确定型叠加自动机154

本节习题158

6.7 本章总结与附加思考题159

附加思考题159

第7章 可计算枚举语言167

7.1 引言167

7.2 非限制性语法167

本节习题169

7.3 图灵机170

本节习题174

7.4 接受与拒绝174

本节习题179

7.5 使用旧自动机180

本节习题187

7.6 多带图灵机188

本节习题191

7.7 非确定性图灵机和语法192

本节习题197

7.8 本章总结与附加思考题198

附加思考题198

第8章 非可计算枚举语言201

8.1 引言201

8.2 作为计算器的图灵机201

本节习题204

8.3 作为语言判定的图灵机205

本节习题209

8.4 存在多少图灵机210

本节习题213

8.5 接受问题213

本节习题217

8.6 乔姆斯基层次结构217

本节习题219

8.7 总结和附加问题222

本节习题222

第9章 算法可解性229

9.1 引言229

9.2 问题归约230

本节习题232

9.3 赖斯定理234

本节习题236

9.4 关于有限自动机238

本节习题239

9.5 关于叠加自动机240

本节习题244

9.6 关于波斯特对应问题245

本节习题249

9.7 关于逻辑理论250

本节习题255

9.8 其他有趣的问题255

本节习题257

9.9 总结和附加问题258

本节习题259

第10章 计算复杂性267

10.1 引言267

10.2 函数增长率268

本节习题271

10.3 复杂性类别272

本节习题275

10.4 空间复杂性276

本节习题278

10.5 时间复杂性279

本节习题283

10.6 NP类284

本节习题286

10.7 NP完整性287

本节习题291

10.8 某些NP完整问题291

本节习题298

10.9 解决NP完整问题300

本节习题303

10.10 本章总结与附加思考题303

附加思考题304

部分习题答案与提示313

参考文献334