目錄
第一章 並行算法基礎
1.1 並行算法的硬件基礎
1.1.1 當代並行計算機體係結構
1.1.2 並行計算機互連網絡
1.2 並行計算模型
1.2.1 SIMD同步並行計算模型
1.2.2 MIMD異步並行計算模型
1.2.3 其他並行計算模型
1.3 並行算法編程模型
1.3.1 數據並行模型
1.3.2 消息傳遞模型
1.3.3 共享變量模型
1.4 並行算法的一般概念
1.4.1 並行算法的定義和分類
1.4.2 並行算法的錶達
1.4.3 並行算法的復雜性度量
1.4.4 並行算法的WT錶示
1.4.5 並行算法的同步和通信
習題
參考文獻
第二章 並行算法的基本設計技術
2.1 平衡樹方法
2.1.1 求取最大值
2.1.2 計算前綴和
2.2 倍增技術
2.2.1 錶序問題的計算
2.2.2 求森林的根
2.3 分治策略
2.3.1 SIMD模型上分治算法的描述
2.3.2 SIMD共享存儲模型上的FFT算法
2.4 劃分原理
2.4.1 歸並原理
2.4.2 劃分算法與歸並算法
2.5 流水綫技術
2.5.1 一維陣列上的流水綫歸並排序原理
2.5.2 一維陣列上的流水綫歸並排序算法
2.6 加速級聯策略
2.6.1 常數時間求最大值算法
2.6.2 雙對數時間算法
2.6.3 加速級聯算法
2.7 破對稱技術
2.7.1 基本著色算法
2.7.2 快速3-著色算法
2.7.3 最優3-著色算法
習題
參考文獻
第三章 比較器網絡上的排序和選擇算法
3.1 Batcher歸並和排序網絡
3.1.1 比較操作和[0，1]原理
3.1.2 奇偶歸並網絡
3.1.3 雙調歸並網絡
3.1.4 Bateher排序網絡
3.2 （m，n）一選擇網絡
3.2.1 分組選擇網絡
3.2.2 平衡分組選擇網絡
3.3 AKS排序網絡
3.3.1 擴展圖和劃分網絡
3.3.2 部分排序算法
3.3.3 完全排序算法
習題
參考文獻
第四章 排序和選擇的同步算法
4.1 Stone雙調排序算法
4.1.1 均勻洗牌函數及其性質
4.1.2 Stone的觀察及其計算模型
4.1.3 Stone的並行排序算法
4.2 Thompson和Kung雙調排序算法
4.2.1 處理器編號方式
4.2.2 Thompon和Kung的觀察
4.2.3 Thompon和Kung的雙調排序算法
4.3 Preparata和Vuilemin雙調排序算法
4.3.1 算法原理
4.3.2 流水綫技術
4.3.3 算法描述
4.4 Akl並行k-選擇算法
4.4.1 算法原理及物理描述
4.4.2 並行k-選擇算法
4.4.3 算法分析
4.5 Valiant並行歸並算法
4.5.1 歸並算法的基本原理
4.5.2 k=pq時Valiant歸並
4.5.3 k=rpq時Valiant歸並
4.6 Hirschberg並行桶排序算法
4.6.1 並行桶排序算法原理
4.6.2 並行桶排序算法描述
4.7 Preparata並行枚舉排序算法
4.7.1 枚舉排序及其實現方法
4.7.2 排序算法的設計和分析
4.8 Cole並行歸並排序算法
4.8.1 使用覆蓋和位序的歸並方法
4.8.2 Cole最佳排序算法
4.8.3 算法的正確性證明及分析
習題
參考文獻
第五章排序和選擇的異步和分布式算法
5.1 MIMD-CREW模型上的異步枚舉
排序算法
5.1.1 算法原理和描述
5.1.2 算法舉例和分析
5.2 MIMD.TC模型上的
異步快排序算法
5.2.1 算法原理和描述
5.2.2 算法舉例和分析
5.3 分布式k-選擇算法
5.3.1 隨機k-選擇算法
5.3.2 確定k-選擇算法
5.4 分布式求中值算法
5.4.1 分布式中值
5.4.2 分布式求中值算法
5.5 分布式定序算法
5.5.1 分布式計算模型
5.5.2 分布式定序算法
5.5.3 算法復雜度分析
5.6 分布式排序算法
5.6.1 模型和定義
5.6.2 靜態排序算法
5.6.3 算法復雜度分析
習題
參考文獻
第六章並行搜索
6.1 單處理機上的搜索
6.1.1 單處理機上的順序搜索
6.1.2 單處理機上有序錶的對半搜索
6.2 SIMD共享存儲模型上有序錶
的搜索
6.2.1 SIMD-EREW模型上的搜索
6.2.2 SIMD-CREW模型上的搜索
6.3 SIMD共享存儲模型上隨機序列的搜索
6.3.1 sIMD-SM模型上的隨機序列搜索.算法描述
6.3.2 sIMDS-M模型上的隨機序列搜索算法分析
6.4 樹連接的SIMD模型上隨機序列的搜索
6.4.1 提問
6.4.2 維護
6.5 網孔連接的SIMD模型上隨機序列的搜索
6.5.1 提問
6.5.2 維護
6.6 MIMD共享存儲模型上有序錶
的搜索
6.6.1 AVL樹及其順序
插入算法
6.6.2 Ellis並行搜索和插入算法
習題
第七章排列和組閤
第八章數據傳輸與選路
第九章並行串匹配
第十章錶達式求值
第十一章上下文無關語富的並行識彆與語法分析
第十二章矩陣運算
第十三章數值計算
第四章腫和捲積與濾波
· · · · · · (收起)