《算法设计与分析》教学大纲
| 课程编号：0908356011 | 课程名称：算法设计与分析 | 学时数：40 | 学分：2 |
| 开课时间： 秋季 | 开课学院：信息与软件工程学院 | 授课对象：硕士/博士 | |
| 先修课程：程序设计基础，数据结构与算法 | |||
一、教学目的
算法分析与设计是计算机科学相关专业一门重要的专业基础课程。本课程是本科算法分析与设计课程的延续，通过对本课程的学习，使学生从理论高度理解算法设计及其复杂度分析的目的和重要意义，掌握算法设计的基本技巧和计算复杂度的相关理论。了解算法研究的前沿，培养学生初步的算法研究能力，以及理论结合实际解决具体问题的能力。
二、教学内容与要求
第一章：绪论 （2学时）
1 本章教学内容：课程简介，算法分析基础。
2 本章教学要求：通过本章课程的学习，要求学生了解本课程的学习内容及其意义，了解研究生阶段算法分析与设计课程的重要性。理解算法的概念，理解什么是程序，程序与算法的区别和内在联系；掌握算法的计算复杂性概念，掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法。
3 本章教学重点：掌握算法的计算复杂性概念，掌握算法渐近复杂性的数学表述。
4 本章教学难点：递归算法的计算复杂度分析方法，主定理。
第二章：递归与分治策略（8学时）
1 本章教学内容：递归与分治策略的算法设计思想，经典算法分析。主要内容包括：
（1）算法范例：二分搜索技术；大整数乘法。（2学时）
（2）算法范例：Strassen矩阵乘法；棋盘覆盖。（2学时）
（3）算法范例：合并排序和快速排序；线性时间选择。（2学时）
（4）算法范例：最接近点对问题；循环赛日程表。（2学时）
2 本章教学要求：理解递归的概念，掌握递归与分治策略的基本要素，学习利用分治的思想简化复杂问题，学会自顶向下分析问题和自底向上求解问题，学会利用分治策略设计有效的递归算法解决问题。通过8个经典应用范例学习递归与分治策略和算法设计与分析方法，通过作业掌握递归和分治策略的算法分析方法和实现技巧。
3 本章教学重点：递归与分治策略的基本思想和在实际工作中的应用。
4 本章教学难点：理解并灵活运用递归与分治策略解决工程问题。
第三章：动态规划算法（8学时）
1 本章教学内容：动态规划算法的算法设计思想，经典算法分析。主要内容包括：
（1）算法范例：矩阵连乘问题；最长公共子序列。（2学时）；
（2）算法范例：最大子段和；凸多边形最优三角剖分。（2学时）；
（3）算法范例：多边形游戏；图像压缩。（2学时）；
（4）算法范例：背包问题；最优二叉搜索树。（2学时）。
2 本章教学要求：理解动态规划算法的概念。掌握动态规划算法的基本要素，即最优子结构性质，和重叠子问题性质。掌握设计动态规划算法的步骤，要求能够找出最优解的性质，并刻划其结构特征；学会递归地定义最优值，并以自底向上的方式计算出最优值；能够根据计算最优值时得到的信息，构造最优解。通过8个经典应用范例学习动态规划算法设计策略，通过作业掌握动态规划算法的算法分析方法和基本设计技巧。
3 本章教学重点：动态规划算法的基本思想和在实际工作中的应用。
4 本章教学难点：理解并灵活运用动态规划算法解决工程问题。
第四章：贪心算法（8学时）
1 本章教学内容：贪心算法的算法设计思想，经典算法分析。主要内容包括：
（1）算法范例：贪心算法的概念和基本要素。（2学时）；
（2）算法范例：活动安排问题；最优装载问题。（2学时）；
（3）算法范例：哈夫曼编码；多机调度问题。（2学时）；
（4）算法范例：最小生成树；单源最短路径。（2学时）。
2 本章教学要求：理解贪心算法的概念，掌握贪心算法的基本要素，即最优子结构性质，和贪心选择性质。理解贪心算法与动态规划算法的差异，理解贪心算法的一般理论，并能够运用贪心算法设计思想解决实际问题。通过8个经典应用范例学习贪心设计策略，通过作业掌握贪心算法的算法分析方法和基本设计技巧。
3 本章教学重点：贪心算法的基本思想和在实际工作中的应用。
4 本章教学难点：理解并灵活运用贪心算法解决工程问题。
第五章：回溯法（8学时）
1 本章教学内容：回溯法的算法设计思想，经典算法分析。主要内容包括：
（1）算法范例：装载问题；批处理作业调度。（2学时）；
（2）算法范例：n皇后问题；0-1背包问题。（2学时）；
（3）算法范例：符号三角形问题；最大团问题。（2学时）；
（4）算法范例：图的m着色问题，旅行售货员问题。（2学时）。
2 本章教学要求：理解回溯法的深度优先搜索策略，掌握用回溯法解题的算法框架，包括：递归回溯、迭代回溯、子集树算法框架、以及排列树算法框架。通过8个经典应用范例学习回溯法的设计策略，通过作业掌握回溯法的算法分析方法和基本设计技巧。
3 本章教学重点：回溯法的基本思想和在实际工作中的应用。
4 本章教学难点：理解并灵活运用深度优先搜索策略解决工程问题。
第六章：分支限界法（6学时）
1 本章教学内容：分支限界法的算法设计思想，经典算法分析。主要内容包括：
（1）算法范例：单源最短路径问题；最大团问题。（2学时）；
（2）算法范例：装载问题；旅行售货员问题。（2学时）；
（3）算法范例：0-1背包问题；批处理作业调度问题。（2学时）。
2 本章教学要求：理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架，包括：队列式(FIFO)分支限界法；以及优先队列式分支限界法。通过6个经典应用范例学习分支限界法的设计策略，通过作业掌握分支限界法的算法分析方法和基本设计技巧。
3 本章教学重点：分支限界法的基本思想和在实际工作中的应用。
4 本章教学难点：理解并灵活运用队列式(FIFO)分支限界法解决工程问题。
三、教学方式
课堂讲解为主，课后作业为辅。
