算法复习大纲.ppt

算法分析与设计复习大纲 复习大纲 引论 1.理解算法和程序的差别； 2.理解判断问题和优化问题这两类计算问题。 复习大纲 算法分析与设计基础 1.理解指数增长的规模； 2.掌握渐近符号O、?、?的含义，能判断一个函数属于哪个渐近增长阶； 典型例题：作业1的第一题 复习大纲 算法分析与设计基础 3.理解贪心算法，会用贪心算法解工作安排问题（Interval scheduling）；能证明贪心算法的正确性； 4.理解分治算法的思想；典型例题：作业1的第三题；掌握Master method（主方法）来求解递归关系式； 5.理解动态规划算法的思想，对动态规划类型的问题能建立起基本的递归关系式并能用从底至上的方法来求解，在求解过程中知道如何建立数据储存的表格。经典问题包括：背包问题和带权重的工作安排问题等。理解背包问题动态规划算法的运行时间是伪多项式时间。 复习大纲 网络流 1. 了解并掌握网络最大流问题和最小割问题及其算法，给出一个图能求出其对应的最大流或者最小割。 解题说明：要体现增广链添加的过程。 复习大纲 NP 完备性理论 1.理解什么是多项式归约 （polynomial-time reduction） 2.知道怎样从一个问题多项式归约到另一个问题，需要熟悉的归约包括：从点覆盖问题到独立集问题，从3-SAT问题到独立集问题等基本归约。 3. 要求掌握同一个问题的最优化问题如何多项时间归约到该问题的判断问题（自身归约）；典型考题：作业2第三题 4.熟悉NP和NPC的概念； 5.记住证明一个问题属于NPC的基本步骤 复习大纲 近似算法 理解什么是近似算法； 熟悉load balancing问题的近似算法； 理解点覆盖问题的定价算法（Pricing method），证明该方法能得到一个2倍近似解； 理解点覆盖问题的整数规划模型如何建立的，理解松弛求解方法； 要求会对一个图问题建立整数规划模型（以点覆盖问题为例） 复习大纲 并行算法 理解各种并行架构，特别是 CREW和EREW两种模型的差别； 要求会在CREW、EREW等模型上设计简单算法并分析复杂度（时间、工作、空间） 考试信息 时间：目前定在5月29号上课时间（最后通知为准） 考试时长：2小时 题目语言：中文（个别名词有对照英文） 考试类型：考查需要参加考试 题目：有部分选做题（两个题目选一个做即可）；肖老师班学生尽量选做A题；如果A、B两题都做了，老师可以随机选择其中一题来判成绩 对成绩的预期：90分以上的5%左右（9人以内）平均分78-72 预计题目类型 判断题 （10个左右，20分左右） 简单计算题 （10分左右） 10个左右大题，其中渐进表达式 1题贪心算法 1-2题分而治之算法 1-2题动态规划算法1-2题最大流最小割1题归约与复杂度（NP相关）的证明题2-3题近似算法1-2题并行算法1-2题其它算法设计题1题 答题中的几大注意事项 1. 要求要写明计算过程的题目，不要只写答案。尽量多写一些中间过程，这些步骤会算分的。 2. 简单计算题没特殊说明，可以只写结果，不写计算过程 答题中的几大注意事项 要求写算法的题目，不要写一个程序。很多同学写一些看不懂的程序在试卷上想蒙混过关，当然也有一些同学花了一些时间认真写了一个Java或C的可能正确的程序。但是这些都很可能只能给零分。程序是给计算机读的，不是给人读的。要求写的算法尽量用简明易懂的语言表达清晰，从文字的角度来体现中心思想。有些算法的回答可能很简单几句话就可以得满分，但是写程序的都不能给分。比如说如下这种形式的回答就很好：用贪心算法，算法步骤如下，每一次在图中贪心选择度数最大的点放到解集中。 答题中的几大注意事项 证明题要注意逻辑和推导过程，多看看ppt中给出的一些算法证明过程（特别是重点中提到的那些问题）。特别注意对贪心算法的证明：先假设贪心算法得到的解不是最优解，假设S1是贪心算法得到的解，而S2是所有最优解中和S1具有最多相同元素的解，然后比较S1和S2，观察S1和S2中第一个（最前面一个）不一样的元素，然后在贪心解S2中将不一样的元素换成S1中的那个元素得到另一个最优解S3，这样S3和S1比S2和S1有更多相同元素，和假设S2是与S1有最多相同元素的最优解矛盾，这样来推导S1是最优解。NP难类型问题的证明：先选好一个已知NP难的问题，然后将已知NP难问题多项式归约到要证明的问题上。先给出这个归约，然后再证明这个归约的正确性。