资源描述：
《《算法设计与分析》复习提纲 201016.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《并行算法》课程总结与复习2020.05.28Ch1绪论1.1并行计算机体系结构Ø并行计算机的分类§SISD,SIMD,MISD,MIMD；§SIMD,PVP,SMP,MPP,COW,DSMØ并行计算机的互连方式§静态：LA(LC),MC,TC,MT,HC,BC,SE§动态：Bus,CrossbarSwitcher,MIN(MultistageInterconnectionNetworks)1.2并行计算模型ØPRAM模型：SIMD-SM，又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREWØSIMD-IN模型：SIMD-DMØ异步A
2、PRAM模型：MIMD-SMØBSP模型：MIMD-DM，块内异步并行，块间显式同步ØLogP模型：MIMD-DM，点到点通讯1.3并行算法的基础知识和性能分析Ø并行算法的定义Ø并行算法的表示Ø并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量及工作量最优Ø并行算法的WT表示：Brent定理Ø加速比性能定律(略)Ø并行算法的同步和通讯(略)Ch2设计技术2.1并行算法的三种基本设计方法及其代表实例2.2基本设计技术Ø平衡树方法：求最大值、计算前缀和Ø倍增技术：表序问题、求森林的根Ø分治策略：FFT分治算法Ø划分原理：均匀划
3、分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分((m,n)-选择)Ø流水线技术：五点的DFT计算，Systolic算法Ø加速级联Ø破对称技术Ch3前缀计算（略）Ch4排序和选择网络（略）4.1Batcher归并和排序Ø0-1原理的证明(略)Ø奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数)Ø双调归并网络：计算流程和复杂性(比较器个数和延迟级数)ØBatcher排序网络：原理、种类和复杂性4.2(m,n)-选择网络Ø分组选择网络Ø平衡分组选择网络及其改进Ch5排序和选择算法（略）5.1一维线性阵列上的并行
4、排序算法5.2二维Mesh上的并行排序算法ØShearSort排序算法ØThompson&Kung双调排序算法及其计算示例5.3Stone双调排序算法(略)5.4Akl并行k-选择算法：计算模型、时间分析5.5Valiant并行归并算法：计算模型、时间分析5.7Preparata并行枚举排序算法：计算模型和算法的复杂度Ch7并行搜索（略）7.1单处理器上的搜索(略)7.2SIMD共享存储模型上有序表的搜索：算法7.3SIMD共享存储模型上随机序列的搜索：算法7.4树连接的SIMD模型上随机序列的搜索：算法7.5网孔连接的SIMD模型上随机序列的搜索：算
5、法和计算示例Ch8选路算法8.1引言Ø信包传输性能参数Ø维序选路(X-Y选路、E-立方选路)Ø选路模式及其传输时间公式8.2单一信包一到一传输SF和CT传·输模式的传输时间(一维环、带环绕的Mesh、超立方)8.3一到多播送SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法8.4多到多播送SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法8.5贪心算法(教材8.2)（略）Ø二维阵列上的贪心算法Ø蝶形网上的贪心算法8.6随机和确定的选路算法(教材8.3)（略）Ch12矩阵运算12.1矩阵的划分：带状划分和棋
6、盘划分，有循环的带状划分和棋盘划分12.2矩阵转置：网孔和超立方连接的算法及其时间分析12.3矩阵向量乘法Ø带状划分的算法及其时间分析Ø棋盘划分的算法及其时间分析ØSystolic算法12.4矩阵乘法Ø简单并行分块算法ØCannon算法及其计算示例ØFox算法及其计算示例ØDNS算法及其计算示例ØSystolic算法Ch13数值计算13.1稠密线性方程组求解ØSIMD-CREW的上三角方程组回代算法ØSIMD-CREW上的Gauss-Jordan算法ØMIMD-CREW上的Gauss-Seidel算法13.2稀疏线性方程组的求解Ø三对角方程组的奇偶规约
7、求解法ØGauss-Seidel迭代法的红黑着色并行算法13.3非线性方程的求根Ch14快速傅立叶变换FFT14.1快速傅里叶变换(FFT)Ø离散傅里叶变换(DFT)Ø串行FFT分治递归算法及其计算原理Ø串行FFT蝶式递归计算及其蝶式计算流图14.2DFT直接并行算法ØSIMD-MT上的并行DFT算法(略)14.3并行FFT算法ØSIMD-MC上的FFT算法(略)ØSIMD-BF上的FFT算法及其时间分析Ch15图论算法15.1图的并行搜索Øp-深度优先搜索及其计算示例Øp-宽深优先搜索及其计算示例Øp-宽度优先搜索及其计算示例15.2图的传递闭包Ø基
8、于布尔矩阵乘积的算法原理Ø计算示例ØSIMD-CC上的传递闭包算法15.3图的连通分量Ø基于传
