《并行算法》课程总结与复习

Ch1 并行算法基础

1.1 并行计算机体系结构

并行计算机的分类

SISD,SIMD,MISD,MIMD；

SIMD,PVP,SMP,MPP,COW,DSM

并行计算机的互连方式

静态：LA(LC),MC,TC,MT,HC,BC,SE

动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks)

1.2 并行计算模型

PRAM模型：SIMD-SM，

又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW

SIMD-IN模型：SIMD-DM

异步APRAM模型：MIMD-SM

BSP模型：MIMD-DM，块内异步并行，块间显式同步

LogP模型：MIMD-DM，点到点通讯

1.3 并行算法的一般概念

并行算法的定义

并行算法的表示

并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 并行算法的WT表示：Brent定理、WT最优

加速比性能定律

并行算法的同步和通讯

Ch2 并行算法的基本设计技术

基本设计技术

平衡树方法：求最大值、计算前缀和

倍增技术：表序问题、求森林的根

分治策略：FFT分治算法

划分原理：

均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-

选择 )

流水线技术：五点的DFT计算

Ch3 比较器网络上的排序和选择算法

3.1 Batcher归并和排序

0-1原理的证明

奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数)

双调归并网络：计算流程和复杂性(比较器个数和延迟级数)

Batcher排序网络：原理、种类和复杂性

3.2 (m, n)-选择网络

分组选择网络

平衡分组选择网络及其改进

Ch4 排序和选择的同步算法

4.1 一维线性阵列上的并行排序算法

4.2 二维Mesh上的并行排序算法

ShearSort排序算法

Thompson&Kung双调排序算法及其计算示例

4.3 Stone双调排序算法

4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析

4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析

4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度

Ch5 排序和选择的异步和分布式算法

5.1 MIMD-CREW模型上的异步枚举排序算法

5.2 MIMD-TC模型上的异步快排序算法

5.3分布式k-选择算法

Ch6 并行搜索

6.1 单处理器上的搜索

6.2 SIMD共享存储模型上有序表的搜索：算法

6.3 SIMD共享存储模型上随机序列的搜索：算法

6.4 树连接的SIMD模型上随机序列的搜索：算法

6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例

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 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 矩阵转置：网孔和超立方连接的算法及其时间分析

12.3 矩阵向量乘法

带状划分的算法及其时间分析

棋盘划分的算法及其时间分析

12.4 矩阵乘法

简单并行分块算法

Cannon算法及其计算示例

Fox算法及其计算示例

DNS算法及其计算示例

Systolic算法

Ch13 数值计算

13.1 稠密线性方程组求解

SIMD-CREW的上三角方程组回代算法

SIMD-CREW上的Gauss-Jordan算法

MIMD-CREW上的Gauss-Seidel算法

13.2 稀疏线性方程组的求解

三对角方程组的奇偶规约求解法

Gauss-Seidel迭代法的红黑着色并行算法 13.3 非线性方程的求根

Ch14 快速傅立叶变换FFT

14.1 快速傅里叶变换(FFT)

离散傅里叶变换(DFT)

串行FFT递归算法及其计算原理

串行FFT蝶式计算及其蝶式计算流图

14.2 DFT直接并行算法

SIMD-MT上的并行DFT算法

14.3 并行FFT算法

SIMD-MC上的FFT算法

SIMD-BF上的FFT算法及其时间分析

Ch15 图论算法

15.1 图的并行搜索

p-深度优先搜索及其计算示例

p-宽深优先搜索及其计算示例

p-宽度优先搜索及其计算示例

15.2 图的传递闭包

基于布尔矩阵乘积的算法原理

计算示例

SIMD-CC上的传递闭包算法

15.3 图的连通分量

基于传递闭包的算法

基于顶点合并的算法

15.4 图的最短路径

基于矩阵乘积的算法原理

计算示例

15.5 图的最小生成树

SIMD-EREW模型上的Prim算法

算法的时间分析

Ch17组合搜索

17.1 基于分治法的与树搜索

与树并行搜索过程

处理器数目与搜索效率关系

17.2 基于分枝限界法的或树搜索

串行分枝限界法

示例: 0-1背包问题,8-谜问题及其搜索算法的并行化 TSP问题的分枝限界算法及其并行化

Ch18 随机算法

18.1 引言

基本知识：随机算法的定义、分类

时间复杂性度量

设计方法

18.2 低度顶点部分独立集

串行算法

随机并行算法及其正确性证明

18.5 多项式恒等的验证

基本原理和方法 矩阵乘积的验证原理

 

第二篇：算法设计与分析总结

第一章 绪论

1、重要特性

1.输入

2.输出

3.有穷性

4.确定性

5.可行性

2、描述算法的方法

