計算機算法：分析與設計導論

第1章 引論        1
1.1 算法的基本概念        1
1.2 算法的數(shù)學基礎        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 算法的優(yōu)化與最優(yōu)算法        26
2.3 算法設計中的常用方法        32
2.3.1 分治法        32
2.3.2 回溯法        33
2.3.3 貪心法        34
2.3.4 分支限界法        35
2.3.5 動態(tài)規(guī)劃        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 基數(shù)排序        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 寬度優(yōu)先搜索        81
4.3.2 寬度優(yōu)先樹        83
4.3.3 深度優(yōu)先搜索算法        84
4.3.4 深度優(yōu)先搜索的性質        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 網(wǎng)絡流及其應用        113
4.9.1 網(wǎng)絡流與最大流最小截集定理        114
4.9.2 最大流的算法        116
4.9.3 網(wǎng)絡流的應用        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 并行計算機發(fā)展簡史        151
6.2.2 并行計算機體系結構        153
6.2.3 并行計算機存儲器模型        156
6.2.4 多處理機中高速緩存一致性問題        159
6.3 并行計算機通信機制        162
6.3.1 靜態(tài)網(wǎng)絡        162
6.3.2 動態(tài)網(wǎng)絡        167
6.3.3 并行計算機的消息傳遞方式        170
6.3.4 互連網(wǎng)絡的路由選擇        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 分解判據(jù)        193
7.6 通信設計        193
7.6.1 局部/全局通信        194
7.6.2 結構化/非結構化通信        196
7.6.3 靜態(tài)/動態(tài)通信        196
7.6.4 同步/異步通信        197
7.6.5 通信判據(jù)        197
7.7 任務組合        198
7.7.1 增加粒度        198
7.7.2 保持靈活性和減少軟件工程的代價        200
7.7.3 組合判據(jù)        201
7.8 處理器映射        201
7.8.1 負載均衡算法        202
7.8.2 任務調度算法        204
7.8.3 映射判據(jù)        206
7.9 習題        207
7.10 參考文獻        208
第8章 并行算法效率分析        209
8.1 引言        209
8.2 并行算法的性能指標        209
8.2.1 執(zhí)行時間        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 二維網(wǎng)格機器（SIMD-MC2）上的同步并行求和算法        221
9.2.2 超立方機器（SIMD-CC）上的同步并行求和算法        222
9.2.3 洗牌交換網(wǎng)絡（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 超立方體網(wǎng)絡上的模擬快速排序        235
9.6 比較器網(wǎng)絡上的并行排序        237
9.6.1 比較器網(wǎng)絡        237
9.6.2 奇偶歸并網(wǎng)絡        237
9.6.3 雙調歸并網(wǎng)絡        237
9.6.4 Batcher排序網(wǎng)絡        238
9.7 習題        239
9.8 參考文獻        241
第10章 并行數(shù)值算法        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 數(shù)據(jù)并行機制        276
11.2.3 數(shù)據(jù)映射        276
11.2.4 實例：高斯消去法的HPF程序        277