算法分析及设计2016-第1讲.ppt

? 1 2 3 4 1 2 3 4 2 1 4 3 2 1 4 3 3 4 1 2 4 3 2 1 1 2 3 4 5 6 7 8 ? 2 1 4 3 6 5 8 7 1 2 3 4 5 6 7 8 3 4 1 2 7 8 5 6 2 1 4 3 6 5 8 7 4 3 2 1 5 6 7 8 3 4 1 2 7 8 5 6 5 6 7 8 1 2 3 4 4 3 2 1 8 7 6 5 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 5 6 7 8 4 3 2 1 清扫污染的问题：一个 不错的分治算法 清扫污染的问题：一个 不错的分治算法 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 实例：给定一棵树T 询问：求一个清扫T的方案，所用清扫人数目最少。 什么是有哪些信誉好的足球投注网站方案？ 2种操作： (1)守住一个端点 (2)从一个端点有哪些信誉好的足球投注网站到另一个端点 (3)离开一个端点 算法分析与设计 2016，计算机科学与技术硕士研究生 第一章 算法分析技术 什么是算法:看上去与程序的定义相同。说清楚难，随着时代进步,也可以从更多的角度认识算法。 维基百科 是程序吗？是计算思想吗？要从几个方面描述才行。 (1)面对的问题不能太平凡， (2)面对的问题不能太复杂， (3)面对的问题要明确，输入输出数据形式化， (4)在现代数字计算机上能实现。 (5)所以要描述成一条一条的语句。 算法+数据结构=程序 第一章 算法分析技术 为什么要设计程序，因为要处理信息。为什么要设计算法，因为要解决问题。 问题就是描述让计算机干啥？ (1)问题；不是一般的问题，有意义的问题，凭感觉了。算法是针对问题的算法，没有问题，哪有算法？ (2)算法是程序，又不是程序。计算机语言描述的计算机求解问题的步骤，按照规定的步骤运行可以得到正确的结果。 数据结构+算法？=程序 例子：求1+2+3+……+n 可以编一个程序 也可以用公式计算： Sum=0; For i=1 to n Sum=Sum+i; End for Output Sum 也可以用公式计算： 一步就完成 Sum=n*(n+1)/2 Output Sum 勉强称为算法 称为算法太勉强 §1.1 算法及复杂性 算法从何入手，求解问题。计算机干什么？ 问题：什么是问题，怎么描述，日常生活中的问题描述，就是要让计算机干什么。输入，输出。 两个要素:输入和输出，要有严格的描述。 实例：描述问题的所有参量。输入数据包含哪些参量 询问：陈述问题所求的解的格式和解应满足的性质。 问题是告诉人的，不是告诉计算机的。 Instance 注意，计算机每次求解只是针对一个实例求解，问题的描述针对所有实例，给一个统一的描述。 算法：对每个问题实例计算机都能计算出满足询问条件的正确答案，的计算方法。是一个过程，语句集合，语句有次序，按照次序执行语句，处理实例，得到正确答案。对每个实例都能得到正确答案。 算法可以理解为一种计算方法，但这种方法一定能用计算机来计算，能用程序实现。 程序：算法在计算机上的具体实现。算法与程序没有本质区别，算法一般不关心在哪台计算机上运行。 程序关心。 例子：求xn，求幂问题 实例(Instance)：实数x和正整数n 询问(query)：xn=? n=10，x=2016.0913,求：2016.091310 每次计算x和n都不同，都是一个实例。 方法：算法， [1] x*x*x*x*x*x*x*x*x*x [2] y=x*x, z=y*y, w=z*z, x10