并行算法的設(shè)計(jì)與分析章

并行算法的設(shè)計(jì)與分析章第一頁，共十五頁，2022年，8月28日18.1隨機(jī)算法的基本知識(shí)18.1.1概率論的基本知識(shí)18.1.2隨機(jī)算法的概念、模型及其度量1.隨機(jī)算法的概念定義:是一個(gè)概率圖靈機(jī).也就是在算法中引入隨機(jī)因素,

即通過隨機(jī)數(shù)選擇算法的下一步操作.三要素:輸入實(shí)例、隨機(jī)源和停止準(zhǔn)則.特點(diǎn):簡(jiǎn)單、快速、易于并行化.一種平衡:隨機(jī)算法可以理解為在時(shí)間、空間和隨機(jī)三大計(jì)算資源中的平衡(LuC.J.,Ph.DThesis,1999).重要文獻(xiàn)

MotwaniR.,RaghavanP.RandomizedAlgorithms.CambridgeUniversityPress,NewYork,1995第二頁，共十五頁，2022年，8月28日18.1隨機(jī)算法的基本知識(shí)18.1.2隨機(jī)算法的概念、模型及其度量2.隨機(jī)算法的意義求解問題的一種重要讓步策略：對(duì)某些問題，若要求其精確解，則設(shè)計(jì)出的算法的時(shí)間復(fù)雜度為指數(shù)級(jí)增長(zhǎng)的，這樣的算法在現(xiàn)實(shí)中不可行的。有效的隨機(jī)算法實(shí)際可行的隨機(jī)算法可轉(zhuǎn)化為確定算法易于并行化促進(jìn)智能計(jì)算的發(fā)展第三頁，共十五頁，2022年，8月28日18.1隨機(jī)算法的基本知識(shí)18.1.2隨機(jī)算法的概念、模型及其度量3.隨機(jī)算法的重要應(yīng)用MonteCarlo求定積分法.隨機(jī)k-選擇算法.隨機(jī)快排序算法素?cái)?shù)判定的隨機(jī)算法二階段隨機(jī)路由算法.4.研究隨機(jī)算法的重要人物及其工作deLeeuw等人提出了概率圖靈機(jī)(1955)JohnGill的隨機(jī)算法復(fù)雜性理論(1977)Rabin的數(shù)論和計(jì)算幾何領(lǐng)域的工作(1976)Karp的算法概率分析方法(1985)Shor的大數(shù)素因子分解量子計(jì)算算法(1994)第四頁，共十五頁，2022年，8月28日18.1隨機(jī)算法的基本知識(shí)18.1.2隨機(jī)算法的概念、模型及其度量5.隨機(jī)算法計(jì)算模型—隨機(jī)PRAM模型（RandomizedPRAMModel,RPRAM)允許每個(gè)處理器在單步時(shí)間內(nèi)產(chǎn)生某個(gè)范圍的隨機(jī)數(shù)。一個(gè)隨機(jī)數(shù)在整數(shù)區(qū)間[1,2,…,m]內(nèi)均等地取任一整數(shù)值。限定在單步時(shí)間內(nèi)產(chǎn)生的隨機(jī)數(shù)的位數(shù)為O(logn)，n為輸入長(zhǎng)度，以確保每個(gè)數(shù)據(jù)均能存儲(chǔ)在一個(gè)存儲(chǔ)單元中并可在O(1)順序?qū)崿F(xiàn)步內(nèi)執(zhí)行操作。假定p個(gè)處理器在同一時(shí)間步所產(chǎn)生的p個(gè)隨機(jī)數(shù)彼此獨(dú)立。6.隨機(jī)算法的分類LasVegas算法和MonteCarlo算法是常見的兩類隨機(jī)算法。LasVegas算法運(yùn)行結(jié)束時(shí)總能給出正確解，但其運(yùn)行時(shí)間每次有所不同。

