并行算法的设计与分析【下载 pdf 百度网盘 epub 免费 2025 电子版 mobi 在线】

并行算法的设计与分析PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第一章　绪论1

1.1 引言2

1.2　并行算法的硬件基础3

1.2.1　并行计算机体系结构3

1.2.2　并行计算机互连网络11

1.2.3　并行计算机存储组织22

1.3　并行计算模型24

1.3.1　模型的定义、功能和分类25

1.3.2　共享存储模型25

1.3.3　分布存储模型28

1.3.4　层次存储模型34

1.3.5　其他并行计算模型37

1.4　并行算法的基础知识39

1.4.1　并行算法的定义40

1.4.2　并行算法的表达41

1.4.3　并行算法的复杂性42

1.4.4　并行算法的同步和通信45

1.5　并行算法的性能分析47

1.5.1　算法的执行速度47

1.5.2　算法使用的处理器数48

1.5.3　并行算法的WT表示50

1.5.4　并行算法的通信成本53

习题54

参考文献59

第二章　设计技术62

2.1　平衡树方法63

2.1.1　求取最大值63

2.1.2　计算前缀和63

2.2　倍增技术67

2.2.1　表序问题的计算68

2.2.2　求森林的根69

2.3　分治策略70

2.3.1　SIMD模型上分治算法的描述70

2.3.2　SIMD共享存储模型上的FFT算法71

2.4　划分原理73

2.4.1　归并原理74

2.4.2　划分算法与归并算法74

2.5　流水线技术75

2.5.1 一维阵列上的流水线归并排序原理76

2.5.2　一维阵列上的流水线归并排序算法76

2.6　加速级联策略78

2.6.1　常数时间求最大值算法78

2.6.2　双对数时间算法79

2.6.3　加速级联算法80

2.7　破对称技术81

2.7.1　基本着色算法81

2.7.2　快速3-着色算法82

2.7.3　最优3-着色算法83

习题84

参考文献86

第三章　前缀计算88

3.1 引言89

3.1.1　前缀计算的定义89

3.1.2　前缀计算的应用90

3.2　并行前缀计算算法90

3.2.1　组合网络上的前缀计算91

3.2.2　互连网络上的前缀计算95

3.2.3　PRAM模型上的前缀计算98

3.3　线性递归方程求解103

3.3.1　平易线性递归方程求解算法103

3.3.2　更优线性递归方程求解算法104

3.4　排序107

3.4.1　基排序107

3.4.2　快排序109

3.5　最大和子序列112

3.5.1　简单串行算法112

3.5.2　易于并行化的串行算法113

3.5.3　并行算法116

习题118

参考文献119

第四章　排序和选择网络120

4.1　Batcher归并和排序网络121

4.1.1 比较操作和［0,1］原理121

4.1.2　奇偶归并网络122

4.1.3　双调归并网络124

4.1.4　Batcher排序网络125

4.2　（m,n）-选择网络128

4.2.1　分组选择网络128

4.2.2 平衡分组选择网络132

4.3　AKS排序网络133

4.3.1 扩展器133

4.3.2　对分器135

4.3.3　分离器137

4.3.4　AKS排序网络的构造及分析138

习题142

参考文献143

第五章　排序和选择算法145

5.1　Stone双调排序算法146

5.1.1　均匀洗牌函数及其性质146

5.1.2　Stone的观察及其计算模型146

5.1.3　Stone的并行排序算法149

5.2　Thompson和Kung双调排序算法151

5.2.1　处理器编号方式151

5.2.2　Thompson和Kung的观察152

5.2.3　Thompson和Kung的双调排序算法153

5.3　Preparata和Vuilemin双调排序算法156

5.3.1　算法原理156

5.3.2　流水线技术158

5.3.3　算法描述159

5.4　Akl并行k-选择算法160

5.4.1　算法原理及物理描述161

5.4.2　并行k-选择算法161

5.4.3　算法分析163

5.5　Valiant并行归并算法164

