资源描述：
《并行计算-多媒体课件-并行算法设计与分析-ch18 Randomized Algorithms.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、ParallelAlgorithmsChapter18RandomizedAlgorithms2021/7/27Y.XuCopyrightUSTC2021/7/27Y.XuCopyrightUSTC主要内容18.1引言-基本知识-时间复杂性度量-设计方法18.2低度顶点部分独立集-串行算法-随机并行算法18.5多项式恒等的验证-基本技术-矩阵乘积的验证2021/7/27Y.XuCopyrightUSTC18.1引言18.1.1基本知识1.随机算法的定义-定义:是一个概率图灵机.也就是在算法中引入随机因素,即通过随机数选择算法的下一步操作.-三要素:输入实例、随机源
2、和停止准则.-特点:简单、快速和易于并行化.-一种平衡:随机算法可以理解为在时间、空间和随机三大计算资源中的平衡(LuC.J.PhDThesis1999).-重要文献MotwaniR.andRaghavanP.,RandomizedAlgorithms.CambridgeUniversityPress,NewYork,19952021/7/27Y.XuCopyrightUSTC18.1引言18.1.1基本知识2.背景和历史(1)重要方法-MonteCarlo求定积分法-随机k-选择算法-随机快排序-素性判定的随机算法-二阶段随机路由算法(2)重要人物和工作-deL
3、eeuw等人提出了概率图灵机(1955)-JohnGill的随机算法复杂性理论(1977)-Rabin的数论和计算几何领域的工作(1976)-Karp的算法概率分析方法(1985)-Shor的素因子分解量子算法(1994)2021/7/27Y.XuCopyrightUSTC18.1引言18.1.1基本知识3.随机算法的分类-LasVegas算法和MonteCarlo算法是常见的两类随机算法。-LasVegas算法运行结束时总能给出正确的解，但其运行时间每次有所不同。-MonteCarlo算法可能得到不正确的结果，但这种概率是小的且有界的。2021/7/27Y.Xu
4、CopyrightUSTC18.1引言18.1.1基本知识4.研究意义-求解问题的一种重要让步策略-有效的随机算法-实际可行的随机算法-可转化为确定算法-易于并行化-促进智能计算的发展2021/7/27Y.XuCopyrightUSTC18.1引言18.1.2时间复杂性度量1.运行时间的期望和方差(1)实例的运行时间期望对固定实例x,设随机算法A的运行时间是一个[0,+∞)上的随机变量,定义随机算法A在实例x上的运行时间期望为,也称为随机算法A在实例x上的执行时间.(2)算法的运行时间期望如果对一个规模为n问题的所有实例是均匀选取的,则定义各个实例上的平均执行时间
5、为随机算法在该问题上的运行时间期望,记为T(n)注:类似地可以定义方差.2.随机复杂度类(参见MotwaniR.andRaghavanP.,RandomizedAlgorithms.)RP(RandomizedPolynomialtime),ZPP,PP,BPPetc.2021/7/27Y.XuCopyrightUSTC18.1引言18.1.3随机算法的设计方法1.挫败对手(FoilingtheAdversary)将不同的算法组成算法群,根据输入实例的不同随机地或有选择地选取不同的算法,以使性能达到最佳.2.随机采样(RandomSampling)用“小”样本群的
6、信息,指导整体的求解.3.随机搜索(RandomSearch)是一种简单易行的方法,可以从统计角度分析算法的平均性能,如果将搜索限制在有解或有较多解的区域,可以大大提到搜索的成功概率.4.指纹技术(Fingerprinting)利用指纹信息可以大大减少对象识别的工作量.通过随机映射的取指方法,Karp和Rabin得到了一个快速的串匹配随机算法.5.输入随机重组(InputRandomization)对输入实例进行随机重组之后,可以改进算法的平均性能.2021/7/27Y.XuCopyrightUSTC18.1引言18.1.3随机算法的设计方法6.负载平衡(Load
7、Balancing)在并行与分布计算、网络通讯等问题中,使用随机选择技术可以达到任务的负载平衡和网络通讯的平衡.7.快速混合Markov链(RapidlyMixingMarkovChain)使用该方法可以解决大空间中的均匀抽样问题.8.孤立和破对称技术(IsolationandSymmetryBreaking)使用该技术可以解决处理的并行性,避免分布式系统的死锁等问题.如:图着色算法,部分独立集问题9.概率存在性证明(ProbabilisticMethodsandExistenceProofs)如果随机选取的物体具有某种特性的概率大于0,则具有该特性的物体一定存在
8、.10.消
