教学大纲

第一章：引论 （2学时）

1 本章教学内容：(1) 算法课程的开始目的和必要性（1学时），(2) 算法和程序的差别（1学时）。
2 本章教学要求：通过本章课程的学习，要求学生理解本课程的学习内容及其意义，了解研究生阶段算法分析与设计课程的重要性，理解算法和程序的差别，理解判断问题和优化问题这两类计算问题的差别。

3 本章教学重点：无。

4 本章教学难点：无。

第二章：算法分析与设计基础 （8学时）

1 本章教学内容：(1) 渐进表达（2学时），(2) 贪心算法（4学时），(2) 分而治之算法（4学时），动态规划算法（4学时）。

2 本章教学要求：通过本章课程的学习，要求学生理解指数增长的规模；掌握算法分析的数学基础，熟悉渐近表示法，掌握渐近符号O、W、Q的定义，要求能判断一个较复杂的函数属于哪个渐近增长阶。熟悉算法设计的三大技巧：贪心算法、分而治之，动态规划。会用贪心算法解工作安排问题（Interval scheduling），并能证明其正确性；理解动态规划算法的思想，对动态规划类型的问题能建立起基本的递归关系式并能用从底至上的方法来求解，在求解过程中知道如何建立数据储存的表格。必须掌握的问题包括：背包问题和带权重的工作安排问题（Weighted interval scheduling）等；理解背包问题动态规划算法的运行时间是伪多项式时间。
3 本章教学重点：（1）贪心算法的策略和贪心算法的技巧，（2）分而治之算法的性质，（3) 动态规划方法，（4）判断一个函数的渐进增长阶。

4 本章教学难点：（1）三种算法技巧的差别，（2）动态规划方法，（3）背包问题的动态规划算法及其时间和空间复杂度分析。

第三章：网络流算法 （4学时）

1 本章教学内容：(1) 最大流和最小割的关系（2学时），(2) 最大流算法（2学时）。

2 本章教学要求：通过本章课程的学习，要求学生了解并掌握网络最大流问题和最小割问题及其算法，要求给出一个有向图和无向图能求出两点间的最大流或者最小割。了解网络流的扩展问题——多对点的网络流问题。

3 本章教学重点：（1）最大流和最小割的对偶理论，（2）最大流算法

4 本章教学难点：（1）最大流算法运行时间分析以及改进。

第四章：NP完备性理论 （10学时）

1 本章教学内容：(1) 规约的定义及性质（2学时），(2) P，NP，NPC，NP难等基本概念（2学时），（3）三种不同类型的规约：简单等价、子问题到一般问题、利用小技巧（4学时）。

2 本章教学要求：通过本章课程的学习，要求学生了解并掌握NP 完备性理论及其实际意义。熟悉多项式规约。掌握证明一个问题NP完全性的基本方法和思路，熟悉最小点覆盖、最大独立集等问题的NP完备性证明。

3 本章教学重点：（1）规约的定义和性质，（2）NP、NPC等基本概念，（3）证明一个问题是NPC的方法和步骤。

4 本章教学难点：（1）证明各种具体问题的NP难性。

第五章：近似算法 （6学时）

1 本章教学内容：(1) 近似算法的性质（2学时），(2) 工作调度问题的近似算法（2学时），（3）点覆盖问题的近似算法（2学时），圆盘覆盖等其它问题的近似算法（2学时）。

2 本章教学要求：通过本章课程的学习，要求学生了解近似算法的理念和设计思想，掌握基本的近似算法设计技巧和分析方法。

3 本章教学重点：（1）近似算法的性质，（2）近似算法设计思路，（3）工作调度问题的近似率的证明。

4 本章教学难点：（1）圆盘覆盖等问题的近似率的证明。

第六章：进阶问题及其他 （10学时）