实验一全排列、快速排序
【实验目的】
1. 掌握全排列的递归算法。
2. 了解快速排序的分治算法思想。
【实验原理】
一、全排列
全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n个数字的排列为例说明排列的生成法。
n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从 它 的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。
二、快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
【实验内容】
１.全排列递归算法的实现。
２.快速排序分治算法的实现。
【实验结果】
１. 全排列：
２. 快速排序：
实验二 最长公共子序列、活动安排问题
【实验目的】
１. 了解动态规划算法设计思想，运用动态规划算法实现最长公共子序列问题。
２. 了解贪心算法思想，运用贪心算法设计思想实现活动安排问题。
【实验原理】
一、动态规划法解最长公共子序列
设序列X=
i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
iii. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=
最长公共子序列问题具有最优子结构性质。
由最长公共子序列问题的最优子结构性质可知，要找出X=
二、贪心法解活动安排问题
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
【实验内容】
１.动态规划算法的实现。
２.贪心算法的实现。
【实验结果】
１. 最长公共子序列：
２.活动安排：
实验三回溯法解n后问题、０-１背包问题
【实验目的】
１．了解回溯算法设计思想，并运用回溯算法实现n后问题和０-１背包问题。
【实验原理】
一、回溯法解n后问题
先选择某一可能的线索进行试探，每一步试探都有多种方式，将每一方式都以一试探。如有问题就返回纠正，反复进行这种试探再返回纠正，直到得出全部符合条件的答案或是问题无解为止。
二、0-1背包问题
用回溯法解问题时，应明确定义问题的解空间，问题的解空间应至少包含问题的一个(最优)解。定义了问题的解空间后，还应将解空间很好地组织起来，使得能用回溯法方便地搜索整个解空间。通常将解空间组织成树或图的形式。
确定了解空间的组织结构后，回溯法从开始结点(根结点)出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展节点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
【实验内容】
１.n后问题的实现。
２.０-１背包问题的实现。
【实验结果】
1. N后问题：
2. ０-１背包问题：
实验四随机投点法计算π值
【实验目的】
１.了解随机算法设计思想，并运用随机算法计算π的值。
【实验原理】
设有一半径为r的圆及其外切四边形，如图所示。向该正方形随机地投掷n个电。设落入园内的点数为k。由于所投入的点再正方形上均匀分布，因而所投入的点落入圆内的概率为
。所以当n足够大时，k与n之就逼近这一概率，即
。从而π≈
。
【实验内容】
运用随机投点算法编程计算π的值。
【实验结果】
第二篇：并行计算-多媒体课件-并行算法设计与分析-课程总结与复习
《并行算法》课程总结与复习
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 多项式恒等的验证
基本原理和方法 矩阵乘积的验证原理