可计算性、计算复杂性与算法设计思路【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

可计算性、计算复杂性与算法设计思路PDF格式电子书版下载

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

第1章 引论1

1.1 数论函数与数论谓词1

1.2 字符串、语言和文法2

1.2.1 字母表与字符串3

1.2.2 语言4

1.2.3 文法6

1.3 字符串的数值化8

1.3.1 哥德尔配数法8

1.3.2 多项式求值配数法9

1.3.3 字符串处理规约为数论函数计算10

1.3.4 Cantor编号11

1.4 可计算性的提出与计算模型产生的历史背景12

第2章 递归函数和λ-演算16

2.1 原始递归函数16

2.2 μ递归函数和一般递归函数20

2.3 递归谓词与三值逻辑24

2.4 递归可枚举集与递归集26

2.5 λ-演算29

2.5.1 λ-表达式29

2.5.2 λ-演算形式系统29

z.5.3 λ-可定义函数32

第3章 图灵机33

3.1 图灵机的基本概念33

3.2 图灵机用于计算整函数36

3.3 图灵机的构造技巧38

3.3.1 控制器中存储信息38

3.3.2 移位39

3.3.3 读写带分为多道轨线41

3.3.4 子程序41

3.4 变形图灵机42

3.4.1 双向无限带图灵机42

3.4.2 多带图灵机44

3.4.3 不确定的图灵机45

3.4.4 脱线图灵机47

3.5 图灵机同递归函数和Chomsky文法的等价性47

3.5.1 图灵机与递归函数的等价性47

3.5.2 图灵机同Chomsky文法的等价性49

3.6 图灵机作为语言产生器52

3.7 多栈机与计数器55

3.7.1 多栈机55

3.7.2 计数器56

3.8 图灵机带符号集的化简58

第4章 可计算性理论60

4.1 邱奇—图灵论题61

4.2 图灵机编码与通用图灵机63

4.2.1 图灵机编码63

4.2.2 通用语言64

4.2.3 通用图灵机64

4.3 递归语言的性质和非递归可枚举语言的存在性65

4.3.1 递归语言的封闭性质65

4.3.2 非递归可枚举语言的存在性66

4.3.3 Ld——非递归可枚举语言的一个实例67

4.4 图灵机停机问题和递归可枚举语言其他一些问题的不可判定性69

4.4.1 递归可枚举语言成员问题的不可判定性69

4.4.2 图灵机停机问题的不可判定性70

4.4.3 一个递归可枚举语言是否为空集问题的不可判定性70

4.5 Post对应问题及其不可判定性71

4.5.1 Post对应问题71

4.5.2 修改的Post对应问题72

4.5.3 PCP的不可判定性73

4.6 上下文无关文法（语言）歧义性问题的不可判定性75

4.6.1 上下文无关文法的推导树76

4.6.2 上下文无关文法的歧义性80

4.6.3 上下文无关语言的固有歧义性82

4.6.4 上下文无关文法（语言）歧义性问题的不可判定性82

4.7 Oracle计算与不可判定性的分层84

4.7.1 Oracle计算85

4.7.2 不可判定性的分层85

第5章 计算复杂性概论87

5.1 计算的时空复杂性度量87

5.1.1 图灵机的空间界和时间界87

5.1.2 问题的时空复杂性88

5.1.3 不确定的时间和空间复杂性89

5.2 线性加速、带的压缩以及带数量的缩减90

5.2.1 对带格的压缩和带数量的缩减90

5.2.2 线性加速与带的减少对时间界的影响91

5.3 复杂性层次（谱系）定理92

5.3.1 空间复杂性层次92

5.3.2 时间复杂性层次93

5.4 各种复杂性度量之间的关系94

5.4.1 空间与时间复杂性度量之间的关系94

5.4.2 确定的和不确定的时空复杂性度量之间的关系95

第6章 NP—完全问题98

6.1 P类和NP类问题98

6.1.1 P类问题的实例99

6.1.2 NP类问题的实例99

6.2 多项式规约与NP完全问题的基本理论105

6.3 Cook定理106

6.4 其他NP完全问题110

6.5 CO-NP问题与NPI问题112

第7章 算法描述与算法分析115

7.1 算法的定义和特征115

7.2 算法的描述116

7.3 算法分析121

7.4 递归方程求解127

7.4.1 递归公式的展开128

7.4.2 常系数线性齐次递归方程的特征方程求解方法129

7.4.3 常系数线性非齐次递归方程求解131

7.5 生成函数132

第8章 几种典型算法的设计思路137

8.1 分治与递归算法137

8.1.1 二分查找算法138

8.1.2 快速排序算法138

8.1.3 矩阵乘法的Strassen算法139

8.1.4 快速傅里叶变换（FFT）141

8.2 散列与凝聚算法142

8.2.1 散列算法142

8.2.2 凝聚算法144

8.3 贪心算法149

8.3.1 背包问题的贪心算法149

8.3.2 求最小生成树的Kruskal算法150

8.3.3 哈夫曼编码151

8.4 动态规划算法154

8.4.1 多级图问题的动态规划算法155

8.4.2 矩阵连乘的动态规划算法157

8.4.3 0-1背包问题的动态规划算法160

8.5 回溯算法161

8.5.1 n后问题的回溯算法162

8.5.2 0-1背包问题的回溯算法164

8.6 分枝限界算法166

8.6.1 0-1背包问题的分枝限界算法166

8.6.2 旅行商问题的分枝限界法168

第9章 近似算法和概率算法175

9.1 近似算法175

9.1.1 满足三角不等式假设的旅行商问题的近似算法175

9.1.2 装箱问题的近似算法177

9.2 概率算法181

9.2.1 素数判定问题的Miller-Rabin算法181

9.2.2 零知识证明183

参考文献185