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

《并行算法》课程总结与复习 ik:)-GV;s  
Ch1 并行算法基础 pXT$Y8M  
1.1 并行计算机体系结构 SiuO99'nV  
    并行计算机的分类 Pl5NHVr  
    SISD,SIMD,MISD,MIMD； NK#"qK""k  
    SIMD,PVP,SMP,MPP,COW,DSM zju
,#%  
    并行计算机的互连方式 O->(9k <  
    静态：LA(LC),MC,TC,MT,HC,BC,SE #&2N,M!Q  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) ^L
v^W  
1.2 并行计算模型 X @jYQ.  
    PRAM模型：SIMD-SM， \PMKmJX0O  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW 7F9g:r/^  
    SIMD-IN模型：SIMD-DM DdS3<3]A  
    异步APRAM模型：MIMD-SM Jgv>$u  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 L+ETMk0  
    LogP模型：MIMD-DM，点到点通讯 wZ3vF)2s  
1.3 并行算法的一般概念 b;;Kxi:7$}  
    并行算法的定义 Y <i}"eI*  
    并行算法的表示 }
!7DF  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 K#C56k q&  
    并行算法的WT表示：Brent定理、WT最优 t?H;iBrpxd  
    加速比性能定律(略) f, j(uP  
    并行算法的同步和通讯(略) AFB 7s z  
Ch2 并行算法的基本设计技术 .L{+O6*c  
2.1 并行算法的三种基本设计方法 +xdFkc  
2.2 基本设计技术 ^]!1'xg  
    平衡树方法：求最大值、计算前缀和 H6\ x.J^,  
    倍增技术：表序问题、求森林的根 ecI 2]aKi  
    分治策略：FFT分治算法 oS|~\,p"  
    划分原理： I4X+'fW,  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) eh7r'DmAR  
    流水线技术：五点的DFT计算，Systolic算法 ~Q9) Q  
    加速级联(略) YeVc,B'  
    破对称技术 :ItW|  
Ch3 比较器网络上的排序和选择算法 z'D{:q  
3.1 Batcher归并和排序 8+cpNX  
    0-1原理的证明(略) y-q?pqt  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) :.<TWBoV  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) r<"/P`r  
    Batcher排序网络：原理、种类和复杂性  RGuHXf  
3.2 (m, n)-选择网络 "t&k{\$\  
    分组选择网络 =i>F^7)U1  
    平衡分组选择网络及其改进 "?&bh@P&  
Ch4 排序和选择的同步算法 Z?aR9OTP  
4.1 一维线性阵列上的并行排序算法(略)  CF92AY
 
4.2 二维Mesh上的并行排序算法 gH55caF<  
    ShearSort排序算法 7kpW1tjY  
    Thompson&Kung双调排序算法及其计算示例 aDv/kFfn  
4.3 Stone双调排序算法(略) nGgc~E$j  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 .FRF<_`^  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 h`rjD d  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 IX?%H!i  
Ch5 排序和选择的异步和分布式算法(略) o(N
yOC  
5.1 MIMD-CREW模型上的异步枚举排序算法 +p6\R;_E  
5.2 MIMD-TC模型上的异步快排序算法 0$ac1;7  
5.3分布式k-选择算法 % peb{i  
Ch6 并行搜索 [F{a-i-  
6.1 单处理器上的搜索(略) |Z|xM   
6.2 SIMD共享存储模型上有序表的搜索：算法 ^uElQI  
6.3 SIMD共享存储模型上随机序列的搜索：算法 :Fp
Bz~!a  
6.4 树连接的SIMD模型上随机序列的搜索：算法 ;-^9j)31+F  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 DC7}Xly(  
Ch8 数据传输与选路 1)Bi>X  
8.1 引言 e-)1K  
    信包传输性能参数 %,D%Q~  
    维序选路(X-Y选路、E-立方选路) Y!$z7K  
    选路模式及其传输时间公式 eW,Pn'  
8.2 单一信包一到一传输 L%Q *\d   
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 1A.\Ao  
8.3 一到多播送 ^:ngHue8~  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 FWTl:LqFO  
8.4 多到多播送 cs;Gk:  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 1V?)zp  
8.5 贪心算法(书8.2) 0EU4irMa  
    二维阵列上的贪心算法 |JQKxvjT  
    蝶形网上的贪心算法 (oEA)yc|  
