并行算法的设计与分析章

并行算法的设计与分析章第一页，共十五页，2022年，8月28日18.1随机算法的基本知识18.1.1概率论的基本知识18.1.2随机算法的概念、模型及其度量1.随机算法的概念定义:是一个概率图灵机.也就是在算法中引入随机因素,

即通过随机数选择算法的下一步操作.三要素:输入实例、随机源和停止准则.特点:简单、快速、易于并行化.一种平衡:随机算法可以理解为在时间、空间和随机三大计算资源中的平衡(LuC.J.,Ph.DThesis,1999).重要文献

MotwaniR.,RaghavanP.RandomizedAlgorithms.CambridgeUniversityPress,NewYork,1995第二页，共十五页，2022年，8月28日18.1随机算法的基本知识18.1.2随机算法的概念、模型及其度量2.随机算法的意义求解问题的一种重要让步策略：对某些问题，若要求其精确解，则设计出的算法的时间复杂度为指数级增长的，这样的算法在现实中不可行的。有效的随机算法实际可行的随机算法可转化为确定算法易于并行化促进智能计算的发展第三页，共十五页，2022年，8月28日18.1随机算法的基本知识18.1.2随机算法的概念、模型及其度量3.随机算法的重要应用MonteCarlo求定积分法.随机k-选择算法.随机快排序算法素数判定的随机算法二阶段随机路由算法.4.研究随机算法的重要人物及其工作deLeeuw等人提出了概率图灵机(1955)JohnGill的随机算法复杂性理论(1977)Rabin的数论和计算几何领域的工作(1976)Karp的算法概率分析方法(1985)Shor的大数素因子分解量子计算算法(1994)第四页，共十五页，2022年，8月28日18.1随机算法的基本知识18.1.2随机算法的概念、模型及其度量5.随机算法计算模型—随机PRAM模型（RandomizedPRAMModel,RPRAM)允许每个处理器在单步时间内产生某个范围的随机数。一个随机数在整数区间[1,2,…,m]内均等地取任一整数值。限定在单步时间内产生的随机数的位数为O(logn)，n为输入长度，以确保每个数据均能存储在一个存储单元中并可在O(1)顺序实现步内执行操作。假定p个处理器在同一时间步所产生的p个随机数彼此独立。6.随机算法的分类LasVegas算法和MonteCarlo算法是常见的两类随机算法。LasVegas算法运行结束时总能给出正确解，但其运行时间每次有所不同。

MonteCarlo算法每次运行结束时可能得到不正确的结果，但这种概率是很小的且有界。第五页，共十五页，2022年，8月28日18.1随机算法的基本知识18.1.2随机算法的概念、模型及其度量7.时间复杂性度量运行时间的期望实例的运行时间期望对固定实例x,设随机算法A的运行时间是一个[0,+∞)上的随机变量,

定义随机算法A在实例x上的运行时间期望为E[],也称为随机算法A在实例x上的执行时间.算法的运行时间期望如果对一个规模为n的问题的所有实例是均匀选取的,则定义各个实例上的平均执行时间为随机算法在该问题上的运行时间期望,记为T(n)

随机复杂度类(参见MotwaniR.,RaghavanP.,RandomizedAlgorithms.)RP(RandomizedPolynomialtime),etc.第六页，共十五页，2022年，8月28日18.1随机算法的基本知识18.1.3随机算法的设计方法1.挫败对手法(FoilingtheAdversary)

将不同的算法组成算法群,根据输入实例的不同，随机地或有选择地选取不同的算法,以使性能达到最佳.2.随机采样法(RandomSampling)

用“小”样本群的信息,指导整体的求解.3.随机搜索法(RandomSearch)

随机地在某个区域进行搜索，这种方法可以从统计角度分析算法的平均性能,如果将搜索限制在有解或有较多解的区域,可以大大提高搜索的成功概率.4.指印技术(Fingerprinting)

定义指印函数（Hash函数），利用指印信息可以大大减少对象识别的工作量.例如：通过随机映射的取指印方法,Karp和Rabin设计了一个线性时间复杂度的快速的串匹配随机算法.5.输入随机重组法(InputRandomization)