5.5.1 归并算法的基本原理164

5.5.2 k=？」时Valiant归并165

5.5.3 k=？」时Valiant归并166

5.6　Hirschberg并行桶排序算法167

5.6.1　并行桶排序算法原理167

5.6.2　并行桶排序算法描述168

5.7　Preparata并行枚举排序算法169

5.7.1　枚举排序及其实现方法169

5.7.2　排序算法的设计和分析171

5.8　Cole并行归并排序算法173

5.8.1　使用覆盖和位序的归并方法173

5.8.2　Cole最佳排序算法175

5.8.3　算法的正确性证明及分析177

5.9　MIMD-CREW模型上的异步枚举排序算法183

5.9.1　算法原理和描述183

5.9.2　算法举例和分析184

5.10　MIMD-TC模型上的异步快排序算法185

5.10.1　算法原理和描述185

5.10.2　算法举例和分析187

习题188

参考文献189

第六章　分布式算法191

6.1　分布式算法概述192

6.1.1　分布式算法特点192

6.1.2　计算模型193

6.1.3　复杂性度量195

6.2　构造生成树算法195

6.2.1　广播和敛播算法196

6.2.2　构造生成树199

6.2.3　构造深度优先生成树201

6.2.4　不指定根构造生成树203

6.2.5　最小生成树206

6.3　环上选举算法210

6.3.1　LCR算法211

6.3.2　改进算法212

6.4　分布式k-选择算法214

6.4.1　随机k-选择算法214

6.4.2　确定k-选择算法216

6.4.3　分布式求中值算法218

6.5　定序与排序220

6.5.1　定序算法220

6.5.2　排序算法224

习题226

参考文献226

第七章　并行搜索228

7.1　单处理机上的搜索229

7.1.1　单处理机上的顺序搜索229

7.1.2　单处理机上有序表的对半搜索229

7.2 SIMD共享存储模型上有序表的搜索230

7.2.1 SIMD-EREW模型上的搜索230

7.2.2 SIMD-CREW模型上的搜索231

7.3 SIMD共享存储模型上随机序列的搜索234

7.3.1 SIMD-SM模型上的随机序列搜索算法描述235

7.3.2 SIMD-SM模型上的随机序列搜索算法分析235

7.4 树连接的SIMD模型上随机序列的搜索236

7.4.1　提问236

7.4.2　维护237

7.5 网孔连接的SIMD模型上随机序列的搜索238

7.5.1　提问239

7.5.2　维护242

7.6　MIMD共享存储模型上有序表的搜索242

7.6.1　AVL树及其顺序插入算法242

7.6.2　Ellis并行搜索和插入算法244

习题247

参考文献248

第八章　选路算法249

8.1　引言250

8.2　贪心选路算法251

8.2.1 一维阵列上的贪心选路算法251

8.2.2　二维阵列上贪心选路算法的分析253

8.2.3　蝶形网络上的贪心选路算法255

8.3　随机和确定选路算法257

8.3.1 二维阵列上的随机选路算法257

8.3.2　超立方网络上的随机选路算法259

8.3.3　二维阵列上的确定选路算法260

8.4　数据的分布和集中262

8.4.1　数据的分布262

8.4.2　多到一选路算法266

8.5　线路交换模式下的选路算法267

8.5.1 阻塞网络中的竞争分析267

8.5.2　阻塞网络中的自选路算法270

8.5.3 可重排网络中的中级选路算法273

习题279

参考文献280

第九章　串匹配282

9.1　字符串精确匹配并行算法283

9.1.1 KMP串匹配顺序算法283

9.1.2　分布存储系统上精确串匹配并行算法285

9.1.3　基于比较指纹函数值的串匹配算法及其并行化289

9.1.4　串匹配的平均时间复杂度分析291

9.1.5　后缀树上的串匹配300

9.2　多模式匹配并行算法310

9.2.1　多模式匹配问题310

9.2.2 可重构网孔机器上多模式匹配并行算法310

