中国科学技术大学并行算法期末考试范围

《并行算法》课程总结与复习 xd`!z`X!,s  
Ch1 并行算法基础 j?n:"@!G/  
1.1 并行计算机体系结构 \3@AC7  
    并行计算机的分类 P>t[35/1  
    SISD,SIMD,MISD,MIMD； 2x*C1   
    SIMD,PVP,SMP,MPP,COW,DSM r?=7#/]  
    并行计算机的互连方式
1$Pn;jg:  
    静态：LA(LC),MC,TC,MT,HC,BC,SE nC5  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) vYNh0)$%F  
1.2 并行计算模型 Vhs:X~=qL  
    PRAM模型：SIMD-SM， L){rv)?="  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW XHlx89v7  
    SIMD-IN模型：SIMD-DM n'#(iW)f  
    异步APRAM模型：MIMD-SM #)BdN  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 Tx7YHE6{  
    LogP模型：MIMD-DM，点到点通讯 ,SAS\!hsE  
1.3 并行算法的一般概念 !Fz9\ |  
    并行算法的定义 [lC*|4t &  
    并行算法的表示 nV0"q|0K;  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 I/s?]v  
    并行算法的WT表示：Brent定理、WT最优 n8M/Y}mH  
    加速比性能定律(略) X~Li`  
    并行算法的同步和通讯(略) <L__;j1Wx  
Ch2 并行算法的基本设计技术 e.0vh?{\  
2.1 并行算法的三种基本设计方法 eD, 7gC-  
2.2 基本设计技术 LTY@}o]\U  
    平衡树方法：求最大值、计算前缀和 h(I~HZ[K&T  
    倍增技术：表序问题、求森林的根 >29eu^~nh  
    分治策略：FFT分治算法 P$)9osr  
    划分原理： L$`!~z1  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 'sm+3d  
    流水线技术：五点的DFT计算，Systolic算法  IjDG  
    加速级联(略) mLO{~ruu  
    破对称技术 Ox&g#,@h  
Ch3 比较器网络上的排序和选择算法 %&^F.JTt\  
3.1 Batcher归并和排序 7;n'4LIa9  
    0-1原理的证明(略) Lvc*L6  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) / vge@bsE  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Ah &D5,3  
    Batcher排序网络：原理、种类和复杂性 { >Y<!  
3.2 (m, n)-选择网络 >;QkV6i7  
    分组选择网络 {61NLF\0H  
    平衡分组选择网络及其改进 FI~)ZhE)]  
Ch4 排序和选择的同步算法 @yB!?x  
4.1 一维线性阵列上的并行排序算法(略) -^;G^Uq6=  
4.2 二维Mesh上的并行排序算法 C did*hxJ  
    ShearSort排序算法 gW6lMyiLb  
    Thompson&Kung双调排序算法及其计算示例 i<1w*yu  
