课程概况
算法设计与分析是计算机专业的核心课程。学习该课程对学习其他专业课奠定了扎实的基础，也对培养计算思维和求解问题的能力起到重要作用。面对各个应用领域的大量实际问题，最重要的是分析问题的性质并选择正确的求解思路，即找到一个好的算法。特别是在当今复杂、海量信息的大数据处理中，一个好的算法往往起到决定性的作用。
本课程注重针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。课程主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程”算法设计与分析（高级）”中加以介绍。
课程的内容分成两大部分：算法的基础知识和通用算法设计技术与分析方法。
算法基础知识部分主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。
通用算法设计技术与分析方法部分主要介绍分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术。重点介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。
课程大纲
01
第一周 基础知识（1）
算法的基本概念及伪码描述，函数的渐近的界。
课时
1.1 本周教学内容简介
1.2 算法设计的两个例子
1.3 问题的计算复杂度：排序问题
1.4 货郎问题与计算复杂性
1.5 算法及其时间复杂度
1.6 算法的伪码表示
1.7 函数的渐近的界
1.8 有关函数渐近的界的定理
1.9 几类重要函数
02
第二周 基础知识（2）
序列求和方法，递推方程求解。
课时
2.1 本周教学内容简介
2.2 序列求和的方法
2.3 递推方程与算法分析
2.4 迭代法求解递推方程
2.5 差消法化简递推方程
2.6 递归树
2.7 主定理及其证明
2.8 主定理的应用
03
第三周 分治策略（1）
课时
3.1 本周教学内容简介
3.2 分治策略的设计思想
3.3 分治策略的一般描述和分析方法
3.4 芯片测试
3.5 快速排序
3.6 幂乘算法及应用
3.7 改进分治算法的途径1：减少子问题数
3.8 改进分治算法的途径2：增加预处理
04
第四周 分治策略（2）
课时
4.1 本周内容简介
4.2 选最大与最小
4.3 选第二大
4.4 一般选择问题的算法设计
4.5.选择问题的算法分析
4.6 卷积及应用
4.7 卷积计算
4.8 快速傅立叶变换FFT算法
4.9 平面点集的凸包
05
第五周 动态规划（1）
课时
5.1 本周教学内容简介
5.2 动态规划算法的例子
5.3 动态规划算法设计
5.4 动态规划算法的递归实现
5.5 动态规划算法的迭代实现
5.6 投资问题
5.7 背包问题
5.8 最长公共子序列
06
第六周 动态规划（2）
课时
6.1 本周教学内容简介
6.2 图像压缩
6.3 最大子段和
6.4 最优二叉检索树的概念
6.5 最优二叉检索树的算法
6.6 RNA二级结构预测
6.7 序列比对
07
第七周 贪心法（1）
课时
7.1 本周教学内容简介
7.2 贪心法的例子
7.3 贪心法的正确性证明
7.4 最优装载问题
7.5 最小延迟调度
7.6 得不到最优解的处理方法
08
第八周 贪心法（2）
课时
8.1 本周教学内容简介
8.2 最优前缀码及哈夫曼算法
8.3 哈夫曼算法的正确性证明
8.4 最小生成树
8.5 Prim算法
8.6 Kruskal算法
8.7 单源最短路径问题及算法
8.8 Dijkstra算法的证明
09
第九周 回溯与分支限界（1）
课时
9.1 本周教学内容简介
9.2 几个回溯算法的例子
9.3 回溯算法的设计思想和适用条件
9.4 回溯算法实现及实例
9.5 图的着色
9.6 搜索树结点数的估计
10
第十周 回溯与分支限界（2）
课时
10.1 本周教学内容简介
10.2 分支限界
10.3 最大团问题
10.4 货郎问题
10.5 圆排列问题
10.6 连续邮资问题
10.7 课程总结
预备知识
程序设计基础、数据结构与算法、高等数学、高等代数
参考资料
《算法设计与分析（第2版）》 屈婉玲、刘田、张立昂、王捍贫编著 清华大学出版社
