并行计算-多媒体课件-并行算法设计与分析-ch18

1、2022/8/12Y.Xu Copyright USTC主要内容18.1 引言 - 基本知识 - 时间复杂性度量 - 设计方法18.2 低度顶点部分独立集 - 串行算法 - 随机并行算法18.5 多项式恒等的验证 - 基本技术 - 矩阵乘积的验证2022/8/12Y.Xu Copyright USTC18.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/8/12Y.Xu Copyright USTC18.1 引言18.1.1 基本知识 2.背景和历史 (1)重要方法 - Monte Carlo求定积分法 - 随机k-选择算法 - 随机快排序 -素性判定的随机算法 - 二阶段随机路由算法 (2)重要人物和工作 - de Leeuw等人提出了概率图灵机(1955) - Jo

3、hn Gill的随机算法复杂性理论(1977) - Rabin的数论和计算几何领域的工作(1976) - Karp的算法概率分析方法(1985) - Shor的素因子分解量子算法(1994)2022/8/12Y.Xu Copyright USTC18.1 引言18.1.1 基本知识 3.随机算法的分类 - Las Vegas算法和Monte Carlo算法是常见的两类随机算法。 - Las Vegas算法运行结束时总能给出正确的解，但其运行时 间每次有所不同。 - Monte Carlo算法可能得到不正确的结果，但这种概率是小 的且有界的。 2022/8/12Y.Xu Copyright US

4、TC18.1 引言18.1.1 基本知识 4.研究意义 - 求解问题的一种重要让步策略 - 有效的随机算法 - 实际可行的随机算法 - 可转化为确定算法 - 易于并行化 - 促进智能计算的发展2022/8/12Y.Xu Copyright USTC18.1 引言18.1.2 时间复杂性度量 1.运行时间的期望和方差 (1)实例的运行时间期望 对固定实例x, 设随机算法A的运行时间 是一个0,+)上的随机变量, 定义随机算法A在实例x上的运行时间期望为 , 也称为随机算法A在实 例x上的执行时间. (2)算法的运行时间期望 如果对一个规模为n问题的所有实例是均匀选取的, 则定义各个实例上 的平均

5、执行时间为随机算法在该问题上的运行时间期望, 记为T(n) 注: 类似地可以定义方差. 2.随机复杂度类(参见Motwani R. and Raghavan P., Randomized Algorithms.) RP(Randomized Polynomial time), ZPP, PP, BPP etc.2022/8/12Y.Xu Copyright USTC18.1 引言18.1.3 随机算法的设计方法 1.挫败对手(Foiling the Adversary) 将不同的算法组成算法群, 根据输入实例的不同随机地或有选择地选取 不同的算法, 以使性能达到最佳. 2.随机采样(Rando

6、m Sampling) 用“小”样本群的信息, 指导整体的求解. 3.随机搜索(Random Search) 是一种简单易行的方法, 可以从统计角度分析算法的平均性能, 如果将搜 索限制在有解或有较多解的区域, 可以大大提到搜索的成功概率. 4.指纹技术(Fingerprinting) 利用指纹信息可以大大减少对象识别的工作量. 通过随机映射的取指方 法, Karp和Rabin得到了一个快速的串匹配随机算法. 5.输入随机重组(Input Randomization) 对输入实例进行随机重组之后, 可以改进算法的平均性能. 2022/8/12Y.Xu Copyright USTC18.1 引言

7、18.1.3 随机算法的设计方法 6.负载平衡(Load Balancing) 在并行与分布计算、网络通讯等问题中, 使用随机选择技术可以达到任 务的负载平衡和网络通讯的平衡. 7.快速混合Markov链(Rapidly Mixing Markov Chain) 使用该方法可以解决大空间中的均匀抽样问题. 8.孤立和破对称技术(Isolation and Symmetry Breaking) 使用该技术可以解决处理的并行性, 避免分布式系统的死锁等问题. 如: 图着色算法, 部分独立集问题 9.概率存在性证明(Probabilistic Methods and Existence Proofs

8、) 如果随机选取的物体具有某种特性的概率大于0, 则具有该特性的物体一 定存在. 10.消除随机性(Derandomization) 许多优秀的确定性算法是由随机算法转换而来的.2022/8/12Y.Xu Copyright USTC18.1 引言18.1.4 随机算法举例: Quick Sort, Min Cut 1. Quick Sort(1)传统的快排序算法 -总是取第一个元素作为划分元； -算法的最坏运行时间是O(n2) ，平均时间是O(nlogn) ； -因此存在一些输入实例，使得算法达到最坏运行时间， 如：降序的序列；(2)随机快排序算法 -随机选择一个元素作为划分元； -任何一个

