并行算法的設計與分析（修訂版）

第一章 并行算法基礎
1.1 并行算法的硬件基礎
1.2 并行計算模型
*1.3 并行算法編程模型
1.4 并行算法的一般概念
習題
參考文獻
第二章 并行算法的基本設計技術
2.1 平衡樹方法
2.2 倍增技術
2.3 分治策略
2.4 劃分原理
2.5 流水線技術
*2.6 加速級聯(lián)策略
2.7 破對稱技術
習題
參考文獻
第三章 比較器網絡上的排序和選擇算法
3.1 Batcher歸并和排序網絡
3.2 （m,n）-選擇網絡
*3.3 AKS排序網絡
習題
參考文獻
第四章 排序和選擇的同步算法
4.1 Stone雙調排序算法
4.2 Thompson和Kung雙調排序算法
*4.3 Preparata和Vuilemin雙調排序算法
4.4 Akl并行k-選擇算法
4.5 Valiant并行歸并算法
*4.6 Hirschberg并行桶排序算法
4.7 Preparata并行枚舉排序算法
*4.8 Cole并行歸并排序算法
習題
參考文獻
第五章 排序和選擇的異步和分布式算法
5.1 MIMD-CREW模型上的異步枚舉排序算法
5.2 MIMD-TC模型上的異步快排序算法
5.3 分布式k-選擇算法
5.4 分布式求中值算法
*5.5 分布式定序算法
*5.6 分布式排序算法
習題
參考文獻
第六章 并行搜索
6.1 單處理機上的搜索
6.2 SIMD共享存儲模型上有序表的搜索
6.3 SIMD共享存儲模型上隨機序列的搜索
6.4 樹連接的SIMD模型上隨機序列的搜索
6.5 網孔連接的SIMD模型上隨機序列的搜索
6.6 MIMD共享存儲模型上有序表的搜索
習題
參考文獻
*第七章 排列和組合
7.1 產生排列的順序算法
7.2 產生組合的順序算法
7.3 產生排列的并行算法
7.4 產生組合的并行算法
習題
參考文獻
第八章 數(shù)據(jù)傳輸與選路
8.1 引言
8.2 貪心選路算法
8.3 隨機和確定選路算法
8.4 數(shù)據(jù)的分布和集中
8.5 線路交換模式下的選路算法
習題
參考文獻
第九章 并行串匹配
9.1 引言
9.2 正文分析
9.3 模式預處理
*9.4 后綴樹上的串匹配
習題
參考文獻
*第十章 表達式求值
10.1 構造表達式樹
10.2 填充游戲用于表達式求值
10.3 最優(yōu)的并行表達式求值算法
10.4 一般表達式求值算法
10.5 正則表達式到非確定自動機的最優(yōu)并行轉換
習題
參考文獻
*第十一章 上下文無關語言的并行識雖與語法分析
11.1 一般的上下文無關語言的并行識別
11.2 一般上下文無關語言的并行語法分析
11.3 括號語言的最優(yōu)并行識別和語法分析
習題
參考文獻
第十二章 矩陣運算
12.1 矩陣轉置
12.2 矩陣相乘
12.3 矩陣和向量相乘
12.4 心動陣列上的矩陣運算
習題
參考文獻
第十三章 數(shù)值計算
13.1 n階線性代數(shù)方程組的求解
*13.2 非線性方程的求根
13.3 偏微分議程的求解
13.4 方陣的特征值與特征向量Jacobi求法
習題
參考文獻
第十四章 FFT和卷積與濾波
14.1 快速傅里葉變換
14.2 DFT直接并行計算法
14.3 并行FFT算法
14.4 心動陣列上的卷積與濾波計算
習題
參考文獻
第十五章 圖論算法
15.1 圖的并行搜索
15.2 圖的傳遞閉包
15.3 圖的連通分量
15.4 圖的最短路徑
15.5 圖的最小生成樹
*15.6 圖的著色
習題
參考文獻
第十六章 圖像分析和計算幾何
16.1 分量標定
16.2 Hough變換
16.3 近鄰問題
16.4 包含問題
16.5 相交問題
16.6 構造問題
習題
參考文獻
第十七章 組合搜索
17.1 基于分治法的與樹搜索
17.2 基于分枝限界法的或樹搜索
17.3 串行的α-β搜索算法
17.4 樹機上的并行搜索算法
17.5 MIMD模型上α-β搜索算法
習題
參考文獻
第十八章 隨機算法
18.1 引言
18.2 部分獨立集
18.3 三角形平面細圖中點的位置
*18.4 模式匹配
18.5 多項式恒等的驗證
18.6 排序
*18.7 最大匹配和完備匹配
習題
參考文獻
第十九章 VLSI計算理論
19.1 VLSI電路模型和計算模型
*19.2 VLSI面-時下界理論
19.3 典型計算圖的結構布局法
19.4 典型計算圖的布局下界
19.5 分治布局法
*19.6 VLSI布局理論
習題
參考文獻
第二十章 模型與下界
20.1 不同PRAM模型的相互模擬
20.2 PRAM-CREW的下界
20.3 PRAM-EREW的下界
20.4 PRAM-CRCW的下界
20.5 P-完全導論
習題
參考文獻
附錄A 復雜度表示及其符號
A.1 大-O及其運算
A.2 大-Ω和大-
A.3 小-o和小-w
附錄B 算法復雜界一覽表
附錄C 索引