單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,*,《,并行計(jì)算,》,作業(yè)參考解答,,,,,5.10,對圖,5.3,所示的單位權(quán)有向圖，試用布爾鄰接矩陣乘法求出其傳遞閉包。,,A+I=,,,,A,+,=((A+I),2,),2,=(A+I),4,=,,,,A,是一個大小為,n,的布爾數(shù)組，欲求出最小的下標(biāo),i,且,A[i,],為真，試設(shè)計(jì)一個常數(shù)時間的,PRAM-CRCW,并行算法。如果使用,PRAM-CREW,模型，運(yùn)行時間如何？,,,,n,2,個處理器,1. copy A[1..n] to B[1..n],//O(1),,2. for i=1 to n par-do  if,B[i,]=true then//O(1),,for j=i+1 to n par-do,B[j,]=false //O(1),endfor,,,endif,,,endfor,,3. for i=1 to n par-do,,if,B[i,]=true then //O(1) return i,,,endif,,,endfor,PRAM-CRCW,下的時間復(fù)雜度為,:O(4),,PRAM-CREW,下第,2,步,B[i,]=false,不能同時寫，需要,O(n,),的時間來寫,,,,,試用分治策略或劃分技術(shù)設(shè)計(jì)一個算法求數(shù)組,A[1..n],的最小元素，要求用,O(n/logn,),個處理器，時間復(fù)雜度為,O(logn,),。,,1.,采用均勻劃分，每個處理器分配,logn,個元素，求出本處理器中的最小元素時間為：,log(log,n),。共得到,n/logn,個局部最小元素。,,2.,對,n/logn,個局部最小元素用平衡二叉樹的算法求最小值（類似算法,6.8,）。時間為：,log(n,/log n)=log n -,log(log,n),,3.,總的時間為,log(log,n) +,log(n,/log n) =,log(n,),,題目,11.7,,(a)A,[0],j,=a,0,+a,2,w,n/2,j,+a,4,w,n/2,j·2,+…+a,n-2,w,n/2,j·(n/2-1),A,[1],j,=a,1,+a,3,w,n/2,j,+a,5,w,n/2,j·2,+…+a,n-1,w,n/2,j·(n/2-1),其中,(w,n/2,),n/2,,= 1,B,j,=a,0,+a,1,w,n,j,+a,2,w,n,j·2,+…+a,n-1,w,n,j·(n-1),其中,(,w,n,,),n,,= 1,利用,w,n/2,j,=,,w,n,j·2,,,,w,n,j·(n/2),= -1,可得：,,B,j,=A,[0],j,+w,n,j,A,[1],j,B,j+n/2,=A,[0],j,+w,n,j+n/2,A,[1],j,=A,[0],j,-w,n,j,A,[1],j,,(b) 1.,遞歸策略不同,2.,參數(shù)傳遞,vs,,返回值,3.,步驟（,7,）中的迭代為算法,11.2,的一 半,,(c),,,,謝謝大家！,,課堂練習(xí),,1.,試畫出基于,Batcher,比較器的雙調(diào)序列（,8,，,6,，,4,，,2,，,0,，,1,，,3,，,5,）的雙調(diào)歸并排序網(wǎng)絡(luò)，并標(biāo)出每個,Batcher,比較器的輸入和輸出數(shù)據(jù)。,,2.,給出矩陣,A,和,B,的,Cannon,矩陣乘法的具體計(jì)算過程。,,,A= B=,,,,