可计算性、计算复杂性与算法设计思路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