计算机算法：分析与设计导论

第1章 引论        1
1.1 算法的基本概念        1
1.2 算法的数学基础        4
1.2.1 集合论        4
1.2.2 逻辑学        6
1.2.3 概率论        7
1.2.4 求和与递归        11
1.2.5 快速估算法        16
1.3 算法的效率与复杂度        16
1.4 习题        20
1.5 参考文献        21
第2章 算法设计与分析技术        22
2.1 算法的渐近复杂度        22
2.2 算法的优化与最优算法        26
2.3 算法设计中的常用方法        32
2.3.1 分治法        32
2.3.2 回溯法        33
2.3.3 贪心法        34
2.3.4 分支限界法        35
2.3.5 动态规划        36
2.4 习题        41
2.5 参考文献        42
第3章 排序问题        43
3.1 引言        43
3.2 基于相邻元素之间的比较排序算法        44
3.2.1 插入排序法        44
3.2.2 冒泡排序法        46
3.2.3 选择排序法        49
3.3 基于分治策略的排序算法        50
3.3.1 归并排序法        51
3.3.2 快速排序法        52
3.3.3 谢尔排序法        56
3.4 堆排序        58
3.4.1 堆的性质        58
3.4.2 堆排序算法        59
3.4.3 加速堆排序        63
3.5 基于比较的排序算法复杂度下界        67
3.6 基数排序        69
3.7 习题        72
3.8 参考文献        73
第4章 图的算法        74
4.1 引言        74
4.2 图的概念        74
4.2.1 历史回顾        74
4.2.2 图的基本概念        75
4.2.3 图的表示        76
4.2.4 树与图的生成树        78
4.2.5 独立集、覆盖与控制集        80
4.3 图的搜索问题        81
4.3.1 宽度优先搜索        81
4.3.2 宽度优先树        83
4.3.3 深度优先搜索算法        84
4.3.4 深度优先搜索的性质        86
4.4 拓扑排序        89
4.5 强连通支        91
4.6 最小生成树算法        95
4.6.1 最小生成树的形成        95
4.6.2 Kruskal算法和Prim算法        98
4.7 最短路径算法        102
4.7.1 问题描述        102
4.7.2 松弛技术        103
4.7.3 Bellman-Ford算法        104
4.7.4 Dijkstra算法        107
4.8 欧拉回路与中国邮递员问题        110
4.8.1 欧拉回路        110
4.8.2 中国邮递员问题        111
4.9 网络流及其应用        113
4.9.1 网络流与最大流最小截集定理        114
4.9.2 最大流的算法        116
4.9.3 网络流的应用        117
4.10 习题        121
4.11 参考文献        122
第5章 NP完全性理论        123
5.1 引言        123
5.2 图灵机        124
5.3 判定问题、语言和编码        128
5.4 P类问题、多项式变换和可满足性问题        129
5.5 NP类问题、NP完全问题和NP困难问题        130
5.5.1 NP类        130
5.5.2 NP完全问题和NP困难问题        132
5.6 Cook定理        135
5.7 NP完全性证明        135
5.7.1 直接变换法        136
5.7.2 限制法        138
5.8 P类问题的证明        139
5.9 近似算法        141
5.9.1 装箱问题        141
5.9.2 0/1背包问题        143
5.9.3 旅行商问题        143
5.10 DNA计算        145
5.10.1 DNA背景知识        145
5.10.2 DNA计算哈密顿路径问题        145
5.11 丘奇—图灵论点的启示        148
5.12 习题        149
5.13 参考文献        150
第6章 并行计算基础        151
6.1 引言        151
6.2 并行计算机        151
6.2.1 并行计算机发展简史        151
6.2.2 并行计算机体系结构        153
6.2.3 并行计算机存储器模型        156
6.2.4 多处理机中高速缓存一致性问题        159
6.3 并行计算机通信机制        162
6.3.1 静态网络        162
6.3.2 动态网络        167
6.3.3 并行计算机的消息传递方式        170
6.3.4 互连网络的路由选择        172
6.4 并行计算模型        173
6.4.1 PRAM模型        173
6.4.2 BSP模型        175
6.4.3 LogP模型        177
6.4.4 C3模型        179
6.5 习题        179
6.6 参考文献        182
第7章 并行算法设计技术        184
7.1 引言        184
7.2 并行算法的基本概念        184
7.3 串行算法的并行化        185
7.3.1 设计方法描述        185
7.3.2 快速排序算法的并行化        185
7.4 并行算法的PCAM设计方法        188
7.5 任务分解        189
7.5.1 域分解        189
7.5.2 功能分解        192
7.5.3 分解判据        193
7.6 通信设计        193
7.6.1 局部/全局通信        194
7.6.2 结构化/非结构化通信        196
7.6.3 静态/动态通信        196
7.6.4 同步/异步通信        197
7.6.5 通信判据        197
7.7 任务组合        198
7.7.1 增加粒度        198
7.7.2 保持灵活性和减少软件工程的代价        200
7.7.3 组合判据        201
7.8 处理器映射        201
7.8.1 负载均衡算法        202
7.8.2 任务调度算法        204
7.8.3 映射判据        206
7.9 习题        207
7.10 参考文献        208
第8章 并行算法效率分析        209
8.1 引言        209
8.2 并行算法的性能指标        209
8.2.1 执行时间        209
8.2.2 效率与加速比        211
8.2.3 可扩展性        212
8.2.4 并行度        214
8.3 并行算法性能分析        214
8.3.1 Brent定理        214
8.3.2 阿姆达尔定律        215
8.3.3 古斯塔夫森定理        215
8.3.4 Sun-Ni定理        216
8.4 习题        216
8.5 参考文献        219
第9章 并行求和与排序        220
9.1 引言        220
9.2 基于不同计算模型的并行求和算法        221
9.2.1 二维网格机器（SIMD-MC2）上的同步并行求和算法        221
9.2.2 超立方机器（SIMD-CC）上的同步并行求和算法        222
9.2.3 洗牌交换网络（SIMD-SE）上的同步并行求和算法        224
9.2.4 共享存储器机器（SIMD-SM）上的并行求和算法        226
9.3 基于不同计算模型的并行排序算法        228
9.3.1 SIMD-EREW上的并行排序算法        228
9.3.2 BSP上的并行排序算法        229
9.4 基于功能划分的并行排序算法        230
9.4.1 并行双调排序算法        230
9.4.2 奇偶交换并行排序        231
9.5 并行快速排序算法        233
9.5.1 PRAM-CRCW计算模型上的快速排序算法        233
9.5.2 超立方体网络上的模拟快速排序        235
9.6 比较器网络上的并行排序        237
9.6.1 比较器网络        237
9.6.2 奇偶归并网络        237
9.6.3 双调归并网络        237
9.6.4 Batcher排序网络        238
9.7 习题        239
9.8 参考文献        241
第10章 并行数值算法        243
10.1 矩阵并行计算        243
10.1.1 并行矩阵乘法        243
10.1.2 LU分解        245
10.1.3 QR分解        247
10.1.4 矩阵求逆        251
10.2 线性方程组的解        253
10.2.1 高斯消去法        253
10.2.2 高斯—塞德尔迭代法        257
10.2.3 松弛法        259
10.3 快速傅里叶变换和离散小波变换        259
10.3.1 快速傅里叶变换        260
10.3.2 离散小波变换        262
10.4 习题        266
10.5 参考文献        268
第11章 并行计算工具与并行程序设计语言HPF简介        269
11.1 并行计算工具        269
11.1.1 概述        269
11.1.2 并行程序设计工具PVM        270
11.1.3 并行程序设计工具MPI        272
11.2 HPF并行编程        275
11.2.1 高性能FORTRAN简介        275
11.2.2 数据并行机制        276
11.2.3 数据映射        276
11.2.4 实例：高斯消去法的HPF程序        277