第1单元 算法引论.pptVIP

算法设计与分析 王晓东 编著 联系方式: 办公地点:信息学院二层软件工程系204 办公电话: 029 学习算法的理由： 一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具。 ——George Forsythe 《计算机科学家到来以前我们做什么》1968 算法是计算机科学的基石。学习算法的理由是非常充分的。没有算法，计算机程序将不复存在，另一个学习算法的理由是可以用它来开发人们的分析能力。 算法可以看作是解决问题的一类特殊方法——它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。 因此，无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。 计算机专业的学生： 程序=算法+数据结构 算法让我们上一个更高的台阶 算法的魅力：思考 对学生的要求: 坚持!坚持就是胜利! 看懂每一道讲授的题目、完成作业、完成实习题目。 上课：不旷课、不迟到。 作业：每章两个算法设计题，提交作业本。 实习：第二章~第六章，每章一个算法实现题目，将程序的源代码的压缩文件，提交到202.117.179.110（作业管理系统\王湘桃\计算机1~3班） 主要内容介绍 第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 主要内容介绍（续） 第7章 概率算法 第9章 NP完全性理论与近似算法 第1章 算法引论 1.1 算法与程序 1.2 表达算法的抽象机制 1.3 算法复杂性分析 1.1 算法与程序 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 1.1 算法与程序 求：非负整数M和N的最大公约数， 记为：Gcd(m,n) 方法一：欧几里得算法 Gcd(m,n)=Gcd(n, m mod n) Gcd(60,24)=Gcd(24,12)=Gcd(12,0)=12 1.1 算法与程序 方法二：连续整数检测算法 （1）将 min(m,n) 的值赋给t。 （2）m除以t，如果余数为0，进入第3步，否则，进入第4步。 （3）n除以t，如果余数为0，返回t值，结束，否则，进入第4步。 （4）t=t-1 ，返回第2步。 1.1 算法与程序 方法三：中学里计算Gcd(m,n)的过程（用数学定义的方法） （1）找到m的所有质因数。 （2）找到n的所有质因数。 （3）找到（1），（2）中的公因数。 （4）求公因数的积，该乘积为m、n的最大公约数。 1.1 算法与程序 理解问题 在设计一个算法前，我们需要做的第一件事就是完全理解所给出的问题，仔细阅读问题的描述，如有任何疑惑就把疑问提出来，手工处理一些小例子，考虑一下特殊情况，有必要的话再继续提出疑问。 严格确定算法需要处理的实例范围是非常重要的。如果不这样做，算法可能会对大多数的输入正确处理，但遇到某些“边界值”的时候就出错。 记住，一个正确的算法不仅应该能处理大多数的情况，而且应该能正确处理“所有”合法的输入。 1.1 算法与程序 了解计算机设备的性能 今天使用的大多数算法仍然要运行于冯·诺依曼计算机上。这个体系结构的重点在于随机存取机。它最主要的设想是：指令逐条运行，每次执行一步操作。相应地，设计运行于这种机器上的算法，称为顺序算法。 一些更新式的计算机可以在同一时间执行多条操作，即并行计算，能够利用这种计算性能优势的算法称为并行算法。 尽管如此，在可预见的未来，学习RAM模型下算法设计和分析的经典技术仍然是算法学的基石。 1.1 算法与程序 在精确解法和近似解法间做选择 精确的解法称为精确算法。 近似的解法称为近似算法。（无法求得精确解[求平方根问题]或由于某些问题固有的复杂性，用已知的精确算法来解决该问题会慢得无法接受[旅行售货员问题]） 1.1 算法与程序 确定适当的数据结构 算法和数据结构是计算机编程的重要基础。 程序=算法+数据结构 1.1 算法与程序 算法设计技术 什么是算法设计技术？是用算法解题的一般性