第1章算法设计序言精选文档.ppt

《第1章算法设计序言精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章算法设计序言精选文档.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章算法设计序言本讲稿第一页，共二十九页nAre you thinking about these questions?Why do we need to study this course?What should we learn in the course?How about the instructor?Is it hard to pass the exams?I am not good in Math.My background is not strong.I can read little English.NO PROBLEM Welcome!本讲稿第二页，共二十九页课程介绍n学时

2、：32学时+16实验n考试方式：考试 成绩：20%中期考试+10%平时+70%期末n教材：王晓东，算法设计与分析（第二版），清华大学出版社；n参考资料：1张德富，算法设计与分析，国防工业出版社；2Michael T.Goodrich，算法分析与设计，人民邮电出版社。3 Kleinberg 等,算法导论,清华大学出版社本讲稿第三页，共二十九页主要内容介绍n第1章算法引论n第2章递归与分治策略n第3章动态规划n第4章贪心算法n第5章回溯法n第6章NP完全性理论本讲稿第四页，共二十九页课程信息n20092009年计算机学院算法选修课年计算机学院算法选修课:选修人数选修人数:112:112 参加期末考

3、试人数参加期末考试人数:79:79 合格人数合格人数:57:57最高分最高分:94:94n20112011年计算机学院算法必修课年计算机学院算法必修课:选修人数选修人数:100:100 平均分：平均分：68.7 68.7 最高分最高分:89:89n建议建议:1.If you do not like math or analysis or logic,please note that the course may be a high load for you.（this course needs your time）2.Read the lecture notes carefully,which

4、 will be more helpful for you than the text books.3.Make sure that you can solve the problems that I put highlines in the course.本讲稿第五页，共二十九页1.1 基本介绍本讲稿第六页，共二十九页思考n什么是计算机你为什么选择这个专业？什么是计算机你为什么选择这个专业？n计算机和一般机械的差别在哪里？计算机和一般机械的差别在哪里？n我们需要计算机来做什么？我们需要计算机来做什么？n什么是计算机问题？什么是计算机问题？ComputerInputsOutputs本讲稿第七页

5、，共二十九页计算机问题n计算机问题计算机问题：A task to be performed by computers （需要计算机解决的任务）（需要计算机解决的任务）Problems Mathematical function from inputs to matching outputs.（输入到对应输出的一个数学功能）（输入到对应输出的一个数学功能）A particular input must always result in the same output every time the function is computed（每次同样的输入计算机给出同样的输出）（每次同样的输入计算机

6、给出同样的输出）Problem definition should include constraints on the resources that may be consumed by any acceptable solution（问题定义时需要给出对计算机解决问题时所能用的资源的规定，（问题定义时需要给出对计算机解决问题时所能用的资源的规定，比如说运行时间、内存等）比如说运行时间、内存等）本讲稿第八页，共二十九页三种不同的计算机问题三种不同的计算机问题nDecision Problem(判断问题，回答判断问题，回答yes或者或者no)比如：输入的数是否大于比如：输入的数是否大于60nO

7、ptimal Problem（优化问题，求最优解）（优化问题，求最优解）比如：从比如：从A到到B的最短路径是什么？的最短路径是什么？nNumerical Calculation（数值计算）（数值计算）比如说用计算机求方程或积分等，这些问题都属于数值计算中比如说用计算机求方程或积分等，这些问题都属于数值计算中本讲稿第九页，共二十九页Algorithms（算法）n1.a method or a process followed to solve a problem using a computern2.takes the input of a problem and transforms it t

8、o the output n3.A problem can have many algorithmsComputerInputsOutputs什么是算法?问题 算法程序本讲稿第十页，共二十九页Algorithm Properties（算法的性质）Must be correct 算法必须是算法必须是正确正确的的Composed of a series of concrete steps包含一系列包含一系列具体具体的步骤的步骤No ambiguity as to which step will be performed next 在执行算法时没有在执行算法时没有二义性二义性Composed of

9、a finite number of steps 只包含只包含有限有限步步Must terminate必须必须终止终止本讲稿第十一页，共二十九页n输 入：有零个或多个外部量作为算法的输入。n输 出：算法产生至少一个量作为输出。n确定性：组成算法的每条指令清晰、无歧义。n有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是满足下述性质的指令序列。算法：本讲稿第十二页，共二十九页程序（program）与算法（algorithm）计算机程序是算法用某种程序语言的一个具体表示计算机程序是算法用某种程序语言的一个具体表示 一个一个Java程序和一个程序和一个C语言程序可能做的是同一个事情，

10、这两个语言程序可能做的是同一个事情，这两个语言表达的就是同一个算法语言表达的就是同一个算法 计算机计算机程序程序是用来给是用来给计算机计算机读的读的而而算法算法是给是给人人来读的，直接将算法输入计算机是不能运行的来读的，直接将算法输入计算机是不能运行的Algorithms can be expressed by pseduocodes（伪代码）（伪代码）or just some short steps that are easy to read and understand本讲稿第十三页，共二十九页对计算问题的算法设计算法设计思想总结选用该问题的一个数学模型选用该问题的一个数学模型-在已知条件

11、下的初始状态、结束状态和状态关系-从已知状态到达结束状态的运算步骤-形成算法为了将两层运算隔开，使二者在设计时不互相影响必须对二者的接口进行抽象。让为了将两层运算隔开，使二者在设计时不互相影响必须对二者的接口进行抽象。让底层通过接口为顶层服务，顶层通过接口调用底层运算。这个接口就是底层通过接口为顶层服务，顶层通过接口调用底层运算。这个接口就是抽象数据类抽象数据类型型(abstract data types,ADT)顶层运算步骤顶层运算步骤底层运算步骤底层运算步骤自顶向下数据模型级数据结构级本讲稿第十四页，共二十九页常用算法设计方法常用算法设计方法nExhaustive search（穷举搜索）