9.3　允许k-差别的近似串匹配并行算法314

9.3.1 编辑距离与允许k-差别的近似串匹配问题315

9.3.2　PRAM模型上允许k-差别的近似串匹配并行算法317

9.4　允许k-误配的近似串匹配并行算法324

9.4.1 汉明距离与允许k-误配的近似串匹配问题324

9.4.2　LARPBS计算模型及其基本数据移动操作325

9.4.3 LARPBS模型上允许k-误配的近似串匹配并行算法327

9.5　最长公共子序列查找并行算法331

9.5.1 求解最长公共子序列问题的顺序算法332

9.5.2 BSR模型上求解最长公共子序列问题的并行算法334

9.5.3　心动阵列处理器结构上求解最长公共子序列问题的并行算法339

习题347

参考文献348

第十章　表达式求值351

10.1　构造表达式树352

10.1.1　全括号表达式的表达式树352

10.1.2　表达式树上的括号操作353

10.1.3　计算match（i）的并行算法355

10.2　填充游戏用于表达式求值356

10.2.1　二叉树上的填充游戏356

10.2.2　填充游戏用于算术表达式求值357

10.3　最优的并行表达式求值算法359

10.4　一般表达式求值算法363

10.4.1　一般表达式与直线程序363

10.4.2　仅有乘法操作符的dag的计算364

10.4.3　仅有加法操作符的dag的计算365

10.4.4　gbdag图和直线程序的计算366

10.5　正则表达式到确定自动机的最优并行转换369

10.5.1　基本概念和术语370

10.5.2 正则表达式到非确定有限自动机的HU转换方法371

10.5.3　有限自动机确定化并行算法375

10.5.4　确定自动机的最小化并行算法377

习题380

参考文献381

第十一章　上下文无关语言383

11.1　一般的上下文无关语言的并行识别384

11.1.1　基本概念和术语384

11.1.2　残缺部分语法树及其合成规则386

11.1.3　共享存储模型上歧义性上下文无关语言并行识别算法388

11.2　一般上下文无关语言的并行语法分析391

11.2.1　基本概念和算法原理391

11.2.2　SIMD-CREW模型上一般上下文无关语言的语法分析算法393

11.3　任意上下文无关语言的并行语法分析397

11.3.1　基本概念与算法原理397

11.3.2　SIMD-LC模型上任意上下文无关语言的并行语法分析算法399

11.4 括号语言的最优并行识别和语法分析401

11.4.1　基本概念和算法原理401

11.4.2　算法的具体实现402

11.4.3　树的压缩技术404

11.4.4 SIMD-CREW模型上括号语言的语法分析算法407

习题408

参考文献409

第十二章　矩阵运算410

12.1 矩阵转置411

12.1.1　单处理机上的矩阵转置算法411

12.1.2 SIMD-MC2模型上的矩阵转置411

12.1.3 SIMD-PS模型上的矩阵转置414

12.1.4 SIMD-CC模型上的矩阵转置416

12.2　矩阵相乘418

12.2.1　单处理机上的矩阵相乘418

12.2.2 SIMD-MC2模型上的矩阵乘法419

12.2.3 SIMD-CC模型上的矩阵乘法421

12.2.4 MIMD机器上的矩阵乘法424

12.3　矩阵和向量相乘427

12.3.1　树连接的机器上的矩阵和向量乘法428

12.3.2　树网结构上的矩阵和向量乘法429

12.4　心动阵列上的矩阵运算430

12.4.1　二维六角形阵列上的矩阵乘法430

12.4.2　二维六角形阵列上方阵的LU分解432

12.4.3　六角形阵列上的方阵求逆435

12.4.4　一维阵列上求解三角形线性系437

习题439

参考文献443

第十三章　数值计算444

13.1　三对角方程组的求解445

13.1.1　三对角方程组直接求解法445

13.1.2　三对角方程组奇偶归约求解法447

13.2 n阶线性方程组的求解449

13.2.1 SIMD-CREW模型上的Gauss-Jordan算法450

