文档介绍：并行算法的一般设计策略
习题例题:
1、令n是待排序的元素数,p=2d是d维超立方中处理器的数目。假定开始随机选定主元x,并将其播送给所有其他处理器,每个处理器按索接收到的x,对其n/p个元素按照≤ x和>x进行划分,然后按维进行交换。这样在超立方上实现的快排序算法如下:
超立方上快排序算法
输入: n个元素,B = n/p, d = log p
输出: 按超立方编号进行全局排序
Begin
id = processor’s label
for i=1 to d do
() x = pivot / * 选主元* /
() 划分B为B1和B2满足B1 ≤B<B2
() if 第i位是零 then
(i) 沿第i维发送B2给其邻者
(ii) C = 沿第i维接收的子序列
(iii) B= B1∪C
else
(i) 沿第i维发送B1给其邻者
(ii) C = 沿第i维接收的子序列
(iii) B= B2∪C
endif
endfor
使用串行快排序算法局部排序B = n/p个数
End
①试解释上述算法的原理。
②试举一例说明上述算法的逐步执行过程。
2、①令T = babaababaa。P =abab,。
②试分析KMP算法为何不能简单并行化。
3、给定序列(33,21,13,54,82,33,40,72)和8个处理器,-CRCW模型上执行快排序所用的二叉树。
4、计算duel(p, q)函数的算法如下:
计算串匹配的duel(p, q) 的算法
输入: WIT〔1: n-m+1〕,1≤p<q≤n-m+1,(p - q) < m/2
输出: 返回竞争幸存者的位置或者null(表示p和q之一不存在)
Begin
if p=null then duel= q else
if q =null then duel= p else
(1) j= q - p +1
(2) w=WIT(j)
(3) if T(q+w-1) ≠ P(w) then
(i) WIT(