中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第六章 并行算法的基本设计技术

第六章并行算法的基本设计技术 习题例题: 1.①试证明:当n≥p时,算法61的时间复杂度为 olog n ②令v表示P中第j段中的元素数,试证明算法6.1在执行过程中,处理器中所积累 的元素数目不会超过2n/p, 即S P 2.①试举一典型算例,说明 valiant归并算法的执行过程。 ②试分析算法6.2所需的处理器数p(m)=O(m)。 ③试证明算法62的时间复杂度为:2 oblog+onst 3.①试分析算法6.3的时间复杂度。 ②令A=(0,1,2,7,9,11,16,17,18,19,23,24,25,27,28,30,33,34) B=(3,4,5,6,8,10,12,13,14,15,20,2,26,29,31)。试按算法63,将其 进行对数划分,并最终将它们归并之 ①试证明 Batcher定理。 ②画出一个16个输入的双调归并网络。 5.①试分析算法69的总运算量W()=? ②假定序列为(1,2,3,4,5,6,7,8),试用算法69求其前缀和 试解释在一维心动阵列上计算卷积时,序列x和y为何要各间隔一拍进入阵列

第六章 并行算法的基本设计技术 习题例题： 1. ①试证明：当 3 n  p 时，算法 6.1 的时间复杂度为         n p n O log 。 ②令 j wi 表示 Pi 中第 j 段中的元素数，试证明算法 6.1 在执行过程中，处理器中所积累 的元素数目不会超过 2n / p ，即 =  p j j i p n w 1 2 。 2. ①试举一典型算例，说明 Valiant 归并算法的执行过程。 ②试分析算法 6.2 所需的处理器数 p(n) = O(n) 。 ③试证明算法 6.2 的时间复杂度为：2loglogn+const。 3. ①试分析算法 6.3 的时间复杂度。 ②令 A=(0，1，2，7，9，11，16，17，18，19，23，24，25，27，28，30，33，34)， B=(3，4，5，6，8，10，12，13，14，15，20，22，26，29，31)。试按算法 6.3，将其 进行对数划分，并最终将它们归并之。 4. ①试证明 Batcher 定理。 ②画出一个 16 个输入的双调归并网络。 5. ①试分析算法 6.9 的总运算量 W(n) = ? ②假定序列为(1，2，3，4，5，6，7，8)，试用算法 6.9 求其前缀和。 6. 试解释在一维心动阵列上计算卷积时，序列 x 和 y 为何要各间隔一拍进入阵列