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