并行算法導論

出版者的話
專家指導委員會
譯者序
前言
致謝
作者簡介
第一部分 并行計算基礎(chǔ)
第0章 引言 1
0.1 計算機簡介 1
0.2 并行計算機 5
0.3 并行處理的概念 6
0.4 高性能計算機 8
0.5 本書的結(jié)構(gòu)和內(nèi)容 9
參考文獻 10
第1章 并行計算要素 11
1.1 并行的層次 11
1.2 并行計算機分類 12
1.2.1 Flynn分類 12
1.2.2 Erlangen分類（Handler分類） 14
1.2.3 Giloi分類 15
1.2.4 Hwang-Brigg分類 15
1.2.5 Duncan分類 15
1.3 并行計算模型 18
1.3.1 二叉樹模型 18
1.3.2 網(wǎng)絡(luò)模型 20
1.3.3 超立方體（k-立方體） 21
1.3.4 網(wǎng)格網(wǎng)絡(luò) 26
1.3.5 金字塔網(wǎng)絡(luò) 26
1.3.6 星形圖 27
1.4 PRAM模型 28
1.5 一些簡單算法 32
1.6 并行算法的性能 34
1.7 小結(jié) 37
參考文獻 37
習題 38
第2章 并行計算數(shù)據(jù)結(jié)構(gòu) 40
2.1 數(shù)組和列表 40
2.2 鏈接列表 41
2.3 圖與樹 44
2.3.1 預備知識 44
2.3.2 歐拉圖與哈密頓圖 48
2.3.3 樹 49
2.3.4 圖的遍歷 57
2.3.5 連通性 58
2.3.6 可平面圖 62
2.3.7 染色與獨立集 64
2.3.8 團覆蓋 65
2.3.9 交圖 65
2.3.10 弦圖 66
2.3.11 更多的交圖 70
2.3.12 圖的匹配問題 70
2.3.13 圖的中心 71
2.3.14 控制理論 72
2.3.15 圖論中的一些問題 73
參考文獻 74
第3章 并行算法設(shè)計環(huán)境 76
3.1 二叉樹設(shè)計環(huán)境 76
3.2 二倍增長 79
3.3 指針跳轉(zhuǎn) 79
3.4 分而治之 82
3.5 劃分 83
3.6 小結(jié) 86
參考文獻 86
習題 86
第4章 簡單并行算法 88
4.1 向量內(nèi)積 88
4.2 矩陣乘法 88
4.3 部分和 90
4.4 二項式系數(shù) 94
4.5 范圍內(nèi)最小值問題 98
參考文獻 101
習題 101
第二部分 圖模型算法
第5章 樹算法 103
5.1 歐拉圈 103
5.2 給樹加根 104
5.3 后序編號 105
5.4 后代個數(shù) 107
5.5 頂點層數(shù) 107
5.6 最低公共祖先 108
5.7 樹收縮 110
5.8 算術(shù)表達式的計算 114
5.9 森林求根問題 117
5.10 到根的路 119
5.11 樹變?yōu)槎鏄?nbsp;123
5.12 頂點直徑 125
5.13 最遠鄰居 128
參考文獻 130
習題 131
第6章 圖算法 132
6.1 簡單圖算法 132
6.2 并行連通度算法 135
6.2.1 廣度優(yōu)先搜索（BFS） 135
6.2.2 利用BFS搜索連通支 139
6.2.3 傳遞閉包矩陣 141
6.2.4 頂點收縮 141
6.3 2-連通支 145
6.4 支撐樹 146
6.5 最短路問題 148
參考文獻 151
習題 152
第7章 弦圖的NC算法 154
7.1 弦圖判別 154
7.2 弦圖的極大團 161
7.3 CV圖的特征 163
7.4 路圖判別 164
7.4.1 一些概念和事實 164
7.4.2 算法概述 168
7.4.3 兩個UV圖的并 169
7.4.4 正確性和復雜度 175
參考文獻 177
第三部分 數(shù)組處理算法
第8章 搜索與合并 179
8.1 串行搜索 179
8.2 CREW PRAM模型下的并行搜索 180
8.3 更多數(shù)據(jù)的并行搜索 181
8.4 無序數(shù)組搜索 182
8.5 秩合并 182
8.6 雙調(diào)合并 184
參考文獻 187
第9章 排序算法 188
9.1 串行排序算法 188
9.1.1 冒泡排序 188
9.1.2 插入排序 189
9.1.3 Shell遞減步長排序 190
9.1.4 堆排序 191
9.2 合并排序 193
9.3 排序網(wǎng)絡(luò) 194
參考文獻 195
習題 196
第四部分 數(shù)值算法
第10章 代數(shù)方程和矩陣 197
10.1 代數(shù)方程 197
10.1.1 幾何解釋 197
10.1.2 對分法 198
10.2 矩陣的行列式 199
10.3 線性方程組 202
10.3.1 高斯消元法 205
10.3.2 Givens旋轉(zhuǎn) 206
10.4 傅里葉變換 208
10.5 多項式乘法 215
10.6 矩陣求逆 217
10.7 Toeplitz矩陣 219
10.8 三對角方程組 222
10.8.1 高斯消元法 222
10.8.2 奇偶約化法 223
參考文獻 226
習題 227
第11章 微分與積分 228
11.1 微分 228
11.2 偏微分 229
11.3 定積分 233
11.4 插值 235
11.4.1 線性插值 235
11.4.2 二次插值 236
11.4.3 拉格朗日插值 236
參考文獻 237
習題 238
第12章 微分方程 239
12.1 歐拉公式 239
12.2 偏微分方程 239
12.3 拋物方程 240
12.3.1 施密特法（求解拋物方程） 242
12.3.2 Laasonen法（求解拋物方程） 246
12.3.3 Crank Nickolson法 248
12.3.4 三層差分法 249
參考文獻 251
部分習題解答 252
索引 258