1.自然语言：优点是直观易懂，缺点是容易出现二义性

2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言

3.程序设计语言：优点是计算机直接运行，缺点是抽象性差

4.伪代码：

3、递归算法分析

1.猜测技术

2.扩展递归技术

3.通用分治递归推式

第二章 NP完全理论

第三章 蛮力法

3.1 蛮力法的设计思想

蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;

关键——依次处理所有元素。

3.2 查找问题中的蛮力法

3.2.1 顺序查找O(n)

3.2.2串匹配问题

BF O(n*m)

BMP O(n+m)

BM O(n*m)

3.3 排序问题中的蛮力法

3.3.1 选择排序O(n²)

3.3.2 起泡排序O(n²)

3.4 组合问题中的蛮力法

3.4.1 生成排列对象O(n!)

3.4.2 生成子集O(2ⁿ)

3.4.3 0/1背包问题O(2ⁿ)

3.4.4 任务分配问题O(n!)

3.5 图问题中的蛮力法

3.5.1 哈密顿回路问题O(n!)

3.5.2 TSP问题O(n!)

3.6 几何问题中的蛮力法

3.6.1 最近对问题O(n²)

3.6.2 凸包问题O(n³)

3.7 实验项目——串匹配问题

第四章 分治法

4.1 分治法的设计思想

设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

步骤：（1）划分（2）求解子问题（3）合并

4.2 排序问题中的分治法

4.2.1 递归排序O(nlog₂n)

4.2.2 快速排序O(nlog₂n)

4.3 组合问题中的分治法

4.3.1 最大字段和问题O(nlog₂n)

4.3.2棋盘覆盖问题O(4^k)

4.3.3 循环赛日程安排问题O(4^k)

4.4 几何问题中的分治法

4.4.1 最近对问题O(nlog₂n)

4.4.2 凸包问题O(nlog₂n)

4.5 实验项目——最近对问题

第五章 减治法

5.1 减治法的设计思想

原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。

5.2 查找问题中的减治法

5.2.1 折半查找O(log₂n)

5.2.2 二叉查找树O(log₂n)

5.3 排序问题中的减治法

5.3.1 堆排序O(log₂n)

5.3.2 选择问题O(log₂n)

5.4 组合问题中的减治法

5.4.1 淘汰塞冠军问题O(n)

5.4.2 假币问题O(log₂n)

5.5 实验项目——8枚硬币问题

第六章 动态规划法

6.1动态规划法的设计思想

将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。

步骤：

将原始问题分解为相互重叠的子问题，确定动态规划函数；

求解子问题，填表；

根据表，自底向上计算出原问题的解。

6.2 图问题中的动态规划法

6.2.1 TSP问题O(2ⁿ)

6.2.2 多段图的最短路径问题O(n+m)

6.3 组合问题中的动态规划法

6.3.1  0/1背包问题O(n*C)

6.3.2 最长公共子序列问题O(n*m)

 .

6.4 查找问题中的动态规划法

6.4.1 最优二叉查找树O(n^3)

6.4.2 近似串匹配问题

6.5 实验项目——最大子段和问题

第七章 贪心法

7.1 贪心法的设计思想

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。

贪心法的关键在于决定贪心策略。

7.2 图问题中的贪心法

7.2.1 TSP问题O(2ⁿ)

7.2.2 图着色问题

7.2.3 最小生成树问题O(2ⁿ)

7.3 组合问题中的贪心法

7.3.1 背包问题O(nlog₂n)

7.3.2 活动安排问题O(nlog₂n)

7.3.3 多机调度问题O(n*m)

7.4 实验项目——哈夫曼编码

第八章 回溯法

8.1 回溯法的设计思想

从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。

步骤：

确定解向量和分量的取值范围，构造解空间树；

确定剪枝函数；

对解空间树按深度优先搜索，搜索过程中剪枝；

从所有的可能解中确定最优解。

8.2 图问题中的回溯法

8.2.1 图着色问题

8.2.2 哈密顿回路问题

8.3 组合问题中的回溯法

8.3.1 八皇后问题

8.3.2 批处理作业调度问题

8.4 实验项目——0/1背包问题

第九章 分支界限法

9.1 分支限界法的设计思想

1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] ，并确定限界函数；

2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；

3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；

4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；

5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。

步骤：

确定解空间树

确定限界函数

按广度优先搜索解空间树，计算限界函数的值，填入PT表

从PT表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。

9.2 图问题中的分支限界法

9.2.1 TSP问题

9.2.2 多段图的最短路径问题

9.3 组合问题中断饿分支限界法

9.3.1 任务分配问题

9.3.2 批处理作业调度问题

5

9.4 实验项目——电路布线问题

第十章 概率算法