4.3 Stone双调排序算法(略) A A<9XC  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 }<&g1x'pa  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 '8k\a{t_z  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 q?Q"Ab  
Ch5 排序和选择的异步和分布式算法(略) ^C):yxNP  
5.1 MIMD-CREW模型上的异步枚举排序算法 f<WnPoV  
5.2 MIMD-TC模型上的异步快排序算法 4^alAq^  
5.3分布式k-选择算法 rg_-gZl8&z  
Ch6 并行搜索 bR*T}w$<  
6.1 单处理器上的搜索(略) QD<^VY
6  
6.2 SIMD共享存储模型上有序表的搜索：算法 B{/Pv0y  
6.3 SIMD共享存储模型上随机序列的搜索：算法 uiE9#G  
6.4 树连接的SIMD模型上随机序列的搜索：算法 9|Jmj @9  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 X'jEI{1w  
Ch8 数据传输与选路 @w6^*Z_hQ  
8.1 引言 / vje='[!  
    信包传输性能参数 lbT<HWzNH  
    维序选路(X-Y选路、E-立方选路) A>OL5TCl  
    选路模式及其传输时间公式 c2?(.UV  
8.2 单一信包一到一传输 YcRjbF,|6  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 2;[75(l6|}  
8.3 一到多播送 f5wOk&G  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Qh/yPO
Sm:  
8.4 多到多播送 ^bL.|vB  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 kc|`VB8L  
8.5 贪心算法(书8.2) T_jwj N  
    二维阵列上的贪心算法 5[X^1
 
    蝶形网上的贪心算法 XV%L6x  
8.6 随机和确定的选路算法(书8.3)(略) _*bXVJ ]  
Ch12矩阵运算 ;N]ElwP  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 6$)Yqg`X  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 wOHK dQ'  
12.3 矩阵向量乘法 [ "J  
    带状划分的算法及其时间分析 uA:;OM}  
    棋盘划分的算法及其时间分析 :7:Nx`D8  
    Systolic算法(略) @%ChPjN  
12.4 矩阵乘法 39"8Nq|e  
    简单并行分块算法 ~O@V;y  
    Cannon算法及其计算示例 [_-CO
}>  
    Fox算法及其计算示例 HEjV7g0E  
    DNS算法及其计算示例 %tUJ >qYU  
    Systolic算法(略) `j4ukOnG  
Ch13 数值计算 "St,4b  
13.1 稠密线性方程组求解 K{M_  4'\  
    SIMD-CREW的上三角方程组回代算法 JWMIZ{/M  
    SIMD-CREW上的Gauss-Jordan算法 ^>g+:?x  
    MIMD-CREW上的Gauss-Seidel算法 vuDp_p*]S  
13.2 稀疏线性方程组的求解 IO^O9IEx,  
    三对角方程组的奇偶规约求解法 l4R:_Z<  
    Gauss-Seidel迭代法的红黑着色并行算法 x-y=Jor  
13.3 非线性方程的求根(略) Z?"Pkc.Ei  
Ch14 快速傅立叶变换FFT 2$[u&__E  
14.1 快速傅里叶变换(FFT) {_^sR}%]F  
    离散傅里叶变换(DFT) *RxbqB-  
    串行FFT递归算法及其计算原理 x0Tb7y`  
    串行FFT蝶式计算及其蝶式计算流图 L8R|\Bx  
14.2 DFT直接并行算法 VCbnS191*  
    SIMD-MT上的并行DFT算法(略) G;fP  
14.3 并行FFT算法 ua4QtDSs  
    SIMD-MC上的FFT算法(略) 3.R?=npA  
    SIMD-BF上的FFT算法及其时间分析 dVO|q9 /  
Ch15 图论算法 ) I-8.  
15.1 图的并行搜索 !8l4H
c8  
    p-深度优先搜索及其计算示例 '7xmj:.==  
    p-宽深优先搜索及其计算示例 ? 76jz>;b  
    p-宽度优先搜索及其计算示例 Fo;xA  
15.2 图的传递闭包 WNd(X}  
    基于布尔矩阵乘积的算法原理 Ae`K 9  
    计算示例 evimnV  
    SIMD-CC上的传递闭包算法 #[I`VA\x  
15.3 图的连通分量 -I4@` V  
    基于传递闭包的算法 42# rhgW  
    基于顶点合并的算法 )W*S6}A  
15.4 图的最短路径 n!3_%K0!r&  
    基于矩阵乘积的算法原理 s)ZL`S?</  
    计算示例 G.T}^xHmL  
15.5 图的最小生成树 ^(UL$cQ>  
    SIMD-EREW模型上的Prim算法 Zf?>:P  
    算法的时间分析 "MK:y[+*  
Ch18 随机算法 ->K*r\T  
18.1 引言 BhdJ/C^  
    基本知识：随机算法的定义、分类、重复性定律 wm8(Ju  
    时间复杂性度量 +s1mm c  
    设计方法 pjHUlQ  
18.2 低度顶点部分独立集 (B,CL222x  
    串行算法 |910xd`Z  
    随机并行算法及其正确性证明 HAN#_B1.  
18.5 多项式恒等的验证 _j<46^  
    基本原理和方法 oD~VK,.  
    矩阵乘积的验证原理 i(L;1 `  
18.8 格点逼近问题(略) N55;oj_K  
18.9 SAT问题的异步随机并行算法(略) s?E7tma
M  
Ch20 模型与下界 &W`yHQ"JY  
20.1不同的PRAM模型的相互模拟 ~G5)ya-  
    PRAM-EREW模拟PPRAM-CRCW H4^-MSw  
    PRAM-CRCW之间的模拟 }MXZ  
20.2下界 ",`fGu )  
    算法研究的两个方向：优化（上界）、可能性（下界） 4J-)+C/edx  
    Gates的工作 ']A+wGR&r  
    理想的PRAM模型与下界 UiaY0 .D  
    PRAM模型的下界 :
4&qASn  
20.3 NP完全理论导引(略) ]W-:-.prh  
20.4 P完全理论(略)