MPI程序设计ch18

1、 Parallel Algorithms Chapter 18 Randomized Algorithms2022/7/16主要内容18.1 引言 - 基本知识 - 时间复杂性度量 - 设计方法18.2 低度顶点部分独立集 - 串行算法 - 随机并行算法18.5 多项式恒等的验证 - 基本技术 - 矩阵乘积的验证2022/7/1618.1 引言18.1.1 基本知识 1.随机算法的定义 - 定义: 是一个概率图灵机. 也就是在算法中引入随机因素, 即通过随机数选择算法的下一步操作. - 三要素: 输入实例、随机源和停止准则. - 特点: 简单、快速和易于并行化. - 一种平衡: 随机算法可以理

2、解为在时间、空间和随机三大 计算资源中的平衡(Lu C.J. PhD Thesis 1999). - 重要文献 Motwani R. and Raghavan P., Randomized Algorithms. Cambridge University Press, New York, 19952022/7/1618.1 引言18.1.1 基本知识 2.背景和历史 (1)重要方法 - Monte Carlo求定积分法 - 随机k-选择算法 - 随机快排序 -素性判定的随机算法 - 二阶段随机路由算法 (2)重要人物和工作 - de Leeuw等人提出了概率图灵机(1955) - John G

3、ill的随机算法复杂性理论(1977) - Rabin的数论和计算几何领域的工作(1976) - Karp的算法概率分析方法(1985) - Shor的素因子分解量子算法(1994)2022/7/1618.1 引言18.1.1 基本知识 3.随机算法的分类 - Las Vegas算法和Monte Carlo算法是常见的两类随机算法。 - Las Vegas算法运行结束时总能给出正确的解，但其运行时 间每次有所不同。 - Monte Carlo算法可能得到不正确的结果，但这种概率是小 的且有界的。 2022/7/1618.1 引言18.1.1 基本知识 4.研究意义 - 求解问题的一种重要让步策

4、略 - 有效的随机算法 - 实际可行的随机算法 - 可转化为确定算法 - 易于并行化 - 促进智能计算的发展2022/7/1618.1 引言18.1.2 时间复杂性度量 1.运行时间的期望和方差 (1)实例的运行时间期望 对固定实例x, 设随机算法A的运行时间 是一个0,+)上的随机变量, 定义随机算法A在实例x上的运行时间期望为 , 也称为随机算法A在实 例x上的执行时间. (2)算法的运行时间期望 如果对一个规模为n问题的所有实例是均匀选取的, 则定义各个实例上 的平均执行时间为随机算法在该问题上的运行时间期望, 记为T(n) 注: 类似地可以定义方差. 2.随机复杂度类(参见Motwan

5、i R. and Raghavan P., Randomized Algorithms.) RP(Randomized Polynomial time), ZPP, PP, BPP etc.2022/7/1618.1 引言18.1.3 随机算法的设计方法 1.挫败对手(Foiling the Adversary) 将不同的算法组成算法群, 根据输入实例的不同随机地或有选择地选取 不同的算法, 以使性能达到最佳. 2.随机采样(Random Sampling) 用“小”样本群的信息, 指导整体的求解. 3.随机搜索(Random Search) 是一种简单易行的方法, 可以从统计角度分析算法的平

6、均性能, 如果将搜 索限制在有解或有较多解的区域, 可以大大提到搜索的成功概率. 4.指纹技术(Fingerprinting) 利用指纹信息可以大大减少对象识别的工作量. 通过随机映射的取指方 法, Karp和Rabin得到了一个快速的串匹配随机算法. 5.输入随机重组(Input Randomization) 对输入实例进行随机重组之后, 可以改进算法的平均性能. 2022/7/1618.1 引言18.1.3 随机算法的设计方法 6.负载平衡(Load Balancing) 在并行与分布计算、网络通讯等问题中, 使用随机选择技术可以达到任 务的负载平衡和网络通讯的平衡. 7.快速混合Mark

7、ov链(Rapidly Mixing Markov Chain) 使用该方法可以解决大空间中的均匀抽样问题. 8.孤立和破对称技术(Isolation and Symmetry Breaking) 使用该技术可以解决处理的并行性, 避免分布式系统的死锁等问题. 如: 图着色算法, 部分独立集问题 9.概率存在性证明(Probabilistic Methods and Existence Proofs) 如果随机选取的物体具有某种特性的概率大于0, 则具有该特性的物体一 定存在. 10.消除随机性(Derandomization) 许多优秀的确定性算法是由随机算法转换而来的.2022/7/161

8、8.1 引言18.1.4 随机算法举例: Quick Sort, Min Cut 1. Quick Sort(1)传统的快排序算法 -总是取第一个元素作为划分元； -算法的最坏运行时间是O(n2) ，平均时间是O(nlogn) ； -因此存在一些输入实例，使得算法达到最坏运行时间， 如：降序的序列；(2)随机快排序算法 -随机选择一个元素作为划分元； -任何一个输入的期望时间是O(nlogn)； -是一个Las Vegas算法； 2022/7/1618.1 引言 2. Min Cut(1)最小截问题定义： 给定一个无向图G(V,E)，找一个截(V1,V2)使得V1和V2间的连边数最小。(2)该

