算法设计及分析1.docVIP

第1章 算法设计基础 教学重点 算法及其重要特性；伪代码；算法设计的一般过程 教学难点 计算机学科的符号化特征 教学内容 和 教学目标 知识点 教学要求 了解 理解 掌握 熟练掌握 算法及其重要特性 √ 算法的描述方法 √ 算法设计的一般过程 √ 问题求解的一般过程 √ 计算机学科的符号化特征 √ 重要的问题类型 √ 1.1 算法的基本概念 1.1.1 算法及其重要特性 算法是计算机科学的基石。其定义为： 算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法五个重要特性： （1）输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。 （2）输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。 （3）有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。 （4）确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。 （5）可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 例1.1 设计算法求两个自然数的最大公约数。 解：设两个自然数是m和n，求解过程如下： 第1步：找出m的所有质因子 第2步：找出n的所有质因子 第3步：从第1步和第2步得到的质因子中找出所有公因子 第4步：将找到的所有公因子相乘，结果即为m和n的最大公约数 存在的问题？ 1.第1步和第2步没有明确定义如何找出一个自然数的所有质因子，而且分解质因数问题是一个NP完全问题，目前尚未找到有效的方法； 2.第3步也没有明确定义如何在两个长度不等的数列中找出所有相同的元素。因此，这个求解过程不满足算法的确定性和可行性。 评价一个“好”算法首先要满足算法的五个重要特性，此外，还要具备下列特性： （1）正确性：算法能满足具体问题的需求，即对于任何合法的输入，算法都会得出正确的结果。（2）健壮性：算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出处理，而不是产生错误动作或陷入瘫痪。（3）可理解性：算法容易理解和实现。算法首先是为了人的阅读和交流，其次是为了程序实现，因此，算法要易于人的理解、易于转换为程序。晦涩难懂的算法可能隐藏一些不易发现的逻辑错误。 （4）抽象分级：算法由人来阅读、理解、使用和修改必须用抽象分级来组织算法表达的思想。（5） 伪代码是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。 伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化了描述算法的不必要的技术细节，是比较合适的描述算法的方法，被称为“算法语言”或“第一语言”。 1.1.3 算法设计的一般过程 1. 理解问题首先搞清楚求解的目标是什么，给出了哪些已知信息、显式条件或隐含条件，应该用什么形式的数据表达计算结果。准确地理解算法的输入是什么要求算法做的是什么即明确算法的入口和出口，这是设计算法的切入点。 2算法设计技术算法设计技术（也称算法设计策略）是设计算法的一般性方法，包括蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、近似算法、概率算法等，这些算法设计技术构成了一组强有力的工具，在为新问题设计算法时，可以运用这些技术设计出新的算法。 3描述算法在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。4. 手工运行算法逻辑错误无法由计算机检测出来，因为计算机只会执行程序，而不会理解动机。经验和研究都表明，发现算法（或程序）中的逻辑错误的重要方法就是手工运行算法跟踪算法。跟踪者要像计算机一样，执行算法，并且这要最大可能地暴露算法中的错误。即使有几十年经验的高级软件工程师，也经常利用此方法查找算法中的逻辑错误。 分析算法的效率算法效率：时间效率和空间效率，时间效率显示了算法运行得有多快，空间效率则显示了算法需要多少额外的存储空间，相比而言，我们更关注算法的时间效率。事实上，计算机的所有应用问题，包括计算机自身的发展，都是围绕着时间——速度这样一个中心进行的。一般来说，一个好的算法首先应该是比同类算法的时间效率高，算法的时间效率用时间复杂性来度量。 6. 实现算法 需要强调的是，一个好算法是反复努力和重新修正的结果。 1.2 为什么要学习和研究算法 1.2.1 算法在问题求解中的地位 用计算机求解问题的一般过程如图1.3所示。 由问题到想法需要分析问题，抽象出具体的数据模型，形成问题求解的基本思路；由想法到算法需要完成数据表示（将数据模型存储到计算机的内存中）和数