第五章并行算法的一般设计策略 习题例题: 1、令n是待排序的元素数,p=24是d维超立方中处理器的数目。假定开始随机选定主元 x,并将其播送给所有其他处理器,每个处理器按索接收到的x,对其m个元素按照≤x和 >x进行划分,然后按维进行交换。这样在超立方上实现的快排序算法如下: 算法56超立方上快排序算法 输入:n个元素,B=mp,d=logp 输出:按超立方编号进行全局排序 (1)id= processor's label (2)for i=l to d do (2.1)x=pivot /*选主元*/ (22)划分B为B1和B2满足B1≤B<B (2.3)if第i位是零then (i)沿第i维发送B2给其邻者 (i)C=沿第i维接收的子序列 (iiiB=B1UC (i)沿第i维发送B1给其邻者 (i)C=沿第i维接收的子序列 (ili) B= B2UC dfor 3)使用串行快排序算法局部排序B=mp个数 ①试解释上述算法的原理 ②试举一例说明上述算法的逐步执行过程 2、①令T= babaababaa。P=abab,试用算法54计算两者的匹配情况。 ②试分析KMP算法为何不能简单并行化 3、给定序列(33,21,13,54,82,33,40,72)和8个处理器,试按照算法52构造 棵为在 PRAM-CRCW模型上执行快排序所用的二叉树 4、计算duel(p,q函数的算法如下 算法57计算串匹配的duel(p,q)的算法 输入:WT(1:nm+1),1≤p<q≤nm+1,p-q)<m2 输出:返回竞争幸存者的位置或者nul(表示p和q之一不存在) fp=null then duel=g else if g =null then duel= p else (1)=q-P+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’s label (2) for i=1 to d do (2.1) x = pivot / * 选主元 * / (2.2) 划分 B 为 B1 和 B2 满足 B1 ≤B＜B2 (2.3) 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 (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 构造一 棵为在 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 之一不存在） Begin if p=null then duel= q else if q =null then duel= p else (1) j= q - p +1