算法分析与设计.ppt

IntroductiontoAlgorithms WhatDoYouWant agoodscoretobemoreintelligentthebeautyofmaththewaytoresearchIfyoulistentomecarefullyfromnowandfinisheveryhomework 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答疑地点 XX305 Gradingpolicy 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型骨牌不得重叠覆盖 Lon