并行算法導論

定　價：￥35.00

作　者：	（印）C.Xavier，（美）S.S.Iyengar著；張云泉，陳英譯；張云泉譯
出版社：	機械工業(yè)出版社
叢編項：	計算機科學叢書
標　簽：	并行計算

購買這本書可以去

ISBN：	9787111133902	出版時間：	2004-02-01	包裝：	簡裝本
開本：	26cm	頁數：	263	字數：

內容簡介

　　并行計算的廣泛采用和現今應用問題的日趨復雜，使得并行算法的設計和分析日益引起人們的興趣。這本書滿足了并行算法的入門者，特別是計算機科學、數學和工程專業(yè)的大學生的需求。本書系統(tǒng)地講述最新的設計技術，并對所描述的每一個算法提供分析和詳細的實現細節(jié)。它的主要內容包括并行計算的基礎，樹和圖的并行算法，排序、搜索和合并的并行算法以及數值算法等。本書的特色在于： ●用清晰簡單的術語講述基本的概念 ●提供大量的例子加強學生的理解 ●展示怎樣為計算機科學、數學和工程的典型問題開發(fā)并行算法 ●對新的設計技術作擴展性的闡述 ●在PRAM模型環(huán)境中討論并行算法 ●在章節(jié)后面附有大量的習題和關于并行計算的參考文獻本書對并行算法作了入門級的介紹，用四部分講解并行算法的設計過程和最新的設計方法，并對書中所描述的每一個算法提供分析和詳細的實現細節(jié)。全書包括并行計算的基礎，樹和圖的并行算法，排序、搜索和合并的并行算法及數值算法等內容。其中重點強調了圖模型算法。在章節(jié)后面附有大量的習題和關于并行計算的參考文獻。本書可以作為大學計算機科學與工程專業(yè)高年級學生的并行算法課教材。對于計算機科學、數學和工程領域的研究生、科研工作者和工程師，也是一本不可多得的參考書。

作者簡介

　　C.Xavier執(zhí)教于印度Palayamkottai圣Xavier學院的計算機科學系。他在并行算法領域已經發(fā)表了大量的論文，并出版了十多部計算機機科學教材。張云泉，男，1995年獲北京理工大學計算機科學技術系計算機應用專業(yè)工學學士學位；2000年獲中科院軟件所計算機軟件與理論專業(yè)工學博士學位（碩、博連續(xù)）?，F為中科院軟件所并行計算實驗室副研究員，中科院計算機科學開放重點實驗兼職副研究員，中科院軟件所并行計算實際室副主任，中國軟件行業(yè)協(xié)會數學軟件分會秘書長。

圖書目錄

出版者的話
專家指導委員會
譯者序
前言
致謝
作者簡介
第一部分并行計算基礎
第0章引言 1
0.1 計算機簡介 1
0.2 并行計算機 5
0.3 并行處理的概念 6
0.4 高性能計算機 8
0.5 本書的結構和內容 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 網絡模型 20
1.3.3 超立方體（k-立方體） 21
1.3.4 網格網絡 26
1.3.5 金字塔網絡 26
1.3.6 星形圖 27
1.4 PRAM模型 28
1.5 一些簡單算法 32
1.6 并行算法的性能 34
1.7 小結 37
參考文獻 37
習題 38
第2章并行計算數據結構 40
2.1 數組和列表 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章并行算法設計環(huán)境 76
3.1 二叉樹設計環(huán)境 76
3.2 二倍增長 79
3.3 指針跳轉 79
3.4 分而治之 82
3.5 劃分 83
3.6 小結 86
參考文獻 86
習題 86
第4章簡單并行算法 88
4.1 向量內積 88
4.2 矩陣乘法 88
4.3 部分和 90
4.4 二項式系數 94
4.5 范圍內最小值問題 98
參考文獻 101
習題 101
第二部分圖模型算法
第5章樹算法 103
5.1 歐拉圈 103
5.2 給樹加根 104
5.3 后序編號 105
5.4 后代個數 107
5.5 頂點層數 107
5.6 最低公共祖先 108
5.7 樹收縮 110
5.8 算術表達式的計算 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
第三部分數組處理算法
第8章搜索與合并 179
8.1 串行搜索 179
8.2 CREW PRAM模型下的并行搜索 180
8.3 更多數據的并行搜索 181
8.4 無序數組搜索 182
8.5 秩合并 182
8.6 雙調合并 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 排序網絡 194
參考文獻 195
習題 196
第四部分數值算法
第10章代數方程和矩陣 197
10.1 代數方程 197
10.1.1 幾何解釋 197
10.1.2 對分法 198
10.2 矩陣的行列式 199
10.3 線性方程組 202
10.3.1 高斯消元法 205
10.3.2 Givens旋轉 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