[理學(xué)]并行算法講稿-資料下載頁
2025-01-19 07:33本頁面
【正文】 同類的子問題； ? 遞歸求解各子問題； ? 將各子問題的解歸并成為原問題的解； 十二、并行分治 并行分治 : F(I) { if 輸入足夠小 then O ? Answer( I )。 else { 分解輸入： I1, ?I k； for all Pi i=1?k do Oi ? F( Ii, Oi )。 O ? Combine( O1,?O k )。 } } 十二、并行分治 ? 最近點對問題 d1 d2 d 2d 十三、劃分法 劃分法 ? 與分治法相似，劃分原理也是將原問題進行分解，分別求解，再歸并子問題的解。 ? 所不同的是，分治法采用簡單的分解方法，因此設(shè)計的難點在于如何歸并子問題的解，而劃分方法則講究分解的方法，以獲得簡單的歸并策略。 有序序列歸并 : 設(shè) A=(a1, a2, …, a n)， B=(b1, b2, …, bm)， 是 U上的單調(diào)增序列，且 A∩B=Ф。 將 A和 B歸并到： C=(c1, c2, …, cm+n)。 十三、劃分法 ? 有序序列歸并 ? 定義：對 U上的有序序列列 X=(x1,x2,…, xt)， x∈ U， x在 X上的位序 rank(x:X)為 X中小于等于 x的元素個數(shù)。 ? 歸并問題即求 rank(x:A∪ B)， x∈ A∪ B。 ? 分別求出 rank(ai:B)和 rank(bj:A)，即可得到rank(x:A∪ B)=rank(x:A) + rank(x:B)。 ? 這樣就可以在 O(logn)時間內(nèi)用 O(nlogn)工作量完成合并的任務(wù)。 ? 但這樣的解法不是一個工作量有效的算法。通過進一步劃分，可以得到工作量有效的解法。 十三、劃分法 ? 有序序列歸并 ? 定義：對 U上的有序序列列 X=(x1,x2,…, xt)， x∈ U， x在 X上的位序 rank(x:X)為 X中小于等于 x的元素個數(shù)。 ? 歸并問題即求 rank(x:A∪ B)， x∈ A∪ B。 ? 分別求出 rank(ai:B)和 rank(bj:A)，即可得到rank(x:A∪ B)=rank(x:A) + rank(x:B)。 ? 這樣就可以在 O(logn)時間內(nèi)用 O(nlogn)工作量完成合并的任務(wù)。 ? 但這樣的解法不是一個工作量有效的算法。通過進一步劃分，可以得到工作量有效的解法。 十七、確定性破對稱技術(shù) ? 基本概念 ? 破對稱：打破并行操作的對稱性，即避免兩個處理器同時被分派對同一個單元進行處理或同時不被分派進行處理。前面的隨機消元中的拋硬幣方法就是一種不確定的破對稱技術(shù)。 ? 確定性破對稱技術(shù)：利用處理器的編號來打破對稱性。例如前面的例子中，通過讓下標較小的處理器先訪問來打破對稱性。 十七、確定性破對稱技術(shù) ? 確定性破對稱算法 ? 要求從靜態(tài)鏈表中選出一部分元素，這部分元素在鏈表中兩兩不相鄰，且數(shù)目是鏈表中元素總數(shù)的常分數(shù)倍。 ? n個處理器和 O(log*n)的計算時間，其中 log*n定義為： ? log*x = min{ i | log(i)x=1, i=0 }。 ? log(i)x定義為： 無定義或且且無定義 xxixiixxxiiiii)1()1()1()1()(l o g0l o g00l o g00)l o g ( l o gl o g??????????????對 1≤n≤265536，有 0≤log*n≤5，因此對一般的實際應(yīng)用， log*n是一個小常數(shù) 。 十七、確定性破對稱技術(shù) ? 無向圖著色與極大獨立集 ? 無向圖 G=(V, E)的一個著色是一個映射Ｃ：Ｖ Ｎ，使得對所有 u, v∈ Ｖ，如果Ｃ (u)=C(v)，則 (u, v)不屬于Ｅ，即相鄰點不同色。 ? 在鏈表上進行６ 著色，可用的顏色號為 {0, 1, 2, 3, 4, 5 }，且相鄰元素不同色。 ? 雖然可以用 O(logn)的時間并行地對鏈表進行 2著色，將奇、偶元素分別著以不同的顏色，但通常只要有一種 O(1)的著色就可以了。 ? 下面的算法在 O(log*n)的時間對 n個元素的鏈表進行 6著色。 十七、確定性破對稱技術(shù) ? 無向圖著色與極大獨立集 ? G=(V, E)的一個獨立集是其頂點集 V的一個子集 V’，使得 E中的每條邊最多只與 V’中的一個頂點相關(guān)聯(lián)。極大獨立集是一個不能再并入其他任何頂點的獨立集。最大獨立集是圖 G的一個規(guī)模最大的獨立集。求極大獨立集是一個易解的問題，求最大獨立集卻是一個 NP完全問題。 ? 雖然對一個鏈表可以通過 O(logn)時間分別標出奇偶點，從而得到兩個最大獨立集，但速度不夠快。而只要我們能求得鏈表的極大獨立集，則可知極大獨立集中的元素個數(shù)不小于n/3（每三個元素中，至少有一個元素屬于極大獨立集）。 我的講課完了，不足之處希望大家提出批評建議！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1