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

1、y.xucopyrightustrc，2020/7/1，并行lalgorithmschapter 18随机分配，2020/7/1， y.xucopyrightustrc 18.1引言-基本知识-时间复杂度测量-设计方法18.2低度顶点部分独立集-串行算法-随机并行算法18.5多项式常数等的验证-基本技术-矩阵积的验证，2020/7/1，y.xu副本right 也就是说，在算法中引入了随机要素，一种平衡：随机算法可以理解为时间、空间、随机三种计算资源的平衡(LUC.j.phdinsis1999 )。 randomized algorithms.cambridgeuniversitypress，N

2、ew York，1995，2020/7/1，Y.Xu Copyright USTC， 18.1序言18.1.1基本知识2 .背景和历史(1)重要的方法蒙特卡洛法-随机k-选择算法-随机快速排序-特征判定的随机算法-两阶段随机路由算法(2)重要人物和工作- de Leeuw等人确定- John Gill随机算法复杂性理论(1977 ) -计算rabin的数学和几何区域的工作(1976) - Karp的算法概率分析方法(1985) - Shor的质因数分解量化算法(1994 )，2020/7/1，y.xucopyri 18.1引言，18.1.1基本知识3 .随机算法的分类- Las Vegas算法

3、和Monte Carlo算法是两种常见的随机算法。 - Las Vegas算法执行结束时总是给出正确的解，但执行时间每次都不同。 - Monte Carlo算法可能得到了错误的结果，但这个概率很小，有边界。、2020/7/1、Y.Xu Copyright USTC、18.1引言、18.1.1基本知识4 .研究意义-解决问题的重要让步策略-有效随机算法-实际可执行的随机算法-可转换为确定算法-容易并行化-知识1 Y.Xu Copyright USTC，18.1引言，18.1.2小时复杂度测定1 .执行时间的期待和方差(1)实例的执行时间的期待相对于固定实例x，随机算法a的执行时间为0， 上的随机

4、变量，定义随机算法a在实例x上的执行时间的期待(2)算法的执行时间，在对规模为n的问题的所有实例均等地选择的情况下，将各实例上的平均执行时间， 注释：期望作为随机算法在该问题上的运行时间，其类似地表示为分布式.2.随机复杂度类(Motwani R. and Raghavan P.)， 随机分配(RP )，ZPP，PP，BPP etc . 参照2020/7/1参照Y.Xu Copyright USTC，18.1引言，18.1.3随机算法的设计方法1 .挫折对象将不同的算法构成算法组， 根据输入实例的不同，随机或选择性地选择不同的算法以优化性能.2.用随机采样用的“小”抽样组的信息，指导整体的求解

5、.3.随机搜索以简单的方法，从统计的角度分析算法的平均性能如果把搜索限定在有解的区域或有很多解的区域的话，就可以大幅度地提到检索的成功概率.4.指纹技术利用指纹信息可以大幅度地减少对象识别的工作量.根据随机映射的指方法，Karp和Rabin可以实现高速的字符串匹配图取得的.5.输入随机化可在输入实例随机重新组织后改善算法的平均性能，2020/7/1、Y.Xu Copyright USTC、18.1引言、18.1.3随机算法的设计方法6 .负载平衡在网络通信等问题上，可以使用随机选择技术来实现任务负载平衡和网络通信之间的平衡.7.快速混合Markov链，使用此方法在大空间中实现均匀太阳可以使用该

6、技术来解决处理的并行性，并避免分布式系统的死锁等问题。 像：图的着色算法一样，部分独立集问题9 .概率存在性证明(probabilisticmethodsandexistenceproofs ) 随机选择的物体具有某个特性的概率大于0的情况下，一定存在具有该特性的物体. 10 .消除随机性(Derandomization )很多优秀的确定算法是从随机算法转换而来的. 2020/7/1，y.xu拷贝18.1.4随机算法示例： Quick Sort，Min Cut 1. Quick Sort (1)传统快速排序算法-总是以第一元素为分割源-算法的最差执行时间为O(n2 )，平均时间为O(nlogn )。 示例：降序序列(2)随机快速排序算法-随机选择元素作为划分元素-输入的期望时间是o (nlogn ) las Vegas算法，2020/7/1、Y.Xu Copyright USTC，18.1引言(2)这个问题可以用确定性算法在O(n2 )时间内完成。(3)随机算法随机选择边，将两个顶点设为一个，除去顶点上的环，返回图中只剩下两个顶点的剩馀两个顶点间的边数(4)例： # cut=2，2020/7/1，y.xucopyright