並行算法的設計與分析

《並行算法的設計與分析（修訂版）》在初版基礎上，對個別章節進行了修改補充，並在每章的開頭，除原有的“內容提要”外，又新增加，“講授要點”，可作為授課教師的教學指導和參考。《並行算法的設計與分析（修訂版）》系統全面地討論了各種專用和通用並行計算模型上的算法的設計和分析方法。書中以並行計算模型為線索，強調算法、結構和模型三者之間的密切關係，着重介紹了各種最基本、常用和典型的並行算法，同時也力圖反映本學科的最新成就和發展趨勢。

全書共分二十章，主要內容包括並行算法基礎，並行算法的基本設計技術，各種計算模型上的計算機領域中諸多常用計算問題的並行算法的設計和分析方法，最後還討論了各種並行計算模型的能力、限制、等價性以及與並行計算有關的NC一理論問題。

《並行算法的設計與分析（修訂版）》取材豐富，內容系統全面，可作為高等學校計算機及其他信息科學類有關專業高年級學生或研究生的教材．也可供從事計算機科學理論和算法研究的科技人員閲讀參考。

第一章 並行算法基礎

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並行搜索和插入算法

習題

第七章排列和組合

第八章數據傳輸與選路

第九章並行串匹配

第十章表達式求值

第十一章上下文無關語富的並行識別與語法分析

第十二章矩陣運算

第十三章數值計算

第四章腫和卷積與濾波 ^[1]