并行算法设计与分析考题与答案

1、P1=Pj,k)=P(0,1)P2=Pj,k) =P(0,2)P3=Pj ,k)=P(0,3)P4=P(j,k)=P(1,0)P5=R,k)=P(1,1)P6=Pj,k) =P(1,2)P7=Pj,k) =P(1,3)并行算法设计与分析考题与答案一、1.3,处理器PI的编号是：解：对于n x n网孔结构，令位于第j行，第k列(0勺，k<n-1)的处理器为 Pi (0< i< n2-1)0以16处理器网孔为例，n=4 (假设j、k由0开始)：由 P0=P(j,k)=P(0,0)P8=Rj,k) = P(2,0)P9=Pj,k) =P(2,1)P10=Pj,k) =P(2,2)P

2、11=Pj,k) = P(2,3)P12 = Pj,k) =P(3,0)P13=Pj,k) = P(3,1)P14=Pj,k) =P(3,2)P15=Pj,k) =P(3,3)同时观察i和j、k之间的关系，可以得出i的表达式为：i= j*n+k3一、1.6矩阵相乘(心动算法) a)相乘过程1234212112121B矩阵=2122112123421214321A矩阵=A(i,l)B(l,j)C(i,j)12【注】矩阵元素中斜加粗标记表示已经计算出的矩阵元素，如A(i,l)表示自左向右移动的矩阵，B(l,j咸示自上向下移动的矩阵，黑色倾12, C(i,j)= C(i,j)+ A(i,l)* B(

3、l,j)C(1,2)0C(2,2)0C(1,3)0C(2,3)0C(1,4)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,2)2A(1,1)1B(3,1)1B(1,2)1C(1,1)4C(1,2)12、C(1,3)0C(1,4)0A(2,1)1B(1,1)2C(2,1)2C(2,2)0C(3,1)0C(3,2)0C(4,1)0C(4,2)0C(2,3)0C(2,4)0C(3,3)0C(3,4)0C(4,3)0C(4,4)05、4、A(1,2)2B(2,2)2C(1,2)5A(2,1)1B(1,2)1C(2

4、,2)1C(3,2)0C(4,2)0A(1,4)4B(4,1)4C(1,1)23A(2,3)1B(3,1)1C(2,1)5A(3,2)1B(2,1)1C(3,1)5A(4,1)2B(1,1)_2C(4,1)435、76、A(1,4)4B(4,2)3C(1,2)23A(2,3)1B(3,2)2C(2,2)7A(3,2)1B(2,2)2C(3,2)4A(4,1)2B(1,2)1C(4,2)2C(1,1)23C(1,2)23A(1,4)4B(4,3)2C(1,3)21C(2,1)13A(2,4)2B(4,2)3C(2,2)13A(2,3)1B(3,3)3C(2,3)7A(3,4)2B(4,1)4C(

5、3,1)14A(4,3)2B(3,1)_1C(4,1)7A(3,3)1B(3,2)2C(3,2)6A(4,2)1B(2,2)2C(4,2)4A(3,2)1B(2,3)1C(3,3)5A(4,1)2B(1,3)2C(4,3)47、98、C(1,3)21A(2,4)2B(4,3)2C(2,3)11A(3,3)1B(3,3)3C(3,3)8A(4,2)1B(2,3)1C(4,3)5A(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)21C(1,4)21A(2,4)2B(4,4)1C(2

6、,4)11A(3,3)1B(3,4)4C(3,4)8A(4,2)1B(2,4)2C(4,4)49、C(1,2)23C(1,3)211C(1,4)21C(2,1)13C(2,2)13C(2,3)11C(2,4)11C(3,1)14C(3,2)12A(3,4)2B(4,4)1C(3,4)10C(4,1)11C(4,2)11A(4,4)1B(4,3)2C(4,3)13C(3,3)12A(4,3)2B(3,4)4C(4,4)12计算完毕b）可以在10步后完成，移动矩阵长L=7, 4*4矩阵N=4,所以需要L+N-1=1011二、（2.1）a）示例n=8时算法的计算过程：Y1=x1*x2*x3*x4 *

7、x5*x6*x7*x815Y1=x1*x2*x3*x4Y2=x5*x6*x7*x8Y1=x1*x2Y2=x3*x4Y3=x5*x6Y4=x7*x8第2轮1b)证明上述算法的复杂度T(n)=O(LOG n),W(n)-O(n)证明：ALGORITHM Prefix SumT(n )W (n)(1) if n-1 then O (1)W1(n )-O (1)(2) forO (1)W2 (n)- O (n/2)(3) Recursively T (n/2)W3 (n/2)(4) for O (1)W4 (n )-O (n)则：T (n )=( O (1) n=1(T(n/2)+O(1) , n&g

8、t;1W(n)= ( O(1), n=1( W(n/2)+O(n) , n>1展开解得：T (n) =O (log n )W(n)= O(n)二（2.3 ）、a） lgnb)如果不是2的藉次，增加一个空分量构成2的藉次，它不会影响算法的复杂度。三、(3.3 b)试构造一个16输入的双调排序网络：假设输入16个数据为A1-A16，可以采用(1,1)归并、(2,2)归并、(4,4)归并，(8,8)归并构造(1,1)归并 (2,2)归并(4,4)归并(8,8)归并三(3.4)、判断下列序列是双调序列吗？为什么？如果是双调网络，他们形成的MIN和MAX序列是什么？(a) A= (-5,-9,-1

9、0,-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序列是双调序列，因为A序列在经过7次左循环后满足 A1>A2>A3>A4<A5<A6<A7<A8循环左移A1A2A3A4A5A6A7A8原数据-5-9-10-5273537第1次-9-10-5273537-5第2次-10-5273537-5-9第3次-5273537-5-9-10第4次273537-5-9-10-5第5次73537-5-9-10-52第6次3537-5-9-

10、10-527第7次37-5-9-10-52735MIN= (-10,-9,-5,-5)MAX= (37,35,7,2) b)B序列是双调序列，因为 B序列在经过 10次左循环后，满足B1>B2>B3>B4>B5=B6=B7>B8>B9>B10>B11<B12<B13<B14<B15<B16循环左移B1B2B3B4B5B6B7B8B9B10B11B12B13B14B15B16原数据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次121931302922212121181410-6-40第8次219