計(jì)算機(jī)算法：分析與設(shè)計(jì)導(dǎo)論

第1章 引論        1
1.1 算法的基本概念        1
1.2 算法的數(shù)學(xué)基礎(chǔ)        4
1.2.1 集合論        4
1.2.2 邏輯學(xué)        6
1.2.3 概率論        7
1.2.4 求和與遞歸        11
1.2.5 快速估算法        16
1.3 算法的效率與復(fù)雜度        16
1.4 習(xí)題        20
1.5 參考文獻(xiàn)        21
第2章 算法設(shè)計(jì)與分析技術(shù)        22
2.1 算法的漸近復(fù)雜度        22
2.2 算法的優(yōu)化與最優(yōu)算法        26
2.3 算法設(shè)計(jì)中的常用方法        32
2.3.1 分治法        32
2.3.2 回溯法        33
2.3.3 貪心法        34
2.3.4 分支限界法        35
2.3.5 動(dòng)態(tài)規(guī)劃        36
2.4 習(xí)題        41
2.5 參考文獻(xiàn)        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 堆的性質(zhì)        58
3.4.2 堆排序算法        59
3.4.3 加速堆排序        63
3.5 基于比較的排序算法復(fù)雜度下界        67
3.6 基數(shù)排序        69
3.7 習(xí)題        72
3.8 參考文獻(xiàn)        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 獨(dú)立集、覆蓋與控制集        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)先搜索的性質(zhì)        86
4.4 拓?fù)渑判?nbsp;       89
4.5 強(qiáng)連通支        91
4.6 最小生成樹算法        95
4.6.1 最小生成樹的形成        95
4.6.2 Kruskal算法和Prim算法        98
4.7 最短路徑算法        102
4.7.1 問題描述        102
4.7.2 松弛技術(shù)        103
4.7.3 Bellman-Ford算法        104
4.7.4 Dijkstra算法        107
4.8 歐拉回路與中國(guó)郵遞員問題        110
4.8.1 歐拉回路        110
4.8.2 中國(guó)郵遞員問題        111
4.9 網(wǎng)絡(luò)流及其應(yīng)用        113
4.9.1 網(wǎng)絡(luò)流與最大流最小截集定理        114
4.9.2 最大流的算法        116
4.9.3 網(wǎng)絡(luò)流的應(yīng)用        117
4.10 習(xí)題        121
4.11 參考文獻(xiàn)        122
第5章 NP完全性理論        123
5.1 引言        123
5.2 圖靈機(jī)        124
5.3 判定問題、語(yǔ)言和編碼        128
5.4 P類問題、多項(xiàng)式變換和可滿足性問題        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計(jì)算        145
5.10.1 DNA背景知識(shí)        145
5.10.2 DNA計(jì)算哈密頓路徑問題        145
5.11 丘奇—圖靈論點(diǎn)的啟示        148
5.12 習(xí)題        149
5.13 參考文獻(xiàn)        150
第6章 并行計(jì)算基礎(chǔ)        151
6.1 引言        151
6.2 并行計(jì)算機(jī)        151
6.2.1 并行計(jì)算機(jī)發(fā)展簡(jiǎn)史        151
6.2.2 并行計(jì)算機(jī)體系結(jié)構(gòu)        153
6.2.3 并行計(jì)算機(jī)存儲(chǔ)器模型        156
6.2.4 多處理機(jī)中高速緩存一致性問題        159
6.3 并行計(jì)算機(jī)通信機(jī)制        162
6.3.1 靜態(tài)網(wǎng)絡(luò)        162
6.3.2 動(dòng)態(tài)網(wǎng)絡(luò)        167
6.3.3 并行計(jì)算機(jī)的消息傳遞方式        170
6.3.4 互連網(wǎng)絡(luò)的路由選擇        172
6.4 并行計(jì)算模型        173
6.4.1 PRAM模型        173
6.4.2 BSP模型        175
6.4.3 LogP模型        177
6.4.4 C3模型        179
6.5 習(xí)題        179
6.6 參考文獻(xiàn)        182
第7章 并行算法設(shè)計(jì)技術(shù)        184
7.1 引言        184
7.2 并行算法的基本概念        184
7.3 串行算法的并行化        185
7.3.1 設(shè)計(jì)方法描述        185
7.3.2 快速排序算法的并行化        185
7.4 并行算法的PCAM設(shè)計(jì)方法        188
7.5 任務(wù)分解        189
7.5.1 域分解        189
7.5.2 功能分解        192
7.5.3 分解判據(jù)        193
7.6 通信設(shè)計(jì)        193
7.6.1 局部/全局通信        194
7.6.2 結(jié)構(gòu)化/非結(jié)構(gòu)化通信        196
7.6.3 靜態(tài)/動(dòng)態(tài)通信        196
7.6.4 同步/異步通信        197
7.6.5 通信判據(jù)        197
7.7 任務(wù)組合        198
7.7.1 增加粒度        198
7.7.2 保持靈活性和減少軟件工程的代價(jià)        200
7.7.3 組合判據(jù)        201
7.8 處理器映射        201
7.8.1 負(fù)載均衡算法        202
7.8.2 任務(wù)調(diào)度算法        204
7.8.3 映射判據(jù)        206
7.9 習(xí)題        207
7.10 參考文獻(xiàn)        208
第8章 并行算法效率分析        209
8.1 引言        209
8.2 并行算法的性能指標(biāo)        209
8.2.1 執(zhí)行時(shí)間        209
8.2.2 效率與加速比        211
8.2.3 可擴(kuò)展性        212
8.2.4 并行度        214
8.3 并行算法性能分析        214
8.3.1 Brent定理        214
8.3.2 阿姆達(dá)爾定律        215
8.3.3 古斯塔夫森定理        215
8.3.4 Sun-Ni定理        216
8.4 習(xí)題        216
8.5 參考文獻(xiàn)        219
第9章 并行求和與排序        220
9.1 引言        220
9.2 基于不同計(jì)算模型的并行求和算法        221
9.2.1 二維網(wǎng)格機(jī)器（SIMD-MC2）上的同步并行求和算法        221
9.2.2 超立方機(jī)器（SIMD-CC）上的同步并行求和算法        222
9.2.3 洗牌交換網(wǎng)絡(luò)（SIMD-SE）上的同步并行求和算法        224
9.2.4 共享存儲(chǔ)器機(jī)器（SIMD-SM）上的并行求和算法        226
9.3 基于不同計(jì)算模型的并行排序算法        228
9.3.1 SIMD-EREW上的并行排序算法        228
9.3.2 BSP上的并行排序算法        229
9.4 基于功能劃分的并行排序算法        230
9.4.1 并行雙調(diào)排序算法        230
9.4.2 奇偶交換并行排序        231
9.5 并行快速排序算法        233
9.5.1 PRAM-CRCW計(jì)算模型上的快速排序算法        233
9.5.2 超立方體網(wǎng)絡(luò)上的模擬快速排序        235
9.6 比較器網(wǎng)絡(luò)上的并行排序        237
9.6.1 比較器網(wǎng)絡(luò)        237
9.6.2 奇偶?xì)w并網(wǎng)絡(luò)        237
9.6.3 雙調(diào)歸并網(wǎng)絡(luò)        237
9.6.4 Batcher排序網(wǎng)絡(luò)        238
9.7 習(xí)題        239
9.8 參考文獻(xiàn)        241
第10章 并行數(shù)值算法        243
10.1 矩陣并行計(jì)算        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 習(xí)題        266
10.5 參考文獻(xiàn)        268
第11章 并行計(jì)算工具與并行程序設(shè)計(jì)語(yǔ)言HPF簡(jiǎn)介        269
11.1 并行計(jì)算工具        269
11.1.1 概述        269
11.1.2 并行程序設(shè)計(jì)工具PVM        270
11.1.3 并行程序設(shè)計(jì)工具M(jìn)PI        272
11.2 HPF并行編程        275
11.2.1 高性能FORTRAN簡(jiǎn)介        275
11.2.2 數(shù)據(jù)并行機(jī)制        276
11.2.3 數(shù)據(jù)映射        276
11.2.4 實(shí)例：高斯消去法的HPF程序        277