并行算法的一般設(shè)計策略

1、第五章并行算法的一般設(shè)計策略習題例題：1、令n是待排序的元素數(shù)，p= 2d是d維超立方中處理器的數(shù)目。假定開始隨機選定主元x,并將其播送給所有其他處理器，每個處理器按索接收到的x,對其n/p個元素按照w x和x進行劃分，然后按維進行交換。這樣在超立方上實現(xiàn)的快排序算法如下：算法 5.6 超立方上快排序算法輸入： n 個元素, B = n/p, d = log p輸出： 按超立方編號進行全局排序Begin(1) id = pr ocessor s label(2) for i=1 to ddo(2.1) x = pivot/ * 選主元 * /(2.2) 劃分B為Bi和B2滿足Bi w B B2

2、(2.3) if第i位是零 then(i) 沿第i維發(fā)送B2給其鄰者(ii) C = 沿第 i 維接收的子序列(iii) B= B 1 U Celse(i) 沿第 i 維發(fā)送 B1 給其鄰者(ii) C = 沿第 i 維接收的子序列(iii) B= B 2U Cendifendfor(3) 使用串行快排序算法局部排序 B = n/p 個數(shù)End 試解釋上述算法的原理。 試舉一例說明上述算法的逐步執(zhí)行過程。2、 令T = babaababa& P =abab，試用算法5.4計算兩者的匹配情況。 試分析 KMP 算法為何不能簡單并行化。3、 給定序列( 33, 21, 13, 54, 82, 33

3、, 40, 72)和 8 個處理器,試按照 算法 5.2構(gòu)造 棵為在 PRAM-CRCW 模型上執(zhí)行快排序所用的二叉樹。4、計算duel(p, q)函數(shù)的算法如下：算法 5.7 計算串匹配的 duel(p, q) 的算法輸入：WIT 1: n-m+1 , 1w p qw n-m+1 , ( p - q) m/2輸出： 返回競爭幸存者的位置或者 null (表示 p 和 q 之一不存在)Beginif p=null then duel= q elseif q =null then duel= p else(1) j= q - p +i(2) w=WIT( j)(3) if T(q+w-1)豐 P

4、(w) then(i) WIT( q) = w(ii) duel= pelse(i) WIT( p) = q -p +1(ii) duel= qendifendifEnd 令 T = abaababaababaababababa P = abaababa，試計算 WIT( i)； 試考慮P=6, q=9的競爭情況。5、對于圖5.2(a)的加權(quán)有向圖，試用 算法5.5，逐步求出D2, D4和D8中各元素dj :d00d01d02d03d04d05d06d00did02d03d04d05d06dwd；d13d125d16dwd121d12d13dud16.060d61d：2d64d：6060d62id62d：3d64d：5d664(b) D2(a) Dd0od0