2022年算法分析与设计复习大纲

DONG Qiang 2022.10.27

第1章 引论

1.理解什么是算法，算法的特征，算法和程序的差别；

2.理解什么是判断问题、搜索问题和优化问题。

第2章 算法分析与设计基础

1.理解指数增长的恐怖；
理解算法分析里为什么常数倍的差别可以被忽略；

2.掌握渐近符号O、Ω、Θ的含义，能判断一个函数属于哪个渐近增长阶；

3.能对给定函数按照渐进增长率进行排序，典型考题：作业1中的第2题；

4.理解贪心算法的思想；
能判断一个算法是否贪心算法；
掌握工作安排Interval scheduling问题的贪心算法及其正确性证明；

5.理解分治算法的思想；
掌握Counting inversions问题的分治算法；
能用Master Theorem求解递归关系式，典型考题：作业1的第1题；

6.理解动态规划算法的思想；
对相应问题能建立基本的递归关系式并用从底至上的方法来求解，在求解过程中知道如何建立数据储存的表格。
重点掌握的问题：带权重的活动安排问题、0-1背包问题、最长公共子序列问题、矩阵连乘的最优计算次序问题，典型考题：作业1中第3题。

7.理解0-1背包问题的动态规划算法不是多项式时间算法。

第3章 网络流

1.理解最大流、任意流、最小割、任意割之间的关系；

2.掌握网络最大流问题和最小割问题及其求解算法，给出一个网络能求出它的最大流或者最小割，典型考题：作业1的第4题（解题过程要列出各条增广路径）。

第4章 NP完备性理论

1.理解什么是多项式归约polynomial-time reduction；

2.从一个问题A多项式归约到另一个问题B时，掌握针对问题A的任意实例构造问题B的实例的方法，重点掌握的归约包括：

• Vertex-Cover 顶点覆盖 ≡p lndependent Set 独立集
• Vertex-Cover 顶点覆盖 ≤p Set-Cover 集合覆盖
• Vertex-Cover 顶点覆盖 ≤p Dominating-Set 支配集
• 3-SAT 三元可满足性 ≤p Independent Set 独立集
• Ham-Cycle 哈密顿回路 ≤p TSP 旅行商
• Ham-Cycle 哈密顿回路 ≤p Longest-Path 最长路径
• 3-Color 三着色 ≤p k-Color k着色 (k > 3)
• Subset-Sum 子集和 ≤p Knapsack 背包
• Subset-Sum 子集和 ≤p Partition 划分
• Partition 划分 ≤p k-Load-Balance k负载均衡

3.要求掌握同一个问题的最优化问题如何多项时间归约到该问题的判断问题（自身归约），例如：

• Vertex-Cover 顶点覆盖问题
• Hamilton Cycle 哈密顿回路问题
• 3-Color 三着色问题

典型考题：作业2中的第2题

4.掌握如果P≠NP ，P、NP和NPC三个集合之间的关系， 以及NP问题定义的非对称性；

5.记住证明一个问题属于NPC的基本步骤；

6.能证明给定的问题是NP完全问题，典型考题：作业2中的第3题。

第5章 近似算法

1.理解为什么会有近似算法，什么是近似算法，如何评价近似算法的优劣

2.掌握负载均衡问题的近似算法及其近似比证明；

3.掌握带权重的顶点覆盖问题的定价算法（Pricing method），证明该方法能得到一个2倍近似解；

4.理解带权重的顶点覆盖问题的整数规划模型如何建立的，理解松弛求解方法；

5.能够对一个图问题建立整数规划模型（例如：带权重的顶点覆盖问题，广义负载均衡问题）；

6.理解求解0-1背包问题的基于取整法的近似算法；

7.能够设计简单的近似算法，并证明该算法是几倍近似算法，典型考题：第5章课件P41练习题。

考试信息

时间：2022-12-14 19:00-21:00

考试时长：2小时

试卷语言：中文

考试类型：闭卷考试（考查也需要参加考试）

如果有二选一的选做题，选我们讲过的一个即可，做另一个不算分

对成绩的预期：90+分的5%左右，平均分72-78

预计题目类型

判断题 （10个左右，20分左右）

简单计算题 （20-30分左右）

求解渐进表达式1题

贪心算法 1题

分治算法/递归式求解1题

动态规划算法1题

最大流最小割1题

归约与复杂度（NPC相关）的证明题2-3题

近似算法1题

答题中的几大注意事项

1.要求要写明计算过程的题目，不要只写答案。尽量多写一些中间过程，这些步骤会算分的。

2.简单计算题没特殊说明，可以只写结果，不写计算过程。

3.要求写算法的题目，不要写一个程序。

很多同学写一些看不懂的程序在试卷上想蒙混过关，当然也有一些同学花了一些时间认真写了一个Java或C的可能正确的程序。但是这些都很可能只能给零分。程序是给计算机读的，不是给人读的。要求写的算法尽量用简明易懂的语言表达清晰，从文字的角度来体现中心思想。有些算法的回答可能很简单几句话就可以得满分，但是写程序的都不能给分。

比如说如下这种形式的回答就很好：用贪心算法求最小顶点覆盖的近似解，算法步骤如下：每一次在当前的图中贪心选择度数最大的点放到解集中，并从图中删除该顶点，直到图中不存在边为止。

4.证明题要注意逻辑和推导过程，多看看ppt中给出的一些算法证明过程。——参考Interval scheduling问题的贪心算法及其正确性证明；

特别注意对贪心算法的证明：先假设贪心算法得到的解不是最优解，假设S1是贪心算法得到的解，而S2是所有最优解中和S1具有最多相同元素的解，然后比较S1和S2，观察S1和S2中第一个（最前面一个）不一样的元素，然后在解S2中将不一样的元素换成S1中的那个元素得到另一个最优解S3，这样S3和S1比S2和S1有更多相同元素，和假设S2是与S1有最多相同元素的最优解矛盾，这样来推导S1是最优解。

5.NP完全问题的证明：先选好一个已知NP完全的问题A，然后将问题A多项式归约到要证明的目标问题B上。先给出这个归约中问题A的实例到问题B的实例的构造方法，然后再证明这个归约的正确性。

附

例题：用贪心算法求最小顶点覆盖的近似解：每一次在当前的图中贪心选择度数最大的点放到解集中，并从图中删除与该顶点相关联的所有边，直到图中不存在边为止。举例说明该算法不是2倍近似算法。

反例：