目录 1
绪论…………………………………………………………………………………………Ⅸ第1章 动态规划 1
1.1 最短路径问题 1
1.2 最佳原理 3
1.3 流动推销员（或旅行商）问题 11
1.4 矩阵链乘问题 14
1.5 最长公共子序列 16
1.6 图的任意两点间的最短距离 18
1.7 整数规划问题 20
1.8 同顺序流水作业的任务安排问题 25
1.9 可靠性问题 27
1.10 设备更新问题 29
习题 33
第2章 优先策略 36
2.1 最短树的Kruskal算法 36
2.2 求最短树的Prim算法 37
2.3 求最短路径的Dijkstra算法 38
2.4 文件存储问题 39
2.5 有期限的任务安排问题 41
习题 42
3.1 二分查找 45
第3章 分治策略 45
3.2 整数乘法 46
3.3 矩阵乘积的Strassen算法 47
3.4 矩阵乘积的Winograd算法 50
3.5 布尔矩阵的乘法问题 51
习题 53
第4章 Huffman编码、FFT算法和数据压缩 55
4.1 Huffman编码 55
4.2 快速傅里叶变换（FFT） 58
4.3 卷积及其应用 70
4.4 数论变换 72
习题 74
第5章 线性规划的分解原理 76
5.1 线性规划和单纯形法简介 76
5.2 Dantzig-Wolfe分解算法 81
习题 89
第6章 最佳二分树 91
6.1 二分树 91
6.2 最佳二分树 94
习题 100
7.2 分类的下界估计 101
第7章 内存分类法之一：插入分类法、Shell分类法 101
7.1 分类 101
7.3 二分插入分类法 104
7.4 Shell分类法 106
习题 108
第8章 内存分类法之二：递选分类法、堆集分类 111
8.1 递选分类法 111
8.2 二分树递选分类法 112
8.3 堆集分类法 113
习题 117
第9章 内存分类法之三：下溢分类法、快速分类法 118
9.1 下溢分类法 118
9.2 快速分类法 121
习题 125
第10章 内存分类法之四：归并分类法和基数分类法 127
10.1 归并分类法 127
10.2 Ford-Johnson归并插入分类法 129
10.3 基数分类法 133
习题 134
11.1 求最小及第二小元素 135
第11章 求第k个元素 135
11.2 求第k个元素 136
习题 138
第12章 外存分类法 139
12.1 外存归并分类法 139
12.2 置换选择段的构造 141
12.3 三条带的外存归并分类法 143
12.4 阶式归并法 147
习题 148
13.1 分类网络举例 149
第13章 分类网络 149
13.2 0-1原理 150
13.3 归并网络 153
13.4 Batcher奇偶归并网络 154
习题 156
第14章 查找及均衡树 157
14.1 AVL树——关于高度均衡的二分树 157
14.2 关于高度均衡的二分树的插入和删除 161
习题 164
第15章 2-3树和2-3-4树 165
15.1 2-3树 165
15.2 2-3-4树 167
15.3 红黑树 169
习题 170
第16章 B-树 171
16.1 B-树概念 171
16.2 插入和删除 172
习题 175
第17章 哈希表 176
17.1 什么是哈希表 176
17.2 哈希函数的构造方法 176
17.3 解决冲突的方法 177
17.4 哈希算法的分析（线性探测法分析） 180
17.5 二重哈希法 181
习题 182
第18章 DFS算法和BFS算法 184
18.1 概述 184
18.2 DFS算法 185
18.3 无向图的DFS算法 187
18.4 有向图的DFS算法 189
18.5 互连通块问题 192
18.6 强连通块问题 193
18.7 BFS算法 197
习题 . 198
第19章 α-β剪枝术和分支定界法 200
19.1 α-β剪枝术 200
19.2 分支定界法和流动推销员问题 200
19.3 同顺序加工任务安排问题 204
习题 207
第20章 整数规划 208
20.1 概述 208
20.2 0-1规划和它的DFS搜索（隐枚举）解法 210
20.3 分支定界法在解整数规划中的应用 218
习题 220
第21章 串匹配 221
21.1 概述 221
21.2 KMP（Knuth-Morris-Pratt）算法 222
21.3 BM（Boyer-Moore）算法 224
21.4 RK（Rabin-Karp）算法 225
习题 226
第22章 概率算法 228
22.1 概率算法举例 228
22.2 随机数产生法 231
22.3 素数的概率判定算法 232
习题 233
第23章 并行算法 234
23.1 并行计算机和并行算法的基本概念 234
23.2 递推关系的并行计算 237
23.3 图的并行算法举例 238
23.4 矩阵乘积的并行计算 242
23.5 分布计算 244
习题 245
24.1 矩阵和向量乘法的并行处理 246
第24章 脉动阵列的并行处理 246
24.2 矩阵乘法的并行处理 247
24.3 带状矩阵的并行乘法 249
习题 252
第25章 计算几何 253
25.1 关于线段问题 253
25.2 求凸包问题 257
习题 259
第26章 NP完备理论 260
26.1 确定型图灵机 260
26.2 可满足性问题 263
26.3 非确定型图灵机与Cook定理 265
26.4 几个NP完备的例子 269
26.5 复杂度类 277
习题 279
第27章 近似算法 281
27.1 任务安排的近似算法 281
27.2 装箱问题的近似算法 285
27.3 流动推销员问题的近似算法 287
27.4 顶点覆盖问题的近似算法 294
习题 295
28.1 什么是密码？ 297
第28章 密码学简介 297
28.2 背包公钥密码 300
28.3 RSA公钥密码 301
28.4 数字签名 303
28.5 Hash算法 303
习题 304
第29章 LP问题的多项式算法 305
29.1 Klee和Minty举例 305
29.2 Χачцян（哈奇扬）算法 308
29.3 Karmarkar算法 311
习题 321