对输入实例进行随机重组之后,可以改进算法的平均性能，例如：随机Quick排序算法.第七页，共十五页，2022年，8月28日18.1随机算法的基本知识18.1.3随机算法的设计方法6.负载平衡法(LoadBalancing)

在并行与分布计算、网络通讯等问题中,使用随机选择技术分配数据可以达到任务的负载平衡和网络通讯的平衡.7.快速混合Markov链法(RapidlyMixingMarkovChain)

使用该方法可以解决大空间中的均匀抽样问题.8.孤立和破对称技术(IsolationandSymmetryBreaking)

使用该技术可以解决内在顺序处理问题的并行性,避免分布式系统的死锁等问题.如:图着色算法,部分独立集问题9.概率存在性证明法(ProbabilisticMethodsandExistenceProofs)

如果随机选取的物体具有某种特性的概率大于0,则具有该特性的物体一定存在.10.消除随机性方法(Derandomization)

注：许多优秀的确定性算法均是由随机算法转换而来.第八页，共十五页，2022年，8月28日18.6随机排序18.6.1随机采样与随机Quick排序1.随机采样

非复原采样法（Samplingwithoutreplacement）等概率地每次从规模为n的原始数据中选择一个元素，选中的元素从原始数据中移去。复原采样法（Samplingwithreplacement）等概率地每次从规模为n的原始数据中选择一个元素，但选中的元素并不从原始数据中移去，即一个元素可能被选择若干次。

2.随机Quick排序算法

Quick排序算法随机化思想：修改算法的数据划分过程，在Quick排序算法的每一步，当数组还没有被划分时，将元素A[p]与从A[p‥r]中随机挑选出的一个元素交换，以确保枢点元素x=A[p]取自A[p‥r]中r-p+1个元素任一个的可能性相同。经过这样的随机化处理之后，就能期望对输入数组的划分一般都是对称（左、右两部分的数据个数相同）的。

第九页，共十五页，2022年，8月28日18.6随机排序18.6.2并行随机Quick排序算法

设A是由n个互不相同元素组成的无序数组，算法思想：从A中随机挑选一个划分元素（Splitter）S(A)，将S(A)与A中各个元素比较，将比S(A)小的元素标记为1，比S(A)大的元素标记为0；将较小的元素移向A的前端，而将较大的元素移向Ａ的后端;对于这些较小的元素（子序列，桶）和较大的元素（子序列，桶）重复以上相同的策略进行并行处理，直到子序列（桶）中的元素数足够小(如30)为止。

算法18.5RPRAM-EREW上随机Quick排序算法Randomized-Quicksort(A[1..n])输入：待排序的数组Ａ，|A|=n输出：有序数组

Begin(1)ifn<=30thensortAusinganysortingalgorithmandreturnsortedA;(2)selectarandomelementS(A)fromA;

//随机选择一个划分元素

(3)fori=1tondoinparallelifA[i]<S(A)thenmark[i]=1elsemark[i]=0;(4)compacttheelementsofAwithmarked1atbeginningofA,followedbyS(A)whichisfollowedbytheelementsofAwithmarked0;setkequaltopositionoftheelementS(A);(5)Randomized-Quicksort(A[1..k-1]);//并行递归调用

Randomized-Quicksort(A[k+1..n])End.第十页，共十五页，2022年，8月28日18.6随机排序18.6.2并行随机Quick排序算法

设e是Ａ中的任一元素，nj为第j（j

≥1）次划分结束时，包含的子序列（桶）的容量（元素数目），其中n0＝n，则引理18.8对于任意的j

≥0，Pr{nj+1≥7nj/8}≤

1/4.引理18.9在20log8/7n次划分步中，元素e

经历了20log8/7n-log8/7

(n/30)次不成功划分步的概率为O(n-7).定理18.15算法18.15高概率地可在O(log2n)时间内使用O(nlogn)次操作（工作量），完成对n个数据的排序。RPRAM-EREW上随机并行Quick排序示例输入：Ａ={4,16,-5,7,25,-8,1,3},n=8

//设算法递归到n=14,16,-5,7,25,-8,1,3

4,-5,-8,1,3,7,16,25

-8,-5,4,1,

3,7,16,25

-8,-5,1,3,4

,7,16,25

