算法设计基础概要课件.ppt

算法设计基础,上海交通大学计算机系,时间 地点 助教,周二3、4，E404周四1、2，E312（双周）主讲：黄林鹏（)助教：王慧芳,算法引论一种创造性方法美 UDI MANBER著HLP Leo LSB 等译电子工业出版社 2005,教材,作者简介,本书作者乌迪-曼博（Udi Manber）博士是美国著名的计算机科学家，公认的国际算法大师，在线信息搜索引擎的先驱。乌迪-曼博曾是美国亚利桑那大学计算机系的教授，后离开学校在雅虎担任执行官，目前是亚马逊()的副总裁和首席算法师（CAO），也是亚马逊旗下搜索网站A的首席执行官，他提出的UDI测试已成为衡量搜索引擎质量的评估标准。,教材简介,本书强调算法设计的创造性方面，讲授算法设计背后的创造性思想，通过算法开发步骤来描述算法设计过程。本书创造性地将算法设计过程和定理归纳证明过程进行类比，揭示了算法设计的基本思想和本质。本书旨在提高读者的问题求解能力和理解算法设计的过程和思想。,内容包括,经典算法、流行算法算法设计的已知技巧以及这些技巧的综合应用并行算法设计大多数算法的伪代码表示500多个习题，其中四分之一给出了答案提示,目录,引言数学归纳法算法分析数据结构基于归纳的算法设计序列和集合的算法图算法集合算法,代数和数值算法 归约 NP完全问题 并行算法,动机,对一些学生来说,不仅要他们亲自动手解决一些简单问题有困难，而且让他们理解给定问题的解决方案也有困难。事物的两个方面，创造和解释，是相关的，不是分离的。为了完全了解一个问题，考察最后的答案是不够的，我们必须了解问题的求解过程。,创造过程vs最终产品,本书强调了算法设计的创造性方面，其主要目的是要告诉读者如何去设计一个新的算法。本书描述算法的顺序不是“问题X、算法A、算法A、程序P、程序 P”等，而是如（但并不总是）“问题X、直接明了的问题求解算法、缺点、改进这些缺点的困难、（可能包含一些错误的）一个好的算法、进一步的改进、分析、和其他方法和算法的关系”等。本书的目标不是给出一个容易转换为程序代码的算法，而是希望让读者理解算法的原理。,老兵新传,本书在算法设计过程中使用的是一种“老兵新传”式的方法学。该方法学除了涵盖许多已知的算法设计技术外，还是一个优雅的、能深入解释算法设计直觉的框架。,快餐 vs 品味,考虑下面类比。你来到一个陌生的城市，租了一辆轿车，现在想知道旅馆的方向。这时如果人家在喋喋不休地告诉你城市的历史、布局和交通状况，你肯定会觉得非常厌烦。你所需要的其实是诸如“向前开、过两个街区、右转、再直着向前开3英里”这样的信息。然而，如果你计划在这个城市里生活较长的一段时间，那么你的看法就会有所变化。你可能会希望在另一个方向上行驶一段时间（假定能找到一个人告诉你方向），慢慢你将对城市有更多的了解。,操练vs创造,大部分章节后面的练习可分为两类：操练性的练习和创造性的习题。 操练性练习的目的在于检查读者对于书中特定例子和算法的理解，创造性习题的目的在于检查读者应用相应章节所介绍的特定算法和技术于新问题求解的能力。,第1章到第4章内容是介绍性的,第2章涉及数学归纳法第3章涉及算法分析，描述了算法分析的过程，给出了对本书所讨论的算法进行简单分析所需要的工具第4章介绍数据结构，那些对数据结构熟悉且具备一定数学基础的同学可以直接跳到第5章。第5章提出了与归纳证明进行类比的算法设计思想，给出一些简单例子，并描述了算法设计过程。,4个领域的算法,本书第6章到第9章分别给出了下面4个领域的算法：序列和集合的算法（如排序、序列比较、匹配等），几何算法(如凸包和交集问题等)、数值和代数算法（如矩阵乘法、快速傅立叶变换等）。,NP完全问题,第10章涉及归约或约简。尽管归约的例子也出现在本书前面的章节之中，但该主题不但独特而且重要，因此有必要作为一章的主题。第10章的内容也是第11章的序幕，后者涉及NP完全问题。复杂性理论已经成为算法的基本组成成分，任何算法设计者都应该了解NP完全问题和证明相关性质的技术。第12章介绍并行算法，本章包含了不同并行计算模型上的几个有意义的算法,高级算法课程的基础,本书内容可能不能在一个学期之内讲授完毕，因此对于教师来说就有许多不同的选择。开设的第一门算法课程可在某种深度涉及第3、5、6、8章的部分内容，这些章节的高级部分加上第9、10、11和12章的内容是可选的，它们可作为高级算法课程的基础。,第1章 引论,算法是“求解数学问题（如寻找最大公约数）的一个过程，该过程步骤有限，通常还涉及重复的操作；广义地说，算法是按部就班解决一个问题或完成某个目标的过程。,算法设计,算法设计是一个古老的研究领域。自古以来，人们总是对发现更好的目标求解方法充满兴趣，不管是取火、建设金字塔还是对邮件进行排序。计算机算法的研究当然是一个新的领域。一些计算机算法采用的方法早在计算机发明之前就存在了，但大多数计算机算法的设计需要新的方法和技术。,潜在的回报,在日常生活中，我们超市采购回家，打开杂贷袋放置食品的过程就可能不是最有效的，有效的过程应该考虑杂贷袋中的食品以及厨柜的结构，但很少会有人去想这事，更不会有人会为它去专门设计算法。反之，进行大规模商业包装和拆装就必须有一个好的方法。另一个例子是修剪草坪，可以考虑如何使来回次数最少、修剪时间最短，或到垃圾堆放处的往返距离最短。除非你非常讨厌修剪草坪，否则你不会花一个小时的时间来思考如何使修剪时间缩短几分钟这样的问题。但另一方面，计算机可以处理非常复杂的任务，而且同一任务往往必须执行多次，因此值得花费时间来设计有效的方法，就算最终得到的方法更加复杂或难以理解也无妨，因为潜在的回报是巨大的。,学习算法这个学科的动力,对与直觉相悖的大型问题求解算法的需要以及了解这些算法的复杂度是学习算法这个学科的动力所在。首先，必须认识到直观的方法并不总是最好的，寻找更好的方法有时非常重要，为此，程序员必须学习新的方法和技术。然而，就如要成为一个好棋手仅仅靠记住许多棋局是不够的一样，就算你学习了大量的算法也不足以应付各种情况，因此我们必须了解算法背后的原理，必须知道如何应用它们，当然更重要的是，何时应用它们。,建筑设计vs算法设计,算法的设计和实现类似于房屋的设计和建筑。我们先从最基本的概念出发考虑房子的修建。设计师的工作是给出满足要求的规划；工程师的工作是确认规划是正确且可行的（以保证房子不会在短时间内倒塌）；建设工人的工作是按照规划建筑房子。当然，在所有阶段，都要考虑造价并进行分析。每个阶段的工作是不同的，但它们又有所联系甚至交织在一起。算法的设计也是如此，先考虑基本的思想和方法，然后作出规划。我们必须证明规划是可行的并且代价是可接受的。最后的工作是在具体的计算机上实现。简单地说，可将过程分为4步：设计、正确性证明、分析和实现。再次，每步都不同但又相关，每步都不能不顾及其他而在真空中完成。,基于数学归纳法的方法学,数学归纳法原理的主要思想是命题无需从什么都没有开始证明，命题的证明可以通过先证明对于一个小的基本实例集命题是正确的，然后由“若对于相对较小的实例命题成立可以导出较大的实例命题成立”的方式证明对所有实例来说命题都是成立的。 将该原理转化为算法设计则提示了一种侧重于如何将简单问题的解扩充为较大问题的解的方法。 给定一个问题，如果我们能说明如何应用类似问题（但参数较小）的解决方法进行问题求解，任务就完成了。因此它的基本思想是如何扩充一个解决方案而不是从零开始进行构造。,算法描述记法,除了通过对算法开发的创造过程进行描述外，本书也包括了许多算法的伪代码。包含程序代码的目的是加强算法的形象描述。我们未对程序进行太多的优化，也不推荐直接使用它们。在许多情况下，我们有意不包括程序的优化版本，因为这可能会引入额外的复杂性，使读者的注意力离开算法的主要思想。我们有时也不详细解释如何将算法思想转换为程序，这种转换有时是显然的有时却不是。本书的侧重点，正如我们前面所提到的，在于算法设计的原理。,习题 1,考虑下面一些数组成的表。你的工作是删去尽可能少的数以使留下来的数以升序排列。例如除了前两个数外删去所有的数就会得到一个升序序列，删去除了第1、3、6、8个数外的其他数也将得到一个升序序列（比前面少删除了一些数）。 9 44 32 12 7 42 34 92 35 37 41 8 20 27 83 64 61 28 39 93 29 17 13 14 55 21 66 72 23 73 99 1 2 88 77 3 65 83 84 62 5 11 74 68 76 78 67 75 69 70 22 71 24 25 26,习题 2,美国总统选举中各州的票数（在一个州中得到大多数选民 选票的候选人获得该州的所有票数）。共有538票。请在数学上确定选举会不会可能以平局结束,