MonteCarlo算法每次運(yùn)行結(jié)束時(shí)可能得到不正確的結(jié)果，但這種概率是很小的且有界。第五頁，共十五頁，2022年，8月28日18.1隨機(jī)算法的基本知識(shí)18.1.2隨機(jī)算法的概念、模型及其度量7.時(shí)間復(fù)雜性度量運(yùn)行時(shí)間的期望實(shí)例的運(yùn)行時(shí)間期望對(duì)固定實(shí)例x,設(shè)隨機(jī)算法A的運(yùn)行時(shí)間是一個(gè)[0,+∞)上的隨機(jī)變量,

定義隨機(jī)算法A在實(shí)例x上的運(yùn)行時(shí)間期望為E[],也稱為隨機(jī)算法A在實(shí)例x上的執(zhí)行時(shí)間.算法的運(yùn)行時(shí)間期望如果對(duì)一個(gè)規(guī)模為n的問題的所有實(shí)例是均勻選取的,則定義各個(gè)實(shí)例上的平均執(zhí)行時(shí)間為隨機(jī)算法在該問題上的運(yùn)行時(shí)間期望,記為T(n)

隨機(jī)復(fù)雜度類(參見MotwaniR.,RaghavanP.,RandomizedAlgorithms.)RP(RandomizedPolynomialtime),etc.第六頁，共十五頁，2022年，8月28日18.1隨機(jī)算法的基本知識(shí)18.1.3隨機(jī)算法的設(shè)計(jì)方法1.挫敗對(duì)手法(FoilingtheAdversary)

將不同的算法組成算法群,根據(jù)輸入實(shí)例的不同，隨機(jī)地或有選擇地選取不同的算法,以使性能達(dá)到最佳.2.隨機(jī)采樣法(RandomSampling)

用“小”樣本群的信息,指導(dǎo)整體的求解.3.隨機(jī)搜索法(RandomSearch)

隨機(jī)地在某個(gè)區(qū)域進(jìn)行搜索，這種方法可以從統(tǒng)計(jì)角度分析算法的平均性能,如果將搜索限制在有解或有較多解的區(qū)域,可以大大提高搜索的成功概率.4.指印技術(shù)(Fingerprinting)

定義指印函數(shù)（Hash函數(shù)），利用指印信息可以大大減少對(duì)象識(shí)別的工作量.例如：通過隨機(jī)映射的取指印方法,Karp和Rabin設(shè)計(jì)了一個(gè)線性時(shí)間復(fù)雜度的快速的串匹配隨機(jī)算法.5.輸入隨機(jī)重組法(InputRandomization)

對(duì)輸入實(shí)例進(jìn)行隨機(jī)重組之后,可以改進(jìn)算法的平均性能，例如：隨機(jī)Quick排序算法.第七頁，共十五頁，2022年，8月28日18.1隨機(jī)算法的基本知識(shí)18.1.3隨機(jī)算法的設(shè)計(jì)方法6.負(fù)載平衡法(LoadBalancing)

在并行與分布計(jì)算、網(wǎng)絡(luò)通訊等問題中,使用隨機(jī)選擇技術(shù)分配數(shù)據(jù)可以達(dá)到任務(wù)的負(fù)載平衡和網(wǎng)絡(luò)通訊的平衡.7.快速混合Markov鏈法(RapidlyMixingMarkovChain)

使用該方法可以解決大空間中的均勻抽樣問題.8.孤立和破對(duì)稱技術(shù)(IsolationandSymmetryBreaking)

使用該技術(shù)可以解決內(nèi)在順序處理問題的并行性,避免分布式系統(tǒng)的死鎖等問題.如:圖著色算法,部分獨(dú)立集問題9.概率存在性證明法(ProbabilisticMethodsandExistenceProofs)

如果隨機(jī)選取的物體具有某種特性的概率大于0,則具有該特性的物體一定存在.10.消除隨機(jī)性方法(Derandomization)

