《并行算法设计与分析》考题与答案
一、1.3，处理器PI的编号是：
解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。

以16处理器网孔为例,n=4（假设j、k由0开始）：
由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0)
P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1)
P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2)
P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3)
P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0)
P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1)
P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2)
P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3)
同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k
一、1.6矩阵相乘（心动算法） a)相乘过程 设
A 矩阵=
121221122121
4321 B 矩阵=1
23443212121121
2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1
2、
4、
6、
8、
10
计算完毕
b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10
二、（2.1）
a)示例n=8时算法的计算过程：
b)证明上述算法的复杂度T(n)=O(LOG n)，W(n)=O(n)
证明：ALGORITHM Prefix Sum T(n ) W (n) （1）if n=1 then ……O (1) W1(n )=O (1)
(2) for ……O (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>1
W(n)= { O(1) , n=1
{ W(n/2)+O(n) , n>1
展开解得：
T（n）=O (log n )
W(n)= O(n)
二（2.3）、
a) lgn
b)如果不是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,-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序列是双调序列，因为A序列在经过7次左循环后满足A1>A2>A3>A4<A5<A6<A7<A8
MIN=（-10,-9,-5,-5）
MAX=（37,35,7,2）
b)
B序列是双调序列，因为B序列在经过10次左循环后，满足
Max=( 31，30，29，22，21，21，21，19，18 )
Min=( -6，-4，0，1，2，3，10 ，14)。