算法设计与分析

通知

教材

屈婉玲等。算法设计与分析（第2版）。清华大学出版社。

Thomas H.Cormen et al. 算法导论（第3版）。机械工业出版社。

Jon Kleinberg and Eva Tardos. Algorithm Design. 清华大学出版社。

王晓东。算法设计与分析（第四版）。清华大学出版社。

推荐慕课

北大公开课 算法设计与分析 屈婉玲教授 [link]

北大公开课 算法设计与分析（高级） 屈婉玲教授 [link]

授课内容

第一章 基础知识 （3周）

1. 课程简介：学习意义、相关教材、OJ平台
2. 调度问题和投资问题
3. 问题计算复杂度的界定、货郎问题、0-1背包问题、NP-Hard问题
4. 算法描述、时间复杂度分析（平均情况、最坏情况）、算法伪代码
5. 函数的渐进的界（会证明）、相关定理
6. 常见函数（对数函数、指数函数、阶乘函数、取整函数）的阶
7. 递推方程的求解（迭代法求解、换元迭代、差消法、递归树、主定理）

第二章 分治策略（2周）

1. 分治算法的设计思想 （二分检索、二分归并排序、Hano塔）
2. 分治算法的一般描述极其分析方法
3. 芯片测试问题、幂乘算法
4. 改进分治算法的途径：减少子问题数（整数位乘问题、矩阵相乘问题）
5. 改进分治算法的途径：增加预处理（平面点对问题）
6. 快速排序
7. 一般选择问题

第三章 动态规划（2周）

1. 动态规划算法的设计思想（最短路径、矩阵链相乘）、最优子结构性质
2. 动态规划算法的实现方法（递归实现、迭代实现）、备忘录
3. 投资问题
4. 最长公共子序列问题
5. 最大字段和问题

第四章 贪心法 （2周）

1. 贪心法的设计思想（活动选择问题）
2. 贪心法的证明方法（按步骤归纳进行证明），涉及问题是活动选择问题
3. 贪心法的证明方法（按按规模归纳进行证明），涉及问题是装载问题
4. 贪心法的证明方法（按交换论证进行证明）， 涉及问题是最小延迟调度问题
5. 得不到最优解的处理，涉及到的问题是找零钱问题
6. 最优前缀码（ 哈夫曼算法）
7. 最小生成树（ Prim算法、 Kruskal算法）
8. 单源最短路径（ Dijkstra算法）

第五章 回溯与分支限界（2周）

1. 回溯算法的设计思想（n皇后放置问题、0-1背包问题、货郎问题）
2. 回溯算法的适用条件（多米诺性质）
3. 回溯算法的实现（递归实现与迭代实现）
4. 图的着色问题
5. 分支限界（代价函数、界）
6. 最大团问题
7. 货郎问题
8. 圆排列问题
9. 连续邮资问题

习题（算法类题目均需给出算法的设计、分析和编程实现）

第一章 基础知识习题练习

第二章 分治策略 （1周） 自己寻找相关题目

第三章 动态规划 （1周） 自己寻找相关题目

第四章 贪心法 （1周） 自己寻找相关题目

第五章 回溯与分支限界（1周）自己寻找相关题目

联系方式

办公室：江苏省南通市啬园路9号南通大学方肇周楼606办公室
邮箱：xchencs at ntu dot edu dot cn