13.2.2 MIMD-CREW模型上的Gauss-Seidel算法452

13.2.3　紧耦合多处理机系统中LU算法的效率分析454

13.3　非线性方程的求根457

13.3.1 SIMD-CREW模型上的求根算法457

13.3.2 MIMD-CREW模型上的牛顿求根法459

13.3.3 Fibonacci分点法异步求根算法461

13.4　偏微分方程的差分求解463

13.4.1　偏微分方程的差分数值求解法464

13.4.2 SIMD-MC2模型上的PDE求解方法465

13.5　方阵的特征值与特征向量Jacobi方法469

13.5.1　对称方阵对角化方法469

13.5.2 SIMD-CC模型上的求特征值算法471

习题473

参考文献475

第十四章　快速傅氏变换476

14.1　快速傅里叶变换477

14.1.1　顺序的FFT算法477

14.1.2 FFT应用于多项式乘积478

14.2 DFT直接并行计算法480

14.2.1 SIMD模型上系数矩阵的计算480

14.2.2 SIMD-MT模型上的DFT算法481

14.3 并行FFT算法484

14.3.1 SIMD-MC2模型上的FFT算法484

14.3.2 SIMD-BF模型上的FF［算法486

14.3.3 SIMD-PS模型上的FFT计算488

14.3.4 SIMD-CC模型上的FFT计算490

14.3.5　一维心动阵列上的DFT计算495

14.4　心动阵列上的卷积与滤波计算496

14.4.1　一维卷积在线性阵列上的实现497

14.4.2　无限冲激滤波在线性阵列上的实现498

14.4.3 中值滤波在线性阵列上的实现499

习题501

参考文献503

第十五章　图论算法504

15.1　图的并行搜索505

15.1.1 p-深度优先搜索505

15.1.2 p-宽深优先搜索506

15.1.3 p-宽度优先搜索506

15.2　图的传递闭包508

15.2.1　传递闭包问题508

15.2.2 SIMD-CC模型上的传递闭包算法509

15.2.3 二维心动阵列上的传递闭包算法510

15.3　图的连通分量513

15.3.1 SIMD-CC模型上的连通分量算法513

15.3.2 SIMD-SM模型上的连通分量算法515

15.3.3 SIMD-TC模型上的连通分量算法516

15.3.4 SIMD-MT模型上的连通分量算法518

15.4　图的最短路径521

15.4.1　所有顶点对间的最短路径算法521

15.4.2 MIMD-SM模型上单源最短路径算法524

15.5　图的最小生成树528

15.5.1 SIMD-EREW模型上最小生成树算法528

15.5.2 MIMD-SM模型上最小生成树算法532

15.5.3　树机模型上最小生成树算法535

15.6　图的着色538

15.6.1　二分图的边着色算法538

15.6.2　外平面图最优顶点着色540

15.6.3　外平面图最优边着色算法546

15.6.4 Halin图最优边着色算法549

习题553

参考文献556

第十六章　计算几何558

16.1　判定问题559

16.1.1 近邻问题559

16.1.2　相交问题563

16.1.3　包含问题569

16.2　构造问题574

16.2.1　求凸壳问题的下界575

16.2.2　顺序求凸壳算法575

16.2.3 SIMD-MT模型上的求凸壳算法577

16.2.4 SIMD-EREW模型上的求凸壳算法579

16.3 Voronoi图问题585

16.3.1　基本概念585

16.3.2　构造Voronoi图的串行分治算法587

16.3.3 超立方模型上构造Voronoi图算法588

16.3.4 SIMD-CREW模型上构造Voronoi图算法593

16.4 平面点集的三角剖分598

16.4.1　基本概念598

16.4.2 Delaunay三角剖分串行算法600

16.4.3 Delaunay三角剖分并行算法604

习题609

参考文献610

第十七章 组合搜索613

17.1　产生排列的算法614

17.1.1　产生词典序的排列算法614

17.1.2　串行排列算法的并行化616