9、问题可以用确定性算法（max-flow min-cut algorithm）在O(n2) 时间内完成。(3)随机算法 随机选一条边，将两顶点合一并除去顶点上的环； 直到图中只剩下两个顶点； 返回剩下两顶点间的连边数； (4)示例：#cut=2 15423541, 234, 51, 234, 51, 2, 32022/7/1618.1 引言 2. Min Cut(5)出错概率 重复k次出错概率为(6)本算法是一个Monte Carlo型算法.2022/7/1618.1 引言18.1.5 相关概率知识 - 数学期望和方差 - Markov和Chebyshev不等式 - Chernoff不等式 设X

10、i是n个独立的Bernoulli随机变量, 对于1in, EXi=pi, 0pi1, 2022/7/16主要内容18.1 引言 - 基本知识 - 时间复杂性度量 - 设计方法18.2 低度顶点部分独立集 - 串行算法 - 随机并行算法18.5 多项式恒等的验证 - 基本技术 - 矩阵乘积的验证2022/7/1618.2 低度顶点部分独立集18.2.1 串行算法 1.问题定义: 设G(V,E)是一个平面图. 顶点集合称为低度顶点部分独立集, 满足以下三个条件: (1)对 , deg(v)d常数; (2)集合X独立，即X中的任何两顶点都不相邻; (3)X的大小满足|X|c|v|，c为某个正常数.

11、2.引理18.1: 设G(V,E)是一个至少有三个顶点的平面图, 则|E|3|V|-6. 3.串行算法 - 定理18.6 对任何平面图G(V,E), 可以在线性时间内构造出低度顶点部 分独立集. - 算法: 取 , d=6; 由Vd构造独立集: 反复取 加入到X中, 每次移去Vd中与v相连 的顶点, 直至Vd空; X就是所求;2022/7/1618.2 低度顶点部分独立集18.2.2 并行算法 1.算法描述(算法18.2) 输入: 平面图G(V,E)的边表 输出: 低度顶点独立集X=vV| label(v)=1 begin (1)Par-do: 标出低度顶点Vd(deg(v)=6); (2)P

12、ar-do: 随机等概率分配所有vVd以标号0或1; /破对称技术 (3)Par-do: 剔除不满足独立性的标号为1的顶点; (4)剩下的标号为1的低度顶点集就是所求的X; end 2022/7/1618.2 低度顶点部分独立集18.2.2 并行算法 2.算法分析 (1)算法的正确性 定理18.7 算法18.2产生的X=vV| label(v)=1就是一个低度顶点集, 使得 Pr|X|ne-n, 其中和为常数, n是顶点数. 证: 我们知道算法18.2产生的X满足低度顶点集的前两个条件, 现在只要证明 条件3高概率成立, 即Pr|X|ne-n, 其中和为常数, n是顶点数. 考虑一个特殊的低度

13、顶点子集VV6, 这里V中的任意两顶点之间的距 离至少为3, 下面只要证明|VX|以高概率满足条件3. V这样构造: 先任取v1V6, 删去V6中与v1距离小于2的顶点, 可知至多 删去36个顶点, 再从V6的剩余顶点中任取v2, 删去V6中与v2距离小于2的顶点, 可知至多删去36个顶点, 直至V6为空. V=v1,v2,. 因此, |V|(1/37)|V6|(1/37)(n/7)=cn c=1/259 (|Vd|c0|V|, c0=(d-5)/(d+1) 2022/7/1618.2 低度顶点部分独立集18.2.2 并行算法 2.算法分析 (1)算法的正确性 定理18.7的证明(续): 由于

14、V中顶点的距离至少大于等于3, 可知随机变量Xi相互独立. 从X的生成过程知: EXi=PrviX(1/2)7 至此证明了条件3高概率成立. (2)算法时间: O(1), 使用了O(n)次运算.2022/7/16主要内容18.1 引言 - 基本知识 - 时间复杂性度量 - 设计方法18.2 低度顶点部分独立集 - 串行算法 - 随机并行算法18.5 多项式恒等的验证 - 基本技术 - 矩阵乘积的验证2022/7/1618.5 多项式恒等的验证18.5.1基本技术 1.原理 - 定理18.13 设p(x1,x2,xn)是域F上的多项式, 且p(x1,x2,xn)非恒等零, 若I是F的任意有限子集

15、, 则In中有p(x1,x2,xn)的零元素数目|I|n-1deg(p), 其中deg(p)是多项式的阶. - 系18.3 令p(x1,x2,xn)0, 则随机元组(y1,y2,yn)In是p(x1,x2,xn)的 零元素的概率deg(p)/|I|. 2.测试多项式p(x1,x2,xn)是否恒为零的方法 先选择有限子集IF, 使|I|2deg(p); 随机选择vIn, 计算p(x1,x2,xn)|v; 如果p(x1,x2,xn)|v为零, 则p0;否则p不恒为零; 注: 该方法的错误概率1/2, 重复k次的错误概率(1/2)k2022/7/1618.5 多项式恒等的验证18.5.2 矩阵乘积的验证 1.问题: AnnBnn=Cnn ? 2.确定并行算法: 需要O(logn)时间, 进行了n3次乘积, 如DNS算法; 3.随机并行算法 (1)原理 - 引理18.7 设u为域F上的n维非零向量, 随机选择v0,1n, 则 i=1nuivi=0的概率1/2 - 定理18.14 随机产生v0,1n, 如果A(Bv)=Cv, 则AB=C; 否则ABC; 出错的概率至多为1/2. 证: 当AB=C时, 结论总是正确的; 当ABC时, 存在下标j, 使AB和C的第j行是不同的. 设u