下载文档原格式
第5章算法与复杂性习题一、选择题1. B2. D3. C4. A5. B6. B7. D8.B9.C 10.A11.A 12.C 13.A 14.A二、简答题1．什么是算法，算法的特性有哪些？答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。
算法的特性有：(1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。
(2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。
(3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。
(4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。
2．什么是算法的时间复杂度和空间复杂度，如何表示？答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。
记为，T(n)，其中，n代表求解问题的规模。
算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。
简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。
记为，S(n)，其中，n代表求解问题的规模。
时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。
3．用图示法表示语言处理的过程。
答：语言处理的过程如图所示：4．简述算法设计的策略。
答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。
一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。
要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。
通常可以利用实验对比分析、数学方法来分析算法。
实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。
1.并行算法:一些可同时执行的诸进程的集合，这些进程相互作用和相互协调。
2.并行与并发的关系：并行<并发并发是指两个或者多个事件在同一时间间隔内发生。
在单处理机系统中，每一时刻仅能有一道程序执行，宏观上多道程序在同时运行，微观上这些程序是分时交替执行。
3.并行与分布式的关系：网络；并行更注重性能，而分布式更注重透明共享。
4.并行与网格计算（普适计算）的关系：网格通过网络连接地理上分布的各类计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等，形成对用户相对透明的虚拟的高性能计算环境，让人们透明地使用这些资源和功能。
它们与并行计算存在规模上的差异。
5.并行与云计算的关系：云计算以开放的标准和服务为基础，以互联网为中心，提供安全、快速、便捷的数据存储和网络计算服务，让互联网这片“云”上的各种计算机共同组成数个庞大的数据中心及计算中心。
云计算把计算及存储以服务的形式提供给互联网用户，用户所使用的数据、服务器、应用软件、开发平台等资源都来自互联网上的虚拟化计算中心，该数据中心负责对分布在互联网上的各种资源进行分配、负载的均衡、软件的部署、安全的控制等。
6.为什么要研究并行算法？（1）CPU的发展速度：Moore Law。
（2）“深蓝”计算机以3.5:2.5战胜卡斯帕罗夫。
（3）需求：快速（天气预报），提高计算精度，与理论、实验并重的科学方法（代替核武器实验）7.并行计算机分类1. SISD,Single Instruction Stream & Single Data Stream:特征：串行的和确定的。
指令系统: CISC, RISC2. SIMD,Single Instruction Stream & Multiple Data Stream:特征：同步的；确定的；适合于指令/操作级并行。
1)阵列处理机（资源重复）;2)流水线处理机（时间重叠）.3. MISD,Multiple Instruction Stream & Single Data Stream :4. MIMD,Multiple Instruction Stream & Multiple Data Stream共享存储MIMD，也称对称多处理机（SMP，Symmetry MultiProcessors），属于紧密耦合的多处理机系统适合于小粒度并行分布式共享存储MIMD，也称为非一致内存访问（NUMA, Non-Uniform Memory Access），属于松耦合的多处理机系统（共享虚拟存储技术）,适合于中小粒度并行分布式存储MIMD1).大规模并行系统MPP (Massively Parallel Processing)CM-5、曙光1000、神州-Ⅱ巨型机可以最大限度地增加处理机的数量，但结点间需要依赖消息传递进行通信，适合于中小粒度并行2).群集系统Cluster特点：适合于粗粒度并行8.网络直径（network diameter）：网络中最远的两台处理机间的距离，即处理机间通信所需要跨越的网络边的条数的最大值。
1 •并行算法:一些可同时执行的诸进程的集合，这些进程相互作用和相互协调。
2•并行与并发的关系：并行v并发并发是指两个或者多个事件在同一时间间隔内发生。
在单处理机系统中，每一时刻仅能有一道程序执行，宏观上多道程序在同时运行，微观上这些程序是分时交替执行。
3•并行与分布式的关系：网络；并行更注重性能，而分布式更注重透明共享。
4•并行与网格计算（普适计算）的关系：网格通过网络连接地理上分布的各类计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等，形成对用户相对透明的虚拟的高性能计算环境，让人们透明地使用这些资源和功能。
它们•并行计算存在规模上的差显。
5•并行与云计算的关系：云计算以开放的标准和服务为基础，以互联网为中心，提供安全、快速、便捷的数据存储和网络计算服务，让互联网这片“云”上的各种计算机共同组成数个庞大的数据中心及计算屮心。
云计算把计算及存储以服务的形式提供给互联网用户，用户所使用的数据、服务器、应用软件、开发平台等资源都來自互联网上的虚拟化计算中心，该数据中心负责対分布在互联网上的各种资源进行分配、负载的均衡、软件的部署、安全的控制等。
6•为什么要研究并行算法？（1）CPU 的发展速度：Moore Law0（2）“深蓝”计算机以3.5:2.5战胜卡斯帕罗夫。
（3）需求：快速（天气预报），提高计算精度，与理论、实验并重的科学方法（代替核武器实验）7•并行计算机分类1.SISD,Single Instruction Stream & Single Data Stream:特征：串行的和确定的。
指令系统:CISC, RISC2.SIMD,Single Instruction Stream & Multiple Data Stream:特征：同步的；确定的；适合于指令/操作级并行。
1）阵列处理机（资源重复）；2）流水线处理机（时间重叠）.3・ MISD,Multiple Instruction Stream & Single Data Stream :4.MIMD,Multiple Instruction Stream & Multiple Data Stream共享存储MIMD,也称对称多处理机（SMP, Symmetry MultiProcessors）,属于紧密耦合的多处理机系统适合于小粒度并行分布式共享存储MIMD,也称为非一致内存访问（NUMA, Non-Uniform Memory Access），属于松耦合的多处理机系统（共享虚拟存储技术），适合于屮小粒度并行分布式存储MIMD1）.大规模并行系统MPP （Massively Parallel Processing）CM・5、曙光1000、神州・II巨型机可以最大限度地增加处理机的数量，但结点间需要依赖消息传递进行通信，适合于中小粒度并行2)・群集系统Cluster特点：适合于粗粒度并行8•网络直径(network diameter)：网络中最远的两台处理机间的距离，即处理机间通信所需要跨越的网络边的条数的最人值。
第4章 并行算法的设计基础
习题例题：
1.试证明Brent 定理：令W (n)是某并行算法A 在运行时间T(n)内所执行的运算数量，则A 使用p 台处理器可在t(n)＝O(W(n)／p+T(n))时间内执行完毕。
2.假定P i （1≤i ≤n ）开始时存有数据d i , 所谓累加求和指用 MERGEFORMAT 1i j j d =￥来代替P i 中的原始值d i 。
算法 PRAM-EREW 上累加求和算法
输入： P i 中保存有d i , l ≤ i ≤ n
输出： P i 中的内容为i j
j l d
=￥begin for j = 0 to logn – 1 do for i = 2j + 1 to n par-do (i) P i = d i-(2^i)(ii) d i = d i + d i-(2^j)endfor endfor end (1)试用n=8为例，按照上述算法逐步计算出累加和。
(2)分析算法时间复杂度。
3.在APRAM 模型上设计算法时，应尽量使各处理器内的局部计算时间和读写时间大致与同步时间B 相当。
当在APRAM 上计算M 个数的和时，可以借用B 叉树求和的办法。
假定有j 个处理器计算n 个数的和，此时每个处理器上分配n/p 个数，各处理器先求出自身的局和；然后从共享存储器中读取它的B 个孩子的局和，累加后置入指定的共享存储单元SM 中；最后根处理器所计算的和即为全和。
算法如下：算法 APRAM 上求和算法
输入： n 个待求和的数
输出： 总和在共享存储单元SM 中
Begin
(1)各处理器求n/p 个数的局和,并将其写入SM 中
(2)Barrier
(3)for k = [ log B ( p(B – 1) + 1) ] – 2 downto 0 do
3.1for all P i , 0 ≤ i ≤ p – 1,do
if P i 在第k 级 then。
