《并行算法的一般设计策略》由会员分享，可在线阅读，更多相关《并行算法的一般设计策略（3页珍藏版）》请在金锄头文库上搜索。
1、第五章并行算法的一般设计策略习题例题：1 、令 n 是待排序的元素数，p 2 d 是 d 维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x，对其 n/p 个元素按照 x和 x 进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下：算法 5.6 超立方上快排序算法输入： n 个元素， B= n/p ,d =log p输出： 按超立方编号进行全局排序Begin(1) id=processor slabel(2) for i=1 to ddo(2.1) x=pivot/*选主元 */(2.2) 划分 B 为 B1 和 B2 满足 B1 B
2、B2(2.3) if 第 i 位是零 then(i) 沿第 i 维发送 B2 给其邻者(ii)C= 沿第 i 维接收的子序列(iii)B=B 1 Celse(i) 沿第 i 维发送 B1 给其邻者(ii)C= 沿第 i 维接收的子序列(iii)B=B 2 Cendifendfor(3) 使用串行快排序算法局部排序B= n/p 个数End试解释上述算法的原理。试举一例说明上述算法的逐步执行过程。2 、令 T=babaababaa。 P=abab ，试用 算法 5.4 计算两者的匹配情况。试分析KMP 算法为何不能简单并行化。3 、给定序列（ 33 ，21 ，13 ，54 ， 82 ，33 ，40
3、 ， 72 ）和 8 个处理器，试按照算法 5.2 构造一棵为在 PRAM-CRCW模型上执行快排序所用的二叉树。4 、计算 duel( p ,q )函数的算法如下：算法 5.7 计算串匹配的duel( p ,q )的算法输入： WIT 1:n-m+1， 1 p q n-m+1， (p - q ) m/2输出： 返回竞争幸存者的位置或者null （表示 p 和 q 之一不存在）Beginif p =null then duel= qelseif q =null then duel=pelse(1) j= q - p+1(2) w=WIT( j)(3) if T(q + w-1) P(w )th
4、en (i)WIT( q )= w(ii)duel=pelse(i)WIT( p )= q p+1(ii)duel=qendifendifEnd令 T=abaababaababaababababa。P=abaababa，试计算 WIT( i)；试考虑 P=6 ， q=9的竞争情况。5 、对于 图 5.2(a) 的加权有向图，试用 算法 5.5 ，逐步求出 D 2 ， D 4 和 D 8 中各元素 dijk：d 002d012d022d 032d042d 052d062d002d012d022d 032d042d 052d062d102d112d122 d132d142d152 d162d102
5、d112d122d132 d142d152 d162d 602d612d622d 632d642d 652d662d602d612d622d 632d642d 652d662(a) D2 (b) D 4d 002d012d022d 032d042d 052d062d102d112d122d132 d142d152 d162d 602d612d622d 632d642d 652d662(a)D 8小结设计并行算法是一件复杂的事， 而并行算法的设计这门学科还属于发展中的一门学科，所以目前尚无一套普遍适用的、系统的设计方法学。 本章只是给出一个非常一般的并行算法的设计方法，它不可能也不应该视为设计并行算法的全部方法。重要的是，通过所介绍的设计方法的学习， 希望读者能从中得到更多的启迪，补充更多的算例，丰富、完善乃至开拓出更新更好的设计方法。
