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

《并行算法》课程总结与复习 !ess.U&m'  
Ch1 并行算法基础 uJ -$i   
1.1 并行计算机体系结构 W/xPVmnV  
    并行计算机的分类 R|M]mwa^w  
    SISD,SIMD,MISD,MIMD； &Wcz~Gx3Q  
    SIMD,PVP,SMP,MPP,COW,DSM Ih|4I SI  
    并行计算机的互连方式 8R!-,I"$  
    静态：LA(LC),MC,TC,MT,HC,BC,SE n|&=6hiI  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) ,^8':X"A{!  
1.2 并行计算模型 IRx%L?  
    PRAM模型：SIMD-SM， ub-e
!{  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW 5%WAnh  
    SIMD-IN模型：SIMD-DM [YULvWAJ  
    异步APRAM模型：MIMD-SM j67ppt  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 Lk,q~  
    LogP模型：MIMD-DM，点到点通讯 |~ fI=1;;x  
1.3 并行算法的一般概念 ~S Bb2*ID  
    并行算法的定义 9;p5z[jI  
    并行算法的表示 M-i3_H)  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 >"bW'  
    并行算法的WT表示：Brent定理、WT最优 GkI'.  
    加速比性能定律(略) 1bQO:n):~  
    并行算法的同步和通讯(略) |YROxY"ML  
Ch2 并行算法的基本设计技术 !'^l}K>  
2.1 并行算法的三种基本设计方法 ial{A6X  
2.2 基本设计技术 rIcgf1v70  
    平衡树方法：求最大值、计算前缀和 ">.k 6Q  
    倍增技术：表序问题、求森林的根 Hq::F
?  
    分治策略：FFT分治算法 (Q=o9o:b  
    划分原理： -_t4A *  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) :Q("   
    流水线技术：五点的DFT计算，Systolic算法 .cJoNl'q  
    加速级联(略) LJ~#0Zu?  
    破对称技术 Rkg8  
Ch3 比较器网络上的排序和选择算法 JH]S'5X8K  
3.1 Batcher归并和排序 __9FQ{Ra  
    0-1原理的证明(略) %50)?J=zB  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) W.[!Q`  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) o{#aF=` {  
    Batcher排序网络：原理、种类和复杂性 8b'@_s!_  
3.2 (m, n)-选择网络 i;9X_?QF  
    分组选择网络 lM4Z7mT /  
    平衡分组选择网络及其改进 l%_K
$$C  
Ch4 排序和选择的同步算法 ugTsI~aE  
4.1 一维线性阵列上的并行排序算法(略) J";N^OR{A%  
4.2 二维Mesh上的并行排序算法 )TiM>{  
    ShearSort排序算法 &^#iS<s1  
    Thompson&Kung双调排序算法及其计算示例 njxLeDe-  
4.3 Stone双调排序算法(略) H5Eso*v@  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 J/e]
  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 1xS+r)_n@  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 3A`]Rk   
Ch5 排序和选择的异步和分布式算法(略) V5Z
C2H  
5.1 MIMD-CREW模型上的异步枚举排序算法 tIDN~[1  
5.2 MIMD-TC模型上的异步快排序算法 \:{K",2  
5.3分布式k-选择算法 uT,i&  
Ch6 并行搜索 ow9a^|@a  
6.1 单处理器上的搜索(略) uFSU|SDd.  
6.2 SIMD共享存储模型上有序表的搜索：算法 .kFO@:  
6.3 SIMD共享存储模型上随机序列的搜索：算法 Ed u(dZbKg  
6.4 树连接的SIMD模型上随机序列的搜索：算法 ].xSX0YQ%  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 W{'hn&vU  
Ch8 数据传输与选路 'u v=D  
8.1 引言 &P9fM-]b s  
    信包传输性能参数 \;N+PE  
    维序选路(X-Y选路、E-立方选路)  lFt!  
    选路模式及其传输时间公式 m0;j1-t  
8.2 单一信包一到一传输 xS_;p9{E  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) #d$zW4ur2  
8.3 一到多播送 QGfwvFm  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 hT-^ 1:N  
8.4 多到多播送 +'gO%^{l  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 M}[Q2v\  
8.5 贪心算法(书8.2) 8a8a:d  
    二维阵列上的贪心算法 !Q|aR  
    蝶形网上的贪心算法 9k71h`5  
8.6 随机和确定的选路算法(书8.3)(略) u=InE|SH  
Ch12矩阵运算 >xo<i8<Miv  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 :Y/aT[  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 GYQ:G=  
12.3 矩阵向量乘法 :'wxm3f  
    带状划分的算法及其时间分析 n+sv2Wv:  
    棋盘划分的算法及其时间分析 .B~yI3D`M  
    Systolic算法(略) rT4Q^t"  
12.4 矩阵乘法 ]'xci"qV`  
    简单并行分块算法 fpQFNV  
    Cannon算法及其计算示例 kum@cA  
    Fox算法及其计算示例 xSN;vrLHR  
    DNS算法及其计算示例 f91]0B`C  
    Systolic算法(略) A<c<!N  
Ch13 数值计算
Awfd0L;9  
13.1 稠密线性方程组求解 DD
mC3  
    SIMD-CREW的上三角方程组回代算法 =:g\I6'a  
    SIMD-CREW上的Gauss-Jordan算法 b&`~%f-   
    MIMD-CREW上的Gauss-Seidel算法 6 DQOar>d  
13.2 稀疏线性方程组的求解 [\Wl~ a l  
    三对角方程组的奇偶规约求解法 {91Y;p C  
    Gauss-Seidel迭代法的红黑着色并行算法 ^n~Kr1}nj  
13.3 非线性方程的求根(略) BK TTta1mY  
Ch14 快速傅立叶变换FFT .&b^6$dC  
14.1 快速傅里叶变换(FFT) GtmoFSZ  
    离散傅里叶变换(DFT) _)vX_gCi  
    串行FFT递归算法及其计算原理 4Wz1O$*  
    串行FFT蝶式计算及其蝶式计算流图 qdk!.A{  
14.2 DFT直接并行算法 |g{50r'=  
    SIMD-MT上的并行DFT算法(略) E^n!h06~G  
14.3 并行FFT算法 7n .A QII  
    SIMD-MC上的FFT算法(略) ).,twf58  
    SIMD-BF上的FFT算法及其时间分析 tlO=>  
Ch15 图论算法 5D/Td#T04  
15.1 图的并行搜索 Q3+%8zZI  
    p-深度优先搜索及其计算示例 CaCApL  
    p-宽深优先搜索及其计算示例 n>JJ Xw,,  
    p-宽度优先搜索及其计算示例 $U ._4  
15.2 图的传递闭包 gF9GU5T:  
    基于布尔矩阵乘积的算法原理 'U& ]KSzxv  
    计算示例 z
I9jxwXU  
    SIMD-CC上的传递闭包算法 Fi+DG?zu  
15.3 图的连通分量 |;V-;e*  
    基于传递闭包的算法 2@_3V_  
    基于顶点合并的算法 ]c_lNHssmq  
15.4 图的最短路径 #bGYHN  
    基于矩阵乘积的算法原理 lgt&kdc%o  
    计算示例 %eHr^j~w$  
15.5 图的最小生成树 'Eia=@  
    SIMD-EREW模型上的Prim算法 @CR<&^s5V  
    算法的时间分析 Pj56,qd>s  
Ch18 随机算法 &>.QDO  
18.1 引言 "<^ Vp
-7r  
    基本知识：随机算法的定义、分类、重复性定律 A0.xPru1p  
    时间复杂性度量 k%-y\WM  
    设计方法 7]5+%[Dg!  
18.2 低度顶点部分独立集 ]*$o qn=m  
    串行算法 *mn9CVZ(}M  
    随机并行算法及其正确性证明 p8s%bPjK  
18.5 多项式恒等的验证 =RWY0|f  
    基本原理和方法 01aw+o  
    矩阵乘积的验证原理 o+^e+ptc  
18.8 格点逼近问题(略) ^LSD_R^N  
18.9 SAT问题的异步随机并行算法(略) G'HLnx}Yi  
Ch20 模型与下界 5M8   
20.1不同的PRAM模型的相互模拟 z __#PQ,n  
    PRAM-EREW模拟PPRAM-CRCW NX
OvC!<  
    PRAM-CRCW之间的模拟 2gvS`+<TP  
20.2下界 @[/!e`]+  
    算法研究的两个方向：优化（上界）、可能性（下界） )5<dmK@  
    Gates的工作 Ex}TDmTu  
    理想的PRAM模型与下界 _ -ec(w~/  
    PRAM模型的下界 2<2a3'pG  
20.3 NP完全理论导引(略) hL;??h,!_  
20.4 P完全理论(略)