8.6 随机和确定的选路算法(书8.3)(略) .6#2i <oPW  
Ch12矩阵运算 JdEb _c3S  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 TY?io@  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 H`@7o8oj1  
12.3 矩阵向量乘法 t[,\TM^h}0  
    带状划分的算法及其时间分析 LnX^*;P5t  
    棋盘划分的算法及其时间分析 dUSuhT  
    Systolic算法(略) >z$|O>j  
12.4 矩阵乘法 y&]D2"I  
    简单并行分块算法 8!Kfe  
    Cannon算法及其计算示例 ;\.&F
Mi  
    Fox算法及其计算示例 A79SAheX#  
    DNS算法及其计算示例 6dMpd4"\  
    Systolic算法(略) v8N1fuP}  
Ch13 数值计算 e(A&VIp  
13.1 稠密线性方程组求解 H5)WxsZ R  
    SIMD-CREW的上三角方程组回代算法 uES
HTX/[  
    SIMD-CREW上的Gauss-Jordan算法 Xw)+5+t"{  
    MIMD-CREW上的Gauss-Seidel算法 0@;E8^pa  
13.2 稀疏线性方程组的求解 gO36tc:ce  
    三对角方程组的奇偶规约求解法 u e~1144  
    Gauss-Seidel迭代法的红黑着色并行算法 4V5*6O9(u  
13.3 非线性方程的求根(略) %+}\i'j7  
Ch14 快速傅立叶变换FFT %## bg<  
14.1 快速傅里叶变换(FFT) %l,EA#89s  
    离散傅里叶变换(DFT) 4 @h6|=  
    串行FFT递归算法及其计算原理 (?(ahtT4T  
    串行FFT蝶式计算及其蝶式计算流图 :T2K\@  
14.2 DFT直接并行算法 -v] 0@jNe  
    SIMD-MT上的并行DFT算法(略) EBm\rM8  
14.3 并行FFT算法 Ff30%  
    SIMD-MC上的FFT算法(略) N !:&$z-  
    SIMD-BF上的FFT算法及其时间分析 =n!8>8d  
Ch15 图论算法 Q_S fFsY  
15.1 图的并行搜索 6|9fcIh]B  
    p-深度优先搜索及其计算示例 UNJ|J$T]  
    p-宽深优先搜索及其计算示例 $: -Ptm@  
    p-宽度优先搜索及其计算示例 .u)YZN0\  
15.2 图的传递闭包 Z|.. hZG  
    基于布尔矩阵乘积的算法原理 Z(FAQ\7  
    计算示例 8u4]@tJ H  
    SIMD-CC上的传递闭包算法 uG<+IT|x  
15.3 图的连通分量 MLJ8m  
    基于传递闭包的算法 RV~w+%f  
    基于顶点合并的算法 u
AJC Q)@  
15.4 图的最短路径 {=kA8U  
    基于矩阵乘积的算法原理 v^pE=f*/  
    计算示例 cCwT0O#d  
15.5 图的最小生成树 ^I^
k4iw4  
    SIMD-EREW模型上的Prim算法 6sntwT"?  
    算法的时间分析 nHhg#wR  
Ch18 随机算法 "8N]1q:$4  
18.1 引言 v{I:Wxe  
    基本知识：随机算法的定义、分类、重复性定律 IV\@GM:ait  
    时间复杂性度量 y8sI @y6  
    设计方法 =|6IyL_N  
18.2 低度顶点部分独立集 -y~JNDS1]  
    串行算法 ,
30&VW##  
    随机并行算法及其正确性证明 4Hu.o7  
18.5 多项式恒等的验证 o] = &  
    基本原理和方法 3)=$BSC%  
    矩阵乘积的验证原理 1=s%.0  
18.8 格点逼近问题(略) Lz4iLLP  
18.9 SAT问题的异步随机并行算法(略) 4bmp
MF-  
Ch20 模型与下界 #<)u%)`  
20.1不同的PRAM模型的相互模拟 W}KtB1J  
    PRAM-EREW模拟PPRAM-CRCW  N3E=t#n  
    PRAM-CRCW之间的模拟 Lq yY??\@  
20.2下界 DS^P Hk39  
    算法研究的两个方向：优化（上界）、可能性（下界） W8\K_M}  
    Gates的工作 ( CEJg|,  
    理想的PRAM模型与下界 ybfNG@N*  
    PRAM模型的下界
%c [by  
20.3 NP完全理论导引(略) RTSg=   
20.4 P完全理论(略)