算法设计与分析(第2版)-郑宗汉-第1章-1.ppt

1、算法设计和分析，什么是算法？2，算法配置(1)问题(2)规则(3)结果，算法是解决任何问题的穷规则的集合。算法是将输入转换为输出的计算序列。根据课程概述、电脑系统的所有软件和特定算法实施。算法性能的好坏直接决定了实现的软件性能的优劣。算法性能确定方法、算法设计方法、设计的算法正常运行时间、存储空间数量等，都需要在软件实施中解决。因此算法设计和分析是计算机科学和技术的核心问题也是大学电脑科系本科生和研究生的重要专业基础课程之一。3，课程内容，第1部分(1-2章):基本概念和常用数学工具(6小时)第2部分(3-11章):排序、递归、分段、贪心法、动态规划、回溯法等基本理论和技术清华大学出版社，第2

2、板块D. E. Knuth等。art of the computer programming、vol.3、Addison-Wesley、1973.a.v.aho、J. D. Ullman等。the design and analysis of computer algorithms . Addison-Wesley、1974.a.v.aho、J. D. Ullman等。data structures and algorithms . Addison-Wesley，1983.4 . s . puter algorithms 3360 introduction to design

3、 and analysis . addisis journals Ieee transactions on electronic computers Ieee transactions on software engineering Ieee transactions on data and knowledge engineering annual ACM symposium on theory of computing annual IEEE symposium on foundations of computer science ACM annual computer science co

4、nference annual M n，n r，返回第一步。1.1.1算法定义和特性，最大公约数问题：查找两个正整数M和N的最大公约数，输入：一个算法有0个或更多输入。外部提供的算法运行前的初始值或初始状态。算法输入是从特定对象集合中提取的。在算法过程中，从正整数集中提取两个输入M，N。，输出：有一个或多个算法输出。这些输出与输入有一定关系，实际上是一种函数输入。徐璐输入其他值徐璐生成其他结果的输出。算法中的输出是输入M，N的最大公约数。限制：执行有限的步骤后，必须算法退出。在算法(欧氏算法)中，对于输入的正整数M，N，M除以N的余数R，然后通过R给出N，使N的值变小。这样往复最终可以使R等于

5、0，或将N减为1。在这两种情况下，r=0牙齿，算法结束。确定性：算法的每个步骤都有正确的定义。要执行的所有动作都清晰、不含糊。例如，如果算法3行中的M，N牙齿是无理数，则M除以N的馀数，就没有明确的定义了。确定性的说明意味着运行第3行时，必须确保M和N的值为正整数。根据算法规定，M，N都是正整数，因此在后续的每个阶段都可以明确执行。可行性：算法中需要实现的所有运算都是基本运算。原则上，人们可以使用纸和笔在有限的时间内准确地完成。算法中的除法、判断、分配等运算都是可能的。因为整数可以用有限的方式表示。如果涉及的数值必须准确地完成，而不是无限小数扩展的意外，则这种运算是不可能的。注意：限制不足。实

6、用的算法，不仅需要有限的步骤，而且需要执行这些步骤的时间是人们可以接受的。特性：(1)输入(2)输出(3)有限(4)可确定性(5)可行性，14，1.1简介1.1.1算法定义和特性1.1.2算法设计和复杂性分析以A为公鸡数，b母鸡数，c为小鸡数，1.1.2算法设计和复杂性分析，输入：购买的3种鸡的总数N输出：满足问题的数量K，公鸡，母鸡，小鸡的数量G，M，S，1。VoidChicken _ Question知道每个城市之间的距离，求出总行程最短的路线。19，最短路径的哈密顿回路问题，数据结构全向权图G=，V是顶点集，E是距离集。1.1.2算法设计和复杂性分析，货郎承担问题的宫商法算法，输入：城市数n，成本(距离)矩阵c输出：旅行路线t，最小成本min，1。void salesman _ problem，20，1 . 1.1.2算法设计和复杂性分析，货郎问题的运行时间和问题规模之间的关系，(假设每次运行循环体一次需要1s时间)，21，1 . 1 . 2算法设计和复杂性分析，思考，白溪问题宫法改善画廊承担问题的宫算法时间什么是有效的算法？如何判断其中一个算法是否更有效？22，表明算法改进设计方法对提高算法性能非常重要。说明穷法对不太大的(货物和负担问题)都行不通。如果一个问题有两个算法，你怎么知道一个牙齿算法比