注：許多優(yōu)秀的確定性算法均是由隨機(jī)算法轉(zhuǎn)換而來.第八頁，共十五頁，2022年，8月28日18.6隨機(jī)排序18.6.1隨機(jī)采樣與隨機(jī)Quick排序1.隨機(jī)采樣

非復(fù)原采樣法（Samplingwithoutreplacement）等概率地每次從規(guī)模為n的原始數(shù)據(jù)中選擇一個(gè)元素，選中的元素從原始數(shù)據(jù)中移去。復(fù)原采樣法（Samplingwithreplacement）等概率地每次從規(guī)模為n的原始數(shù)據(jù)中選擇一個(gè)元素，但選中的元素并不從原始數(shù)據(jù)中移去，即一個(gè)元素可能被選擇若干次。

2.隨機(jī)Quick排序算法

Quick排序算法隨機(jī)化思想：修改算法的數(shù)據(jù)劃分過程，在Quick排序算法的每一步，當(dāng)數(shù)組還沒有被劃分時(shí)，將元素A[p]與從A[p‥r]中隨機(jī)挑選出的一個(gè)元素交換，以確保樞點(diǎn)元素x=A[p]取自A[p‥r]中r-p+1個(gè)元素任一個(gè)的可能性相同。經(jīng)過這樣的隨機(jī)化處理之后，就能期望對(duì)輸入數(shù)組的劃分一般都是對(duì)稱（左、右兩部分的數(shù)據(jù)個(gè)數(shù)相同）的。

第九頁，共十五頁，2022年，8月28日18.6隨機(jī)排序18.6.2并行隨機(jī)Quick排序算法

設(shè)A是由n個(gè)互不相同元素組成的無序數(shù)組，算法思想：從A中隨機(jī)挑選一個(gè)劃分元素（Splitter）S(A)，將S(A)與A中各個(gè)元素比較，將比S(A)小的元素標(biāo)記為1，比S(A)大的元素標(biāo)記為0；將較小的元素移向A的前端，而將較大的元素移向Ａ的后端;對(duì)于這些較小的元素（子序列，桶）和較大的元素（子序列，桶）重復(fù)以上相同的策略進(jìn)行并行處理，直到子序列（桶）中的元素?cái)?shù)足夠小(如30)為止。

算法18.5RPRAM-EREW上隨機(jī)Quick排序算法Randomized-Quicksort(A[1..n])輸入：待排序的數(shù)組Ａ，|A|=n輸出：有序數(shù)組

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

//隨機(jī)選擇一個(gè)劃分元素

(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]);//并行遞歸調(diào)用

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

設(shè)e是Ａ中的任一元素，nj為第j（j

≥1）次劃分結(jié)束時(shí)，包含的子序列（桶）的容量（元素?cái)?shù)目），其中n0＝n，則引理18.8對(duì)于任意的j

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

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

經(jīng)歷了20log8/7n-log8/7

(n/30)次不成功劃分步的概率為O(n-7).定理18.15算法18.15高概率地可在O(log2n)時(shí)間內(nèi)使用O(nlogn)次操作（工作量），完成對(duì)n個(gè)數(shù)據(jù)的排序。RPRAM-EREW上隨機(jī)并行Quick排序示例輸入：Ａ={4,16,-5,7,25,-8,1,3},n=8

//設(shè)算法遞歸到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隨機(jī)排序18.6.3拓展的并行隨機(jī)Quick排序算法

算法思想：從當(dāng)前子序列（桶）中隨機(jī)挑選個(gè)劃分元素（樣本），將每個(gè)桶劃分成+1個(gè)較小的桶，然后并行遞歸排序各個(gè)桶。每個(gè)劃分步的代價(jià)仍保持為對(duì)數(shù)時(shí)間，且總的運(yùn)行時(shí)間也是對(duì)數(shù)的。算法18.6RPRAM-EREW上擴(kuò)展的算法Randomized-Quicksort(A[1..n])輸入：待排序的數(shù)組Ａ，|A|=N輸出：有序數(shù)組

