查看完整版本: [-- 中国科学技术大学并行算法期末考试范围 --]

考博论坛 -> 考博见面礼 -> 中国科学技术大学并行算法期末考试范围 [打印本页] 登录 -> 注册 -> 回复主题 -> 发表主题

diverxu 2008-10-29 20:13

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

《并行算法》课程总结与复习 Tl/!Dn  
Ch1 并行算法基础 d[( }  
1.1 并行计算机体系结构 _`Lv@T.  
    并行计算机的分类 _Qh :*j!  
    SISD,SIMD,MISD,MIMD； z\F#td{r  
    SIMD,PVP,SMP,MPP,COW,DSM 5w^6bw){  
    并行计算机的互连方式 LtK= nK  
    静态：LA(LC),MC,TC,MT,HC,BC,SE `<oNEr+#  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) $eSSW+8q"  
1.2 并行计算模型 !:^?GN#~x  
    PRAM模型：SIMD-SM， vB <2f*U  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW J^y}3ON  
    SIMD-IN模型：SIMD-DM aS  $ J `  
    异步APRAM模型：MIMD-SM m|by^40A(  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 Tu[I84  
    LogP模型：MIMD-DM，点到点通讯 N"zg)MsX  
1.3 并行算法的一般概念 j8cXv  
    并行算法的定义 ZR[6-  
    并行算法的表示 :T9 P9<  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 N'@E^ rYc  
    并行算法的WT表示：Brent定理、WT最优 tso\bxiU  
    加速比性能定律(略) ]*&`J4i  
    并行算法的同步和通讯(略) %8hx3N8>  
