123,123,123

內(nèi)容簡(jiǎn)介

　　《并行算法的設(shè)計(jì)與分析（修訂版）》在初版基礎(chǔ)上，對(duì)個(gè)別章節(jié)進(jìn)行了修改補(bǔ)充，并在每章的開(kāi)頭，除原有的“內(nèi)容提要”外，又新增加，“講授要點(diǎn)”，可作為授課教師的教學(xué)指導(dǎo)和參考。《并行算法的設(shè)計(jì)與分析（修訂版）》系統(tǒng)全面地討論了各種專用和通用并行計(jì)算模型上的算法的設(shè)計(jì)和分析方法。書(shū)中以并行計(jì)算模型為線索，強(qiáng)調(diào)算法、結(jié)構(gòu)和模型三者之間的密切關(guān)系，著重介紹了各種最基本、常用和典型的并行算法，同時(shí)也力圖反映本學(xué)科的最新成就和發(fā)展趨勢(shì)。全書(shū)共分二十章，主要內(nèi)容包括并行算法基礎(chǔ)，并行算法的基本設(shè)計(jì)技術(shù)，各種計(jì)算模型上的計(jì)算機(jī)領(lǐng)域中諸多常用計(jì)算問(wèn)題的并行算法的設(shè)計(jì)和分析方法，最后還討論了各種并行計(jì)算模型的能力、限制、等價(jià)性以及與并行計(jì)算有關(guān)的NC一理論問(wèn)題?！恫⑿兴惴ǖ脑O(shè)計(jì)與分析（修訂版）》取材豐富，內(nèi)容系統(tǒng)全面，可作為高等學(xué)校計(jì)算機(jī)及其他信息科學(xué)類有關(guān)專業(yè)高年級(jí)學(xué)生或研究生的教材．也可供從事計(jì)算機(jī)科學(xué)理論和算法研究的科技人員閱讀參考。《并行算法的設(shè)計(jì)與分析（修訂版）》初版于1994年，曾獲教育部高等學(xué)校優(yōu)秀教材一等獎(jiǎng)。

作者簡(jiǎn)介

　　陳國(guó)良，中國(guó)科學(xué)技術(shù)大學(xué)教授，博士生導(dǎo)師，中國(guó)科學(xué)院院士，1938年6月生于安徽省潁上縣，1961年畢業(yè)于西安交通大學(xué)無(wú)線電系計(jì)算機(jī)專業(yè)。1981-1983年在美國(guó)普度大學(xué)作訪問(wèn)學(xué)者，1984年至今曾多次應(yīng)邀赴東京大學(xué)、普度大學(xué)、澳大利亞國(guó)立大學(xué)、新南威爾士大學(xué)、昆士蘭大學(xué)、格里福斯大學(xué)、堪薩斯城市大學(xué)、依阿華大學(xué)、威斯康星大學(xué)、Mahat‘ish國(guó)際大學(xué)、香港理工大學(xué)、澳門(mén)大學(xué)、北京大學(xué)、國(guó)防科技大學(xué)等講學(xué)交流?，F(xiàn)任國(guó)家高性能計(jì)算中心（合肥）主任，國(guó)際高性能計(jì)算（亞洲）常務(wù)理事，中國(guó)計(jì)算機(jī)學(xué)會(huì)開(kāi)放系統(tǒng)專業(yè)委員會(huì)副主任，中國(guó)數(shù)學(xué)會(huì)計(jì)算數(shù)學(xué)并行計(jì)算專業(yè)委員會(huì)委員。曾任國(guó)家教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)副主任，全國(guó)高等教育電子、電工和信息類專業(yè)自考指導(dǎo)委員會(huì)副主任，安徽省高校計(jì)算機(jī)基礎(chǔ)課程教學(xué)指導(dǎo)委員會(huì)副主任，中國(guó)計(jì)算機(jī)學(xué)會(huì)理事，安徽省計(jì)算機(jī)學(xué)會(huì)理事長(zhǎng)，全國(guó)自然科學(xué)名詞審定委員會(huì)委員，中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系主任。陳國(guó)良教授長(zhǎng)期從事計(jì)算機(jī)科學(xué)技術(shù)的研究與教學(xué)工作。主要研究領(lǐng)域?yàn)椴⑿兴惴?、并行?jì)算機(jī)體系結(jié)構(gòu)和智能計(jì)算等。先后承擔(dān)10多項(xiàng)國(guó)家863計(jì)劃、國(guó)家攀登計(jì)劃、國(guó)家自然科學(xué)基金、國(guó)家973計(jì)劃、教育部博士點(diǎn)基金等科研項(xiàng)目。取得了多項(xiàng)被國(guó)內(nèi)外廣泛引用、達(dá)國(guó)際先進(jìn)水平的科研成果，發(fā)表論文200多篇，出版著作9部、譯著5部，參與主編計(jì)算機(jī)類辭典、詞匯5部，主審、主編計(jì)算機(jī)類各種教材8部。曾獲國(guó)家科技進(jìn)步二等獎(jiǎng)、國(guó)家級(jí)教學(xué)成果二等獎(jiǎng)、國(guó)家教育部科技進(jìn)步一等獎(jiǎng)、中國(guó)科學(xué)院科技進(jìn)步二等獎(jiǎng)和自然科學(xué)三等獎(jiǎng)、全國(guó)優(yōu)秀教材一等獎(jiǎng)、全國(guó)學(xué)術(shù)著作優(yōu)秀獎(jiǎng)、安徽省科技進(jìn)步二等獎(jiǎng)、國(guó)家科委高技術(shù)研究與發(fā)展計(jì)劃三等獎(jiǎng)、國(guó)家教委科技進(jìn)步三等獎(jiǎng)共18項(xiàng)，并獲2001年度“國(guó)家863計(jì)劃15周年先進(jìn)個(gè)人重要貢獻(xiàn)獎(jiǎng)”。陳國(guó)良教授在中國(guó)科學(xué)技術(shù)大學(xué)執(zhí)教30多年。長(zhǎng)期以來(lái)，圍繞著并行算法的教學(xué)與研究，逐漸形成了一套完整的“算法理論一算法設(shè)計(jì)一算法實(shí)現(xiàn)一算法應(yīng)用”的并行算法學(xué)科體系，營(yíng)造了我國(guó)并行算法類的教學(xué)基地。他先后指導(dǎo)培養(yǎng)研究生100多名，其中博士生60名，為我國(guó)培養(yǎng)了一批在國(guó)內(nèi)外從事算法研究的高級(jí)人才。曾榮獲1998年度安徽省教育系統(tǒng)勞動(dòng)模范、安徽省優(yōu)秀教師稱號(hào)、2001年度寶鋼教育基金優(yōu)秀教師特等獎(jiǎng)和2003年度第一屆高等學(xué)校教學(xué)名師獎(jiǎng)。陳國(guó)良教授是我國(guó)非數(shù)值并行算法研究的學(xué)科帶頭人。他率先創(chuàng)建的我國(guó)第一個(gè)國(guó)家高性能計(jì)算中心是我國(guó)并行算法研究、環(huán)境科學(xué)與工程計(jì)算軟件的重要基地，在學(xué)術(shù)界和教育界有一定的影響和地位。

圖書(shū)目錄

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