-8,-5,1,3,

4,7,16,25第十一页，共十五页，2022年，8月28日18.6随机排序18.6.3拓展的并行随机Quick排序算法

算法思想：从当前子序列（桶）中随机挑选个划分元素（样本），将每个桶划分成+1个较小的桶，然后并行递归排序各个桶。每个划分步的代价仍保持为对数时间，且总的运行时间也是对数的。算法18.6RPRAM-EREW上扩展的算法Randomized-Quicksort(A[1..n])输入：待排序的数组Ａ，|A|=N输出：有序数组

Begin(1)若n≤30则使用任一算法排序A;(2)从A中独立（随机）地采样n1/2

个划分元素，并形成集合S;

(3)成对比较S中元素将其排序，并以n1/2*n1/2

的二维表T的形式存放结果;对T的每一行用前缀和计算S各元素的位序；

(4)将A中元素置入桶{Bi}，1≤

i≤

n1/2+1,使得Bi的元素就是A中那些处于S中第(i-1)个最小者和第i个最小者之间的元素;

//第0个最小者为负无穷大，第

+1个最小者为正无穷大

(5)并行递归排序各桶中的元素

End.定理18.16算法18.15高概率地可在O(logn)时间内使用O(nlogn)次操作（工作量），完成对n个数据的排序。第十二页，共十五页，2022年，8月28日18.7随机串匹配18.7.1KARP-RABIN串匹配随机算法思想基于映射思想和素数理论，定义一个称为“指印”(Fingerprint)的函数，它首先将模式串映射成一个比模式串短得多的指印（位串数据），然后将正文串中每一个长度为m的子串也映射一个比子串本身短得多的指印（位串数据）。要求所构造的指印函数尽可能扫描整个文本串，并且能迅速计算出每个长度为m的子串的指印。算法的匹配比较过程不是直接比较模式串与正文子串本身，而是比较模式串的指印函数值和正文子串的指印函数值。

若两者的指印函数值相等，算法就认为模式与当前正文子串高概率地匹配。假设正文串与模式串中出现的字符集合为∑，｜∑｜=d。将模式串以及正文串中每个长度为m的子串用以d为基的整数表示。即定义一个映射（函数），它将长度为m

的字符串映射成整数x(0≤x≤d-1)。第十三页，共十五页，2022年，8月28日18.7随机串匹配18.7.2KARP-RABIN串匹配随机算法

设asc(c)为字符c的ASCII值，将模式串P=p1p2…pm

表示成:

x=asc(p1)dm-1+asc(p2)dm-2+…+asc(pm-1)d1+asc(pm)

其对应的指印（散列）函数是：h(x)=xmodq，q是区间[1,n2

m]中随机选取的某个适当大的素数。同理，将正文串中长度为m

的某个子串titi+1…ti+m-1表示成:

y=asc(ti)dm-1+asc(ti+1)dm-2+…+asc(ti+m-2)d1+asc(ti+m-1)

其对应的指印（散列）函数是：h(y)=ymodq，q是区间[1,n2

m]中随机选取的某个适当大的素数。为了迅速计算出正文中每个长度为m的字符串的指印（散列）函数值，我们考虑正文中前后两个紧接着的长度为m的字符串的指印函数值之间的关系。记正文中子串titi+1…ti+m-1对应的整数为yi

，则有

yi

=asc(ti)dm-1+asc(ti+1)dm-2+…+asc(ti+m-2)d1+asc(ti+m-1)

而正文中子串ti+1ti+2…ti+m

对应的整数为yi+1

满足

yi+1=asc(ti+1)dm-1+asc(ti+2)dm-2+…+asc(ti+m-1)d1+asc(ti+m)=(yi–asc(ti

)dm-1)d+asc(ti+m)

因此有:h(yi+1)=h((yi–asc(ti

)dm-1)d+asc(ti+m))modq，i=1~n-m。令xx=dm-1modq

，则得到计算每个长度为m的子串的指印函数值的递推公式为：

h(yi+1)=((h(yi)-xx×asc(ti))d+asc(ti+m))modq

，i=1~n-m。第十四页，共十五页，2022年，8月28日18.7随机串匹配18.7.2KARP-RABIN串匹配随