12、Greedy method（贪心法）nDivide-and-conquer（分而治之法）nDynamic programming（动态规划）nBack tracking（回溯法）nBranch-and-bound（分支定界法）n本讲稿第十五页，共二十九页1.1.2 2 一些算一些算法问题法问题本讲稿第十六页，共二十九页活动安排问题活动安排问题nInput.Input.一系列活动，每个活动有一个起始时间和结束时间一系列活动，每个活动有一个起始时间和结束时间.nGoal.Goal.找出最大一组活动，使得这些活动两两的时间不重叠。找出最大一组活动，使得这些活动两两的时间不重叠。Time0123456

13、7891011fgheabcdheb本讲稿第十七页，共二十九页带权重的活动安排问题带权重的活动安排问题nInput.Input.一系列活动，每个活动有一个起始时间和结束时间，还一系列活动，每个活动有一个起始时间和结束时间，还有一个权值。有一个权值。nGoal.Goal.找出一组权重最大的活动，使得这些活动两两的时间不重找出一组权重最大的活动，使得这些活动两两的时间不重叠。叠。Time012345678910112011161323122026本讲稿第十八页，共二十九页二分图匹配问题二分图匹配问题C152AE3BD4nInput.Input.一个二分图一个二分图.nGoal.Goal.找出数量最

14、多的一组边，使得这组边中任何两条都没有公找出数量最多的一组边，使得这组边中任何两条都没有公共顶点。共顶点。本讲稿第十九页，共二十九页最大独立集问题最大独立集问题62517346514nInput.Input.一个图一个图.nGoal.Goal.找出图中数量最多的一组点，使得这组点中任何两找出图中数量最多的一组点，使得这组点中任何两点间都不存在一条边。点间都不存在一条边。本讲稿第二十页，共二十九页1.1.3 3 算法复算法复杂性分析杂性分析本讲稿第二十一页，共二十九页一个故事一个故事 n在席盖莫夫著的从一到无穷大中记载着一个关于古印度舍罕王（Shirham）的故事：n 舍罕王打算重赏“国际象棋”

15、（真正的国际象棋是后来进化演变来的）的发明人和进贡者，宰相西萨班达伊尔（Sissa Ben Dahir）。这位聪明的大臣的胃口看来并不大，他跪在国王面前说：“陛下，请您在这张棋盘的第一个小格内，赏给我一粒麦子；在第二个小格内两粒，第三个给四粒，照这样下去，每个小格内都比以前一个小格加一倍。陛下啊，把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人罢！”舍罕王听后很生气，说：”你也太小看我们印度国了，我拿一袋子麦子全给你好了。“n 西萨班达伊尔坚持说还是按要求放满好。最后大家拿了许多袋麦子过来都只完成了一小部分的填充工作，大家这才感觉到问题的严重。本讲稿第二十二页，共二十九页什么问题？什么问题？n

16、Shirhams story.The amount of wheat012323632021222322326312488388608 9223372036854775808 Sum371516777215 18，446，744，073，709，551，615.本讲稿第二十三页，共二十九页算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性时间复杂性，需要的空间资源的量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该

17、有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在复杂性函数名当中）本讲稿第二十四页，共二十九页1.4 算法复杂性分析主要问题：如何将复杂性函数具体化？根据T（N,I)的概念，它应该是算法在一台抽象的计算机上运行所需要的时间。u设此抽象的计算机所提供的元运算有k种，分别记为O1，O2,Oku又设每次执行一次这些元运算的时间分别为t1,.tku对于算法A，设统计用到元运算Oi的次数为ei ei=ei(N,I)因此本讲稿第二十五页，共二十九页1.4算法复杂性分析最坏情况下的时间复杂性：最好情况下的时间复杂性：

18、平均情况下的时间复杂性：其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入；是中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。本讲稿第二十六页，共二十九页渐进表达渐进表达n对于一个输入为对于一个输入为n n的问题，现给出两个算法的问题，现给出两个算法A A和和B.B.n算法算法A A运行运行100n100n步，算法步，算法B B运行运行nlognnlogn步。步。n哪个算法好？哪个算法好？就算都是多项式，也需表现差异就算都是多项式，也需表现差异n若算法若算法A A运行运行n n2 2+100n+100n步，算法步

19、，算法B B运行运行2n2n2 2步。步。n哪个算法好？哪个算法好？n很多时候我们认为很多时候我们认为n n和和n n2 2之间的差异是较大的，而之间的差异是较大的，而n n和和5n5n之间的之间的差异是微小的甚至可以忽悠不计的，怎样表达这种差异？差异是微小的甚至可以忽悠不计的，怎样表达这种差异？n用渐进表达式可以解决这个问题。用渐进表达式可以解决这个问题。本讲稿第二十七页，共二十九页渐进分析复杂性渐近性态：当N单调增加趋于 时，T（N）也单调增加趋于 如果存在 当N-时有那么称 是T（N）的渐近性态直观上 是T（N）中略去低阶项所留下的主项本讲稿第二十八页，共二十九页算法复杂性分析复杂性渐近性态：比如：T（N）可取的一个答案是进一步考虑到分析算法复杂性的目的在于比较求解同一问题的两个不同进一步考虑到分析算法复杂性的目的在于比较求解同一问题的两个不同算法的效率算法的效率 如果两个算法的渐近复杂性的如果两个算法的渐近复杂性的阶阶不相同时，只需要确定各自的不相同时，只需要确定各自的阶阶就可就可以判断哪个算法的效率高！以判断哪个算法的效率高！本讲稿第二十九页，共二十九页