法与另一个非常快但非最优的算法“串接”起来,形成一个快速最优的算法,此法虽不具有 普适性.但对有些问题却效果甚佳;随机法是在算法设计时,引入随机性使得算法在执行时 可以随机地选择下一执行步,从而可望得到平均性能较好的算法(即其复杂度比同一问题的 确定性算法的最坏情况的复杂度要好),随机算法设计简单,但分析较复杂,经常要分析算 法可在多少时间步内以多大的概率结束,用随机法设计的算法,其运行结果也可能是不正确 的,但这种错误的概率应是很小的;贪心法( Greedy Method)是一种最直接的设计技术,其设 计特点是.在算法的每一步都力图确保获得局部最优,这种设计方法的副作用是容易陷入局 部最优。对于组合问题的算法设计技术,有动态规划法( Dynamic Programming),它是在每 判定步,列出多种可能的解,然后按照某种条件,舍弃那些肯定不能导致最优解的局部解, 它和贪心法的区别在于,贪心法仅产生一个判定序列,而动态规划法可能产生很多判定序列, 但依据“最优性原理“,非局部最优解的序列肯定不是最优的,所以不予考虑:回溯法 ( Backtracking)是一种穷举法,在问题求解时常使用深度优先搜索( Depth- First searching)快, 在搜索过程中,一旦碰到某个无法搜索下去的分支,就向其父节点回溯,再搜索该父节点的 其它分支,如果所有的分支节点均无希望的解,则再向上追溯,如此等等,回溯法虽提供了 一种规律性求解的方法,但其时间复杂度较高:分支界限法 Branch and bound)与回溯法颇 类似.但它是基于广度优先搜索( Breadth- First searching)法,它利用部分解的最优性信息, 避免考虑那些不能导致最优的解,以加快问题的求解,其解题过程是:对解集合反复进行分 支,即反复构造其子集合,每次分支时都对所得到的子集合计算最优解的界,若它不能优于 当前已知的最优解,则对此子集合就不再进行分支,否则继续分支,以探索更好的解,直到 所得的子集合仅有一个解为止。 第七章小结本章已经描述了并行算法设计的四个步骤:首先将给定问题划分成一些小的任 务,划分方法可以使用域分解法或功能分解法;其次分析诸任务之间的通信需求,通信可以 是局部的和全局的,静态的和动态的,结构化的和非结构化的以及同步的和异步的:然后使 用组合方法.在尽可能保持灵活性的同时,减少通信和开发成本:最终以最小化总执行时间 为目标将诸任务分配给处理器,使用负载平衡和任务调度技术可以改善映射的质量,在每个 设计步骤之后均列出了相应的设计检验推则以评价设计的好坏 经过上述四个步骤设计出的并行算法,在开始编码实现之前尚须考虑以下几件事:对算 法进行性能分析以选得好的算法,根据要求证实所作的设计是否满意,考虑算法具体实现时 的代价和代码重用的可能性:最终考虑如何将算法装配到一个更大的系统中去 第十章小结线性代数方程组的求解在科学和工程计算中应用非常广泛,这是因为很多科学 与工程问题的计算,最终大都可以化为线性代数方程组的求解。本章主要讨论最基本的线性 方程组的求解,包括三角形方程组、三对角方程组、稠密和稀疏线性方程组等的经典解法。 线性代数方程组的数值解法通常有两种:直接法和迭代法。直接法,又称消元法,是利 用矩阵变换技巧,将一般的系数矩阵化为特殊形式(如上三角和对角形式)的矩阵以对方程组 消解。其优点是可以预先估计运算量,并可得到问题的推确解,但由于实际计算过程中总存 在着舍入误差,因此直接法得到的结果并非绝对精确,并且还存在着计算过程的稳定性问题 迭代法是一种逐步求精的近似求解过程,此法一般总是假定方程组中的系数a≠0(i 1,…,n)。其优点是简单,易于计算机编程,但它存在着迭代是否收敛和收敛快慢的问题 迭代求解的过程是,先给定初始解,然后逐次迭代下去,且理论上讲,每次迭代的结果都 应改善前一次的计算结果。迭代过程由预先给定的精度要求来控制,但由于方程组的准确解 般是不知道的,因此判断某次迭代是否满足精度要求是困难的,通常我们总是认为当相邻 两次迭代值x(k)与x(k-l)也很接近时,x与x(k)也很接近,因此就可直接用条件法与另一个非常快但非最优的算法“串接”起来，形成一个快速最优的算法，此法虽不具有 普适性．但对有些问题却效果甚佳；随机法是在算法设计时，引入随机性使得算法在执行时， 可以随机地选择下一执行步，从而可望得到平均性能较好的算法(即其复杂度比同一问题的 确定性算法的最坏情况的复杂度要好)，随机算法设计简单，但分析较复杂，经常要分析算 法可在多少时间步内以多大的概率结束，用随机法设计的算法，其运行结果也可能是不正确 的，但这种错误的概率应是很小的；贪心法(Greedy Method)是一种最直接的设计技术，其设 计特点是．在算法的每一步都力图确保获得局部最优，这种设计方法的副作用是容易陷入局 部最优。对于组合问题的算法设计技术，有动态规划法(Dynamic Programming)，它是在每 一判定步，列出多种可能的解，然后按照某种条件，舍弃那些肯定不能导致最优解的局部解， 它和贪心法的区别在于，贪心法仅产生一个判定序列，而动态规划法可能产生很多判定序列， 但依据“最优性原理“，非局部最优解的序列肯定不是最优的，所以不予考虑：回溯法 (Backtracking)是一种穷举法，在问题求解时常使用深度优先搜索(Depth-First Searching)快， 在搜索过程中，一旦碰到某个无法搜索下去的分支，就向其父节点回溯，再搜索该父节点的 其它分支，如果所有的分支节点均无希望的解，则再向上追溯，如此等等，回溯法虽提供了 一种规律性求解的方法，但其时间复杂度较高；分支界限法(Branch and Bound)与回溯法颇 类似．但它是基于广度优先搜索(Breadth-First Searching)法，它利用部分解的最优性信息， 避免考虑那些不能导致最优的解，以加快问题的求解，其解题过程是：对解集合反复进行分 支，即反复构造其子集合，每次分支时都对所得到的子集合计算最优解的界，若它不能优于 当前已知的最优解，则对此子集合就不再进行分支，否则继续分支，以探索更好的解，直到 所得的子集合仅有一个解为止。 第七章小结 本章已经描述了并行算法设计的四个步骤：首先将给定问题划分成一些小的任 务，划分方法可以使用域分解法或功能分解法；其次分析诸任务之间的通信需求，通信可以 是局部的和全局的，静态的和动态的，结构化的和非结构化的以及同步的和异步的；然后使 用组合方法．在尽可能保持灵活性的同时，减少通信和开发成本；最终以最小化总执行时间 为目标将诸任务分配给处理器，使用负载平衡和任务调度技术可以改善映射的质量，在每个 设计步骤之后均列出了相应的设计检验推则以评价设计的好坏。 经过上述四个步骤设计出的并行算法，在开始编码实现之前尚须考虑以下几件事：对算 法进行性能分析以选得好的算法，根据要求证实所作的设计是否满意，考虑算法具体实现时 的代价和代码重用的可能性；最终考虑如何将算法装配到一个更大的系统中去。 第十章小结 线性代数方程组的求解在科学和工程计算中应用非常广泛，这是因为很多科学 与工程问题的计算，最终大都可以化为线性代数方程组的求解。本章主要讨论最基本的线性 方程组的求解，包括三角形方程组、三对角方程组、稠密和稀疏线性方程组等的经典解法。 线性代数方程组的数值解法通常有两种：直接法和迭代法。直接法，又称消元法，是利 用矩阵变换技巧，将一般的系数矩阵化为特殊形式(如上三角和对角形式)的矩阵以对方程组 消解。其优点是可以预先估计运算量，并可得到问题的推确解，但由于实际计算过程中总存 在着舍入误差，因此直接法得到的结果并非绝对精确，并且还存在着计算过程的稳定性问题。 迭代法是一种逐步求精的近似求解过程，此法一般总是假定方程组中的系数 aii ≠ 0 (i = 1,…,n)。其优点是简单，易于计算机编程，但它存在着迭代是否收敛和收敛快慢的问题。 迭代求解的过程是，先给定初始解，然后逐次迭代下去，且理论上讲，每次迭代的结果都 应改善前一次的计算结果。迭代过程由预先给定的精度要求来控制，但由于方程组的准确解 一般是不知道的，因此判断某次迭代是否满足精度要求是困难的，通常我们总是认为当相邻 两次迭代值 xi(k)与 xi(k-1)也很接近时，xi 与 xi(k)也很接近，因此就可直接用条件