Ch2 并行算法的基本设计技术 2E$K='H:,  
2.1 并行算法的三种基本设计方法 Co^^rd@  
2.2 基本设计技术 G5T(  
    平衡树方法：求最大值、计算前缀和  JE=3V^k  
    倍增技术：表序问题、求森林的根 M/5+AsT  
    分治策略：FFT分治算法 I*`;1+`  
    划分原理： HbZFL*2x3  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) iQ8T3cC+  
    流水线技术：五点的DFT计算，Systolic算法 3[ cGSI"+  
    加速级联(略) hx$b Y  
    破对称技术 y py  
Ch3 比较器网络上的排序和选择算法 F['%?+<3  
3.1 Batcher归并和排序 ('oA{,#L  
    0-1原理的证明(略) Y$<p_X,  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) r=cm(AHF  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) E(miQ   
    Batcher排序网络：原理、种类和复杂性 {osadXd C  
3.2 (m, n)-选择网络 ,b,t^xX>)  
    分组选择网络 q!Q*T^-rO  
    平衡分组选择网络及其改进 ]wHXrB8vx  
Ch4 排序和选择的同步算法 w%uM=YmuT  
4.1 一维线性阵列上的并行排序算法(略) I/k/5  
4.2 二维Mesh上的并行排序算法 |576)  
    ShearSort排序算法 s#4Q?<65u  
    Thompson&Kung双调排序算法及其计算示例 n^2'O:V s  
4.3 Stone双调排序算法(略)  BRF4 p:  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 Rwe!xY^d8  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 \o<&s{ 6L  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 0fAo&B  
Ch5 排序和选择的异步和分布式算法(略) N D1'XCN  
5.1 MIMD-CREW模型上的异步枚举排序算法 >7(7  
5.2 MIMD-TC模型上的异步快排序算法 fIii  
5.3分布式k-选择算法 @ev8"JZ1  
Ch6 并行搜索 3dB{DuQ  
6.1 单处理器上的搜索(略) 39oI &D>8  
6.2 SIMD共享存储模型上有序表的搜索：算法 / 0y 5/  
6.3 SIMD共享存储模型上随机序列的搜索：算法 (&oT6Ji  
6.4 树连接的SIMD模型上随机序列的搜索：算法 dhmrh5Uf  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 3fq'<5 ^  
Ch8 数据传输与选路 hO..j  
8.1 引言 TSKR~3D#  
    信包传输性能参数 XT{o ]S~nq  
    维序选路(X-Y选路、E-立方选路) sZ%wQqy~k  
    选路模式及其传输时间公式 \$Aw[ 5&t  
8.2 单一信包一到一传输 .v[!_bk8C  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) ^y2}C$1V  
8.3 一到多播送 =0mXTY1  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 F:'>zB]-}  
8.4 多到多播送 ~'t+X  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 =:(<lKf,<F  
8.5 贪心算法(书8.2) `(VVb@:o  
    二维阵列上的贪心算法 M(#]NTr ~4  
    蝶形网上的贪心算法 (k24j*1e$  
8.6 随机和确定的选路算法(书8.3)(略) 0s%]%2O N  
Ch12矩阵运算 ?RU_SCp-  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 2hFOwI  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 ydf;g5OZ  
12.3 矩阵向量乘法 ?Y'r=Q{w  
    带状划分的算法及其时间分析 %)PQomn?  
    棋盘划分的算法及其时间分析 $X]Z-RCK3  
    Systolic算法(略) 0&2eiMKG?n  
12.4 矩阵乘法 +YnQOh%v0s  
    简单并行分块算法 &d&nsQ  
    Cannon算法及其计算示例 L; 'C5#GN  
    Fox算法及其计算示例 _NB8>v  
    DNS算法及其计算示例  !AFii:#  
    Systolic算法(略) B+2Jea,N  
Ch13 数值计算 N3o kN8d  
13.1 稠密线性方程组求解 ;7bY>zc(w  
    SIMD-CREW的上三角方程组回代算法 ^9 {r2d&c  
    SIMD-CREW上的Gauss-Jordan算法 <hzuPi@  
    MIMD-CREW上的Gauss-Seidel算法 &T[BS;  
13.2 稀疏线性方程组的求解 HFTDea+#  
    三对角方程组的奇偶规约求解法 T[]kun  
    Gauss-Seidel迭代法的红黑着色并行算法 O*-sSf   
13.3 非线性方程的求根(略) jWJ/gv~ $  
Ch14 快速傅立叶变换FFT e 3x;(@j  
14.1 快速傅里叶变换(FFT) gfm aO ]  
    离散傅里叶变换(DFT) r!HB""w  
    串行FFT递归算法及其计算原理 kq=tL@W`0}  
    串行FFT蝶式计算及其蝶式计算流图 GN ?1dwI  
14.2 DFT直接并行算法 (]*!`(_b  
    SIMD-MT上的并行DFT算法(略) C 8q VYrw  
14.3 并行FFT算法 Y~uqKb;A  
    SIMD-MC上的FFT算法(略) u(P;) E"1  
    SIMD-BF上的FFT算法及其时间分析 z{dn   
Ch15 图论算法 \|q.M0  
15.1 图的并行搜索 aIABx!83>  
    p-深度优先搜索及其计算示例 DU.[Sp  
    p-宽深优先搜索及其计算示例 +Y|HO[  
    p-宽度优先搜索及其计算示例 7Vxe] s  
15.2 图的传递闭包 h2C1'+Q{9  
    基于布尔矩阵乘积的算法原理 W9ewj:4\0  
    计算示例 xr\wOQ*`  
    SIMD-CC上的传递闭包算法 =#c?g Wb56  
15.3 图的连通分量 N}2xt)JZz  
    基于传递闭包的算法 RU^lR8;  
    基于顶点合并的算法 |.zotEh  
15.4 图的最短路径 y~N,=5>j  
    基于矩阵乘积的算法原理 #Ua+P(1q  
    计算示例 'ehJr/0&g  
15.5 图的最小生成树 `y!6(xI  
    SIMD-EREW模型上的Prim算法 { !C';^  
    算法的时间分析 Eb<iR)e H=  
Ch18 随机算法  } Rc8\,  
18.1 引言 vZns,K#4H\  
    基本知识：随机算法的定义、分类、重复性定律 6QOdd 6_d  
    时间复杂性度量 K"sfN~@rT[  
    设计方法 *L9s7RR  
18.2 低度顶点部分独立集 t;@VsQ8  
    串行算法 |WB<yA1  
    随机并行算法及其正确性证明 .FnO  
18.5 多项式恒等的验证 Aghcjy|j  
    基本原理和方法 :I5]|pt  
    矩阵乘积的验证原理 rZy38Wo  
18.8 格点逼近问题(略) 3d.JV'C'c  
18.9 SAT问题的异步随机并行算法(略) cf|<~7  
Ch20 模型与下界 6?0 ^U 9  
20.1不同的PRAM模型的相互模拟 "9 -duDg  
    PRAM-EREW模拟PPRAM-CRCW byv(:xk|'e  
    PRAM-CRCW之间的模拟 @$~ BU;kR  
20.2下界 'r%`(Z{~  
    算法研究的两个方向：优化（上界）、可能性（下界） x,js}Mlw  
    Gates的工作 7;C9V`  
    理想的PRAM模型与下界 Wx&AY"J  
    PRAM模型的下界 q phN   
20.3 NP完全理论导引(略) WIo^=?%  
20.4 P完全理论(略)


查看完整版本: [-- 中国科学技术大学并行算法期末考试范围 --] [-- top --]


Powered by freekaobo v7.5 SP3 Code ©2003-2010 PHPWind
Gzip enabled

You can contact us