9、输入的期望时间是O(nlogn)； -是一个Las Vegas算法； 2022/8/12Y.Xu Copyright USTC18.1 引言 2. Min Cut(1)最小截问题定义： 给定一个无向图G(V,E)，找一个截(V1,V2)使得V1和V2间的连边数最小。(2)该问题可以用确定性算法（max-flow min-cut algorithm）在O(n2) 时间内完成。(3)随机算法 随机选一条边，将两顶点合一并除去顶点上的环； 直到图中只剩下两个顶点； 返回剩下两顶点间的连边数； (4)示例：#cut=2 15423541, 234, 51, 234, 51, 2, 32022/8/12

10、Y.Xu Copyright USTC18.1 引言 2. Min Cut(5)出错概率 重复k次出错概率为(6)本算法是一个Monte Carlo型算法.2022/8/12Y.Xu Copyright USTC18.1 引言18.1.5 相关概率知识 - 数学期望和方差 - Markov和Chebyshev不等式 - Chernoff不等式 设Xi是n个独立的Bernoulli随机变量, 对于1in, EXi=pi, 0pi1, 2022/8/12Y.Xu Copyright USTC主要内容18.1 引言 - 基本知识 - 时间复杂性度量 - 设计方法18.2 低度顶点部分独立集 - 串行

11、算法 - 随机并行算法18.5 多项式恒等的验证 - 基本技术 - 矩阵乘积的验证2022/8/12Y.Xu Copyright USTC18.2 低度顶点部分独立集18.2.1 串行算法 1.问题定义: 设G(V,E)是一个平面图. 顶点集合称为低度顶点部分独立集, 满足以下三个条件: (1)对 , deg(v)d常数; (2)集合X独立，即X中的任何两顶点都不相邻; (3)X的大小满足|X|c|v|，c为某个正常数. 2.引理18.1: 设G(V,E)是一个至少有三个顶点的平面图, 则|E|3|V|-6. 3.串行算法 - 定理18.6 对任何平面图G(V,E), 可以在线性时间内构造出低

12、度顶点部 分独立集. - 算法: 取 , d=6; 由Vd构造独立集: 反复取 加入到X中, 每次移去Vd中与v相连 的顶点, 直至Vd空; X就是所求;2022/8/12Y.Xu Copyright USTC18.2 低度顶点部分独立集18.2.2 并行算法 1.算法描述(算法18.2) 输入: 平面图G(V,E)的边表 输出: 低度顶点独立集X=vV| label(v)=1 begin (1)Par-do: 标出低度顶点Vd(deg(v)=6); (2)Par-do: 随机等概率分配所有vVd以标号0或1; /破对称技术 (3)Par-do: 剔除不满足独立性的标号为1的顶点; (4)剩下

13、的标号为1的低度顶点集就是所求的X; end 2022/8/12Y.Xu Copyright USTC18.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是顶点数. 考虑一个特殊的低度顶点子集VV6, 这里V中的任意两顶点之间的距 离至少为3, 下面只要证明|VX|以高概率满足条件

14、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/8/12Y.Xu Copyright USTC18.2 低度顶点部分独立集18.2.2 并行算法 2.算法分析 (1)算法的正确性 定理18.7的证明(续): 由于V中顶点的距离至少大于等于3, 可知随机变量Xi相互独立.

15、从X的生成过程知: EXi=PrviX(1/2)7 至此证明了条件3高概率成立. (2)算法时间: O(1), 使用了O(n)次运算.2022/8/12Y.Xu Copyright USTC主要内容18.1 引言 - 基本知识 - 时间复杂性度量 - 设计方法18.2 低度顶点部分独立集 - 串行算法 - 随机并行算法18.5 多项式恒等的验证 - 基本技术 - 矩阵乘积的验证2022/8/12Y.Xu Copyright USTC18.5 多项式恒等的验证18.5.1基本技术 1.原理 - 定理18.13 设p(x1,x2,xn)是域F上的多项式, 且p(x1,x2,xn)非恒等零, 若I是

16、F的任意有限子集, 则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/8/12Y.Xu Copyright USTC18.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=(u1,un)是AB