17.1.3 自适应排列产生器621

17.2　产生组合的算法623

17.2.1 产生组合的顺序算法623

17.2.2 产生组合的并行算法624

17.3　分支限界法的搜索629

17.3.1 8-谜问题630

17.3.2　串行分支限界算法631

17.3.3 用串行分支限界法求TSP633

17.3.4　并行TSP算法637

17.4　串行的α-β搜索算法639

17.4.1 博弈树与最小最大原理639

17.4.2　串行的α-β算法640

17.4.3 MIMD模型上α-β搜索算法642

17.5　动态规划648

17.5.1　矩阵链乘问题649

17.5.2　最短路径问题653

17.5.3 0/1背包问题654

习题656

参考文献659

第十八章　随机算法661

18.1 引言662

18.1.1　概率论的基本知识662

18.1.2　随机算法的模型及其度量666

18.1.3　随机算法的设计方法666

18.2　部分独立集668

18.2.1　有向环图669

18.2.2 平面图670

18.3　三角形平面细图中点的位置672

18.3.1　细图层次673

18.3.2　细图层次的构造算法673

18.4　模式匹配675

18.4.1　指纹函数676

18.4.2　串匹配679

18.4.3　二维数组的匹配680

18.5　多项式恒等的验证682

18.5.1 基本技术682

18.5.2　矩阵乘积的验证683

18.6　排序685

18.6.1　随机采样与随机快排序685

18.6.2　并行随机快排序算法686

18.6.3　快速随机并行排序算法688

18.7　最大匹配和完备匹配691

18.7.1　图的代数性质692

18.7.2　测试完备匹配存在的随机算法694

习题698

参考文献699

第十九章　VLSI计算理论701

19.1 VLSI电路模型和计算模型702

19.1.1 VLSI电路模型702

19.1.2 VLSI计算模型704

19.2 VLSI面-时下界理论706

19.2.1 几种基本的下界论点706

19.2.2　信息流和穿越序列708

19.3　典型计算图的结构布局法710

19.3.1　树的布局710

19.3.2　网孔和树网的布局712

19.3.3　洗牌交换网的布局713

19.3.4　立方环的布局715

19.3.5　蝶形网的布局717

19.4　典型计算图的布局下界718

19.4.1　树的布局下界718

19.4.2　树网的布局下界720

19.4.3　洗牌交换网的布局下界723

19.4.4　蝶形网的布局下界724

19.5　分治布局法724

19.5.1 分离集725

19.5.2　强分离集727

19.5.3 通道生成728

19.5.4　分治布局法729

19.6 VLSI布局理论732

19.6.1 平面图的分离定理732

19.6.2　图的交叉点数733

19.6.3　布局下界定理734

习题736

参考文献737

第二十章　并行计算理论738

20.1　不同PRAM模型的相互模拟739

20.1.1 在PRAM-EREW上模拟PPRAM-CRCW739

20.1.2　在CPRAM-CRCW上模拟PPRAM-CRCW740

20.1.3　在APRAM-CRCW上模拟PPRAM-CRCW742

20.2 PRAM-CREW的下界743

20.2.1　理想的PRAM模型743

20.2.2　形式描述744

20.2.3　特定问题的下界746

20.3 PRAM-EREW的下界747

20.3.1 工具和方法747

20.3.2　主要下界748

20.4 PRAM-CRCW的下界750

20.4.1 PRAM-CRCW与无界扇入电路751

20.4.2　无界扇入电路的下界757

20.5　并行复杂性理论762

20.5.1　串行复杂性理论简介762

20.5.2　问题的可并行化763

20.5.3 NC类和RNC类766

20.5.4 P-完全问题范例770

20.5.5　小结778

习题778

参考文献779

附录A　复杂度表示及其符号781

A.1　大-O及其运算781

A.2　大-Ω和大-Θ781

A.3　小-ο和小-ω782

附录B　算法复杂界一览表783

附录C　专业术语中英文对照表及索引797