Begin(1)若n≤30則使用任一算法排序A;(2)從A中獨(dú)立（隨機(jī)）地采樣n1/2

個(gè)劃分元素，并形成集合S;

(3)成對(duì)比較S中元素將其排序，并以n1/2*n1/2

的二維表T的形式存放結(jié)果;對(duì)T的每一行用前綴和計(jì)算S各元素的位序；

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

i≤

n1/2+1,使得Bi的元素就是A中那些處于S中第(i-1)個(gè)最小者和第i個(gè)最小者之間的元素;

//第0個(gè)最小者為負(fù)無窮大，第

+1個(gè)最小者為正無窮大

(5)并行遞歸排序各桶中的元素

End.定理18.16算法18.15高概率地可在O(logn)時(shí)間內(nèi)使用O(nlogn)次操作（工作量），完成對(duì)n個(gè)數(shù)據(jù)的排序。第十二頁，共十五頁，2022年，8月28日18.7隨機(jī)串匹配18.7.1KARP-RABIN串匹配隨機(jī)算法思想基于映射思想和素?cái)?shù)理論，定義一個(gè)稱為“指印”(Fingerprint)的函數(shù)，它首先將模式串映射成一個(gè)比模式串短得多的指?。ㄎ淮?dāng)?shù)據(jù)），然后將正文串中每一個(gè)長(zhǎng)度為m的子串也映射一個(gè)比子串本身短得多的指?。ㄎ淮?dāng)?shù)據(jù)）。要求所構(gòu)造的指印函數(shù)盡可能掃描整個(gè)文本串，并且能迅速計(jì)算出每個(gè)長(zhǎng)度為m的子串的指印。算法的匹配比較過程不是直接比較模式串與正文子串本身，而是比較模式串的指印函數(shù)值和正文子串的指印函數(shù)值。

若兩者的指印函數(shù)值相等，算法就認(rèn)為模式與當(dāng)前正文子串高概率地匹配。假設(shè)正文串與模式串中出現(xiàn)的字符集合為∑，｜∑｜=d。將模式串以及正文串中每個(gè)長(zhǎng)度為m的子串用以d為基的整數(shù)表示。即定義一個(gè)映射（函數(shù)），它將長(zhǎng)度為m

的字符串映射成整數(shù)x(0≤x≤d-1)。第十三頁，共十五頁，2022年，8月28日18.7隨機(jī)串匹配18.7.2KARP-RABIN串匹配隨機(jī)算法

設(shè)asc(c)為字符c的ASCII值，將模式串P=p1p2…pm

表示成:

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

其對(duì)應(yīng)的指?。ㄉ⒘校┖瘮?shù)是：h(x)=xmodq，q是區(qū)間[1,n2

m]中隨機(jī)選取的某個(gè)適當(dāng)大的素?cái)?shù)。同理，將正文串中長(zhǎng)度為m

的某個(gè)子串titi+1…ti+m-1表示成:

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

其對(duì)應(yīng)的指?。ㄉ⒘校┖瘮?shù)是：h(y)=ymodq，q是區(qū)間[1,n2

m]中隨機(jī)選取的某個(gè)適當(dāng)大的素?cái)?shù)。為了迅速計(jì)算出正文中每個(gè)長(zhǎng)度為m的字符串的指?。ㄉ⒘校┖瘮?shù)值，我們考慮正文中前后兩個(gè)緊接著的長(zhǎng)度為m的字符串的指印函數(shù)值之間的關(guān)系。記正文中子串titi+1…ti+m-1對(duì)應(yīng)的整數(shù)為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

對(duì)應(yīng)的整數(shù)為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

，則得到計(jì)算每個(gè)長(zhǎng)度為m的子串的指印函數(shù)值的遞推公式為：

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

，i=1~n-m。第十四頁，共十五頁，2022年，8月28日18.7隨機(jī)串匹配18.7.2KARP-RABIN串匹配隨