算法分析与设计

IntroductiontoAlgorithmsWhatDoYouWant?agoodscoretobemoreintelligentthebeautyofmaththewaytoresearchIfyoulistentomecarefullyfromnowandfinisheveryhomework,Ipromisethatyouwillgetallofthem.Lecture1本课程的教学目的及要求(1/2)分析算法的渐进效率；掌握最坏，平均及最好情况下复杂性的分析；叙述分治法的模式和解释当什么情况算法设计会需要它，练习使用此模式的算法，实现并推导出分治法的递归描述；叙述动态规划的模式和解释当什么情况算法设计会需要它，练习使用此模式的算，实现并分析动态规划算法。叙述贪心算法的模式和解释当什么情况算法设计会需要它，练习使用此模式的算法，实现并分析贪心算法；解释各主要的排序算法，练习这些算法的分析及它们所包含的设计策略，实现将排序作为子程序的算法，推算比较排序法执行时间的下限，和解释怎样可以克服这些界限；实现图论算法和使用图论计算为关键的算法，分析它们，以及如何使用图来模拟工程问题；本课程的教学目的及要求(2/2)教材内容：第一部分（PartI）基础（Foundations）第一章计算中算法的角色（TheRoleofAlgorithmsinComputing）第二章开始（GettingStarted）第三章函数的增长率（GrowthofFunctions）第四章递归（Recurrences）第五章概率分析与随机化算法（ProbabilisticAnalysisandRandomizedAlgorithms）第二部分（PartII）排序与顺序统计（SortingandOrderStatistics）第六章堆排序（Heapsort）第七章快速排序（Quicksort）第八章线性时间中的排序（SortinginLinearTime）第九章中值与顺序统计（MediansandOrderStatistics）第三部分（PartIII）数据结构（DataStructures）第十章基本的数据结构（ElementaryDataStructures）第十一章散列表（HashTables）第十二章二叉查找树（BinarySearchTrees）第十三章红-黑树（Red-BlackTrees）第十四章扩充的数据结构（AugmentingDataStructures）第四部分（PartIV）高级的设计与分析技术（AdvancedDesignandAnalysisTechniques）第十五章动态规划（DynamicProgramming）第十六章贪婪算法（GreedyAlgorithms）第十七章分摊分析（AmortizedAnalysis）第五部分（PartV）高级的数据结构（AdvancedDataStructures）第十八章B-树（B-Trees）第十九章二项式堆（BinomialHeaps）第二十章斐波纳契堆（FibonacciHeaps）第二十一章不相交集的数据结构（DataStructuresforDisjointSets）第六部分（PartVI）图算法（GraphAlgorithms）第二十二章基本的图算法（ElementaryGraphAlgorithms）第二十三章最小生成树（MinimumSpanningTrees）第二十四章单源最短路径（Single-SourceShortestPaths）第二十五章全对的最短路径（All-PairsShortestPaths）第二十六章最大流（MaximumFlow）第七部分（PartVII）精选的主题（SelectedTopics）第二十七章排序网络（SortingNetworks）本课程的难点和学习方法•双语学习•较多的数学知识和推倒(第一部分)•预习-上课认真听讲-复习（重点词汇）•预备的数学知识(p51-57)•本次课和下节课所讲重点内容在教材上划出。教材IntroductiontoAlgorithms(SecondEdition)，（美）ThomasH.CormenCharlesE.LeisersonRonaldL.RivestCliffordStein，高等教育出版社参考教材1、算法设计与分析王晓东清华大学出版社2、算法分析与设计（美）MichaelT.GoodrichRobertoTamassia著人民邮电出版社3、算法设计技巧与分析（沙特）M.H.Alsuwaiyel著电子工业出版社4、算法设计与分析郑宗汉清华大学出版社5、算法导论，ThomasH.CormenCharlesE.LeisersonRonaldL.RivestCliffordStein著，潘金贵等译，机械工业出版社教辅用书在学期中将会指定多次作业。要求同学上交并给出成绩，作为部分期末成绩。作业的目的是让同学有练习掌握课堂内容的机会。因此，鼓励同学们合作解题。虽然鼓励合作解答题目，但是，要求独立写下答案，并要求在习题上写下合作者们的名字。如果没有跟任何人合作，应该写下“合作者：无”。如果答案是由研究而来(例如：互联网)，注明你的资料来源，但依你自己的方法写下答案。作业要求在学期中将会有大约4次的讨论课，共四组(大约20个人为1个小组)，15分钟问题的描述和讲解。题目可以自己拟定，也可以由教师指定。目的是让同学们及时复习，培养团队合作以及主动学习精神，记入平时成绩。课前讨论当被指定“用一个算法”来解决某个问题。应该提供以下部分：1.算法的描述：伪代码(pseudocode)。2.最少以一个工作例子或图表来更明确的显示你的算法是怎样工作的。3.算法正确性的一个证明（或表示）（*）。4.算法执行时间的分析。作业以及实验报告中算法描述要求相关事项教学方式：理论(48学时)，实践(16学时)最终的评分会基于作业、平时表现、实验报告和期末考先修课程：《离散数学》《数据结构》《数值分析》《C语言程序设计》作业：每个部分交一次答疑时间：周四下午2：30答疑地点：XX305Gradingpolicy:Homework:8%ExperimentRunResults:8%ExperimentPaper:8%Arrival:6%FinalExam:70%古城哥尼斯堡，景致迷人，碧波荡漾的普瑞格尔河横贯其境。普瑞格尔河的两岸及河中的两个美丽的小岛，由七座桥连接组成了这座秀色怡人的城市（如图）。市民们喜欢四处散步，于是便产生这样的问题：是否可以设计一种方案，使得人们从自己家里出发，经过每座桥恰好一次，最后回到家里。这便是著名的“哥尼斯堡七桥问题”。热衷于这个有趣的问题的人们试图解决它，但一段时间内竟然没有人能给出答案。后来，问题传到了著名数学家欧拉那里，居然也激起了他的兴趣。他从人们寻求路线屡遭失败的教训中敏锐地领悟到，也许这样的方案根本就不存在。欧拉经过悉心的研究，1736年，年方29岁的欧拉终于解决了这个问题，并向圣彼得堡科学院递交了一份题为《哥尼斯堡的七座桥》的论文。论文不仅仅是解决了这一难题，而且引发了一门新的数学分支——图论的诞生。你能解决以下问题吗？七桥问题18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。Euler定理Königsberg桥对应的图定义（欧拉图）通过无向连通图G的每条边一次且仅有一次的回路称为欧拉回路。具有欧拉回路的图为欧拉图。定义包含多重图在内，即欧拉回路中允许顶点重复出现。欧拉图▪定理G是无向连通图，则G是欧拉图G中所有顶点度数都是偶数。定义如果无向连通图G的每条边一次且仅一次的通路称为图G的欧拉通路。定理具有一条连接顶点vi和vJ的欧拉通路的充分条件是vi和vJ是G中仅有的具有奇数度的顶点。货郎担问题一个货郎要去若干城镇卖货，然后回到出发地，给定各城镇之间所需的旅行时间后，应怎样计划他的路线，使他能去每个城镇恰好一次而且总时间最短？实质：无向加权图，寻找最短的Ｈ回路的问题。货郎担问题用图论的术语说，就是在一个赋权完全图中，找出一个具有最小权的Hamilton圈（包含图G的每个顶点的圈)。这个问题目前还没有有效的算法。30！=265,252,859,812,191,058,636308,480,000,000有兴趣的同学编程序实现，看你能解决多大规模的问题。哈密顿图一.１８５９年发明的一种游戏。在一个实心的正十二面体，20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。定义通过图G的每个顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图。哈密顿通路是通过图G的每个顶点一次且仅一次的通路。注：（1）欧拉道路未必是哈密顿道路，因为欧拉道路可以经过同一顶点多次。哈密顿道路未必是欧拉道路，因为哈密顿道路不一定要经过Ｅ中所有的边。（2）基本道路必然是简单道路。哈密顿图四色问题著名的世界难题“四色猜想”：一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。四色问题1852年，刚从伦敦大学毕业的FrancisGuthrie提出了四色猜想。1878年著名的英国数学家Cayley向数学界征求解答。此后数学家Heawood花费了毕生的精力致力于四色研究，于1890年证明了五色定理（每个平面图都是5顶点可着色的）。直到1976年6月，美国数学家K.Appel与W.Haken，在3台不同的电子计算机上，用了1200小时，才终于完成了“四色猜想”的证明，从而使四色猜想成为了四色定理。棋盘覆盖在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。LongestCommonSubsequence(LCS)Application:comparisonoftwoDNAstringsEx:X={ABCBDAB},Y={BDCABA}LongestCommonSubsequence:X=ABCBDABY=BDCABABruteforcealgorithmwouldcompareeachsubsequenceofXwiththesymbolsinYFractionalknapsackproblem?