并行算法設(shè)計(jì)與分析考題與答案

1、P8=j)=P(2,0)P1=Pj,k)=P(0,1)P2=j=P(0,2)P3=Pj,k)=P(0,3)P4=P(j,k)=P(1,0)P5=j)=P(1,1)P6=j)=P(1,2)P7=j)=P(1,3)并行算法設(shè)計(jì)與分析考題與答案一、1.3,處理器PI的編號(hào)是：解：對(duì)于nxn網(wǎng)孔結(jié)構(gòu)，令位于第j行，第k歹(0<j,k<n-1)的處理器為Pi(0<i<n2-1)o以16處理器網(wǎng)孔為例,n=4(假設(shè)j、k由0開(kāi)始)：由P0=P(j,k)=P(0,0)P9=j)=P(2,1)P10=j)=P(2,2)P11=Pj,k)=P(2,3)P12=j)=P(3,0)P13=j

2、)=P(3,1)P14=j)=P(3,2)P15=j)=P(3,3)同時(shí)觀察i和j、k之間的關(guān)系，可以得出i的表達(dá)式為：i=j*n+k一、1.6矩陣相乘(心動(dòng)算法)a)相乘過(guò)程設(shè)1234212112121212A矩陣=B矩陣=2112123421214321A(i,l)B(l,j)C(i,j)12【注】矩陣兀素中A(i,l)表示自左向右移動(dòng)的矩陣，B(l,j)表示自上可下移動(dòng)的矩陣，斜加粗標(biāo)記表示已經(jīng)計(jì)算出的矩陣元素，如12,C(i,j)=C(i,j)+A(i,l)*B(l,j)黑色傾1、A(1.1)1B(1.1)2C(1,1)2C(1,2)0C(1,3)0C(1,4)0C(2,1)0C(2,

3、2)0C(2,3)0C(2,4)0C(3,1)0C(3,2)0C(3,3)0C(3,4)0C(4,1)0C(4,2)0C(4,3)0C(4,4)02、A(1.2)2A(1.1)1B(3,1)1B(1.2)1C(1,1)4C(1,2)1C(1,3)0C(1,4)0A(2,1)1B(1.1)2C(2,1)2C(2,2)0C(2,3)0C(2,4)0C(3,1)0C(3,2)0C(3,3)0C(3,4)0C(4,1)0C(4,2)0C(4,3)0C(4,4)0A(1.3)3A(1.2)2A(1.1)1B(3,1)1B(2,2)2B(1.3)2C(1,1)7C(1,2)5C(1,3)2C(1,4)0A

4、(2,2)1A(2,1)1B(2,1)2B(1.2)1C(2,1)4C(2,2)1C(2,3)0C(2,4)0A(3,1)2B(1.1)2C(3,1)4C(3,2)0C(3,3)0C(3,4)0C(4,1)0C(4,2)0C(4,3)0C(4,4)04、A(1.4)4A(1.3)3A(1.2)2A(1.1)1B(4,1)4B(3,2)2B(2,3)1B(1.4)1C(1,1)23C(1,2)11C(1,3)4C(1,4)1A(2,3)1A(2,2)2A(2,1)1B(3,1)1B(2,2)2B(1.3)2C(2,1)5C(2,2)5C(2,3)2C(2,4)0A(3,2)1A(3,1)2B(2

5、,1)1B(1.2)1C(3,1)5C(3,2)2C(3,3)0C(3,4)0A(4,1)2B(1.1)_2C(4,1)4C(4,2)0C(4,3)0C(4,4)0A(1.4)4A(1.3)3A(1.2)2B(4.2)3B(3,3)3B(2.4)2C(1,1)23C(1,2)23C(1,3)13C(1,4)5A(2.4)2A(2,3)1A(2,2)2A(2,1)1B(4,1)4B(3,2)2B(2,3)1B(1.4)1C(2,1)13C(2,2)7C(2,3)4C(2,4)1A(3,3)1A(3,2)1A(3,1)2B(3,1)1B(2,2)2B(1.3)2C(3,1)6C(3,2)4C(3,

6、3)4C(3,4)0A(4.2)1A(4,1)2B(2.1)_1B(1.2)1C(4,1)5C(4,2)2C(4,3)0C(4,4)06、A(1.4)4A(1.3)3B(4.3)2B(3.4)4C(1,1)23C(1,2)23C(1,3)21C(1,4)17A(2.4)2A(2,3)1A(2,2)2B(4.2)3B(3,3)3B(2.4)2C(2,1)13C(2,2)13C(2,3)7C(2,4)5A(3,4)2A(3,3)1A(3,2)1A(3,1)2B(4,1)4B(3,2)2B(2,3)1B(1.4)1C(3,1)14C(3,2)6C(3,3)5C(3,4)2A(4,3)2A(4.2)1

7、A(4,1)2B(3.1)_1B(2,2)2B(1.3)2C(4,1)7C(4,2)4C(4,3)4C(4,4)08、A(1.4)4B(4,4)1C(1,4)21A(2,3)1B(3.4)4C(2,4)9A(3,2)1B(2.4)2C(3,4)4A(4,1)2B(1.4)1C(4,4)2C(1,2)23C(2,1)13C(2,2)13C(3,1)14C(3,2)12C(1,3)21C(2,3)11C(3,3)121C(1,4)21C(2,4)11C(4,1)11C(4,2)11A(4,4)1B(4,3)2C(4,3)13A(3,4)2B(4,4)1C(3,4)10A(4,3)2B(3.4)4C

8、(4,4)12計(jì)算完畢b）可以在10步后完成，移動(dòng)矩陣長(zhǎng)L=7,4*4矩陣N=4,所以需要L+N-1=10二、（2.1）a）示例n=8時(shí)算法的計(jì)算過(guò)程:丫1=x1*x2*x3*x4*x5*x6*x7*x8丫1=x1*x2*x3*x4Y2=x5*x6*x7*x8Y2=x3*x4第1輪Y3=x5*x6Y4=x7*x8Y1=x1*x2x1x2x3x6x8x4x5x7第2輪1b)證明上述算法的復(fù)雜度T(n)=O(LOGn),W(n)-O(n)證明：ALGORITHMPrefixSumT(n)W(n)(1)ifn-1thenO(1)W1(n)-O(1)(2)forO(1)W2(n)-O(n/2)(3)R

9、ecursivelyT(n/2)W3(n/2)(4)forO(1)W4(n)-O(n)則：T(n)=O(1)n=1T(n/2)+O(1),n>1W(n)=O(1),n=1W(n/2)+O(n),n>1展開(kāi)解得：T(n)=O(logn)W(n)=O(n)二（2.3）、a）lgnb）如果不是2的哥次，增加一個(gè)空分量構(gòu)成2的哥次，它不會(huì)影響算法的復(fù)雜度。三、（3.3b）試構(gòu)造一個(gè)16輸入的雙調(diào)排序網(wǎng)絡(luò)：假設(shè)入16個(gè)數(shù)據(jù)為A1-A16,可以采用（1,1）歸并、（2,2）歸并、（4,4）歸并，（8,8）歸并構(gòu)造（1,（1） （2,2）歸并（4,4）歸并（8,8）歸并三(3.4)、判斷下列序列

10、是雙調(diào)序列嗎？為什么？如果是雙調(diào)網(wǎng)絡(luò)，他們形成的MIN和MAX序列是什么？(a) A=(-5,-9,-10,-5,2,7,35,37)(b) B=(21,18,14,10,-6,-4,0,1,2,19,31,30,29,22,21,21)解：)a)A序列是雙調(diào)序列，因?yàn)锳序列在經(jīng)過(guò)7次左循環(huán)后滿足A1>A2>A3>A4<A5<A6<A7<A8循環(huán)左移A1A2A3A4A5A6A7A8原數(shù)據(jù)-5-9-10-5273537第1次-9-10-5273537-5第2次-10-5273537-5-9第3次-5273537-5-9-10第4次273537-5-9-1

11、0-5第5次73537-5-9-10-52第6次3537-5-9-10-527第7次37-5-9-10-52735MIN=(-10,-9,-5,-5)MAX=(37,35,7,2)b)B序列是雙調(diào)序列，因?yàn)锽序列在經(jīng)過(guò)10次左循環(huán)后，滿足B1>B2>B3>B4>B5=B6=B7>B8>B9>B10>B11<B12VB13VB14VB15VB16循環(huán)左移B1B2B3B4B5B6B7B8B9B10B11B12B13B14B15B16原數(shù)據(jù)21181410-6-401219313029222121第1次181410-6-40121931302922212121第2次1410-6-4012193130292221212118第3次10-6-401219313029222121211814第4次-6-40121931302922212121181410第5次-40121931302922212121181410-6第6次0121931302922212121181410-6-4第7次1