-
第一章算法与问题
介绍算法的概念与性质、问题的求解过程、问题变换的目的和类型。算法与程序、算法与问题的区别和内在联系。
-
●1.1稳定匹配问题
引入稳定匹配问题，介绍问题的求解过程
-
●1.2Hi!什么是算法？
介绍算法的概念与性质、算法与程序、算法与问题的区别和内在联系。
-
●1.3大学入学申请问题
引入大学入学申请问题，介绍问题变换的目的和类型
-
第二章算法分析
介绍算法的时间和空间复杂度, 算法复杂度分析和比较的方法,常用算法的复杂度分析，以及时空均衡的概念和处理方法。
-
●2.1算法分析
引入时间复杂度和空间复杂度的概念，介绍算法分析的方法和阶段，问题的规模和关键操作。
-
●2.2几个符号
介绍算法渐近复杂性的数学表述和性质，算法的上界、下界、同阶、高阶和低阶的表示。算法的分类和划分标准。
-
●2.3复杂度比较
算法复杂度比较的方法和实例分析。
-
●2.4分析实例
实例分析常用算法的复杂度。
-
●2.5时空均衡
时空均衡的概念和处理方法。
-
第三章枚举算法
介绍蛮力和枚举算法和特点，枚举算法的优化方法，排列和组合的生成方法。
-
●3.1枚举
介绍蛮力与枚举算法和特点，枚举算法的优化方法。
-
●3.2集合与排列
介绍排列和组合的生成方法。
-
第四章贪心算法
介绍贪心算法的基本思想、基本要素和正确性证明方法。贪心算法的常用问题，运用贪心解决实际问题。
-
●4.1背包问题
介绍部分背包问题，引入贪心算法的基本思想和特点。
-
●4.2基本要素
介绍贪心算法的基本要素、处理技巧和证明方法。
-
●4.3区间问题
介绍区间调度、区间划分、区间选点和区间覆盖问题。
-
●4.4MST问题
介绍MST的特性，MST的常用算法和证明方法。
-
●4.5哈夫曼编码
介绍哈夫曼编码、生成算法和应用实例。
-
第五章递推算法
介绍递推和倒推的基本思想，递归和递推、递归与循环的关系，递推方程的求解方法。递推常用问题，使用递推和倒推设计和分析算法。
-
●5.1递归与递推
介绍递推的基本思想，递归和递推、递归与循环的关系。消除递归的方法。
-
●5.2正推与倒推
介绍倒推的基本思想和应用实例，递推和倒推的关系。
-
●5.3递推方程求解
介绍递推方程的求解方法和实例分析。
-
第六章分治算法
介绍分治基本思想和适用条件，改进分治算法的方法，分治算法的常用问题，使用分治方法设计和分析算法。
-
●6.1分治算法
引入合并排序，介绍分治算法的基本思想、适用条件、基本步骤和设计模式。合并排序算法和改进。
-
●6.2分治类型
引入实例介绍分治不相似、不独立情况的处理，三分法和减治类型。堆排序和排序算法比较。
-
●6.3减少子问题个数
引入实例介绍减少子问题个数，降低时间复杂度。
-
●6.4改进分治的均衡度
引入实例介绍改进分治的均衡度，降低时间复杂度。
-
●6.5减少合并的时间
引入实例介绍减少合并时间，降低时间复杂度。
-
第七章动态规划
介绍动态规划的基本思想、基本步骤、基本要素、复杂度分析。动态规划和分治算法、贪心算法、备忘录方法的联系和区别。递推关系和子问题的联系和区别。动态规划的分类、常用问题和设计与分析方法。
-
●7.1动态规划
引入兔子序列和赋权区间调度，介绍动态规划的基本思想、基本步骤和基本要素，动态规划和分治、贪心、备忘录方法的联系和区别。
-
●7.2数字三角形
引入数字三角形问题，介绍正推与反推、递推关系和状态转移方程。
-
●7.3增加变量
介绍0-1背包、恰好装满、完全背包和多重背包问题的动态规划算法。
-
●7.4区间动归
引入矩阵连乘介绍区间动归的算法和加括号的方法。
-
●7.5DAG图
引入实例介绍DAG图的动归算法，拓扑排序算法。
-
●7.6树图动归（上）
介绍了负权的最短路算法，负环的检测和处理。
-
●7.7树图动归（下）
介绍任意点间的最短路算法、树状动归和树上最大独立集问题的动归算法。
-
●7.8序列比对
介绍序列比对和最长公共子序列问题的动归算法。
-
第八章回溯算法
介绍回溯算法的思想和性质。递归回溯和迭代回溯。子集树和排列树算法框架。 回溯算法的效率分析。常用回溯算法的设计与分析方法。
-
●8.1装载问题
引入装载问题，介绍回溯算法的思想和性质。剪枝函数与使用。
-
●8.2旅行商问题
引入旅行商问题，介绍排列树算法和剪枝函数。
-
●8.3基本特征
介绍回溯算法的解题步骤，递归回溯和迭代回溯。子集树和排列树算法框架。 回溯算法的效率分析和改进方法。
-
第九章分支限界
介绍队列式(FIFO)分支限界法和优先队列式分支限界的基本思想与算法框架，回溯和分支限界的联系和区别，限界函数的改进，运用分支限界法解决实际问题。
-
●9.10/1背包问题
引入0-1背包问题，介绍队列式分支限界。
-
●9.2旅行商问题
引入旅行商问题，介绍优先队列式分支限界。
-
●9.3基本思想
分支限界的基本思想、基本步骤，回溯和分支限界的联系和区别，限界函数的改进。
-
第十章网络流算法
介绍最大流最小割、最大流算法、最小费用最大流算法，最大流算法的改进、推广与应用，二分图最大匹配算法、最佳匹配算法与应用。
-
●10.1最大流最小割
介绍网络、最大流与最小割，最大流最小割定理和算法。
-
●10.2最大流算法
介绍最大流算法的改进方法，容量缩放和最短路算法。
-
●10.3预流推进算法
介绍最高标号预流推进算法。
-
●10.4最大流推广
介绍最大流算法的推广和应用实例。
-
●10.5最小费用最大流
介绍最小费用最大流算法和应用实例
-
●10.6二分匹配
介绍二分图的性质、二分测试和二分匹配算法
-
●10.7 二分匹配应用
介绍二分匹配、独立集、顶点覆盖、路径覆盖的关系、性质与应用实例。
-
●10.8最佳匹配
介绍最佳匹配的概念和算法、最佳匹配算法的转化。
-
第十一章随机算法
介绍随机算法的分类和特点，数值随机算法、舍伍德算法、拉斯维加斯算法和蒙特卡罗算法的设计思想和设计分析。
-
●11.1随机算法1
介绍伪随机数的生成与应用，随机算法的分类和特点，数值随机算法的设计思想和应用实例。
-
●11.2随机算法2
介绍蒙特卡罗算法、拉斯维加斯算法、舍伍德算法的设计思想和应用实例。
-
第十二章P与NP
介绍P类、NP类和NP完全问题的概念和关系，多项式时间变换与多项式归约，NP完全问题的证明方法。NP完全问题的求解策略。
-
●12.1P与NP
介绍P类、NP的概念和关系，多项式归约与多项式时间变换，NP问题的性质，NP完全问题的概念和关系。
-
●12.2NP完全证明
介绍 NP完全问题的证明方法：局部替换、分支设计和限制技术。
-
●12.3NP完全求解
介绍NP完全问题的性质和求解策略、使用动态规划和分支限界求解小实例。
-
第十三章近似算法
介绍绝对近似算法、相对近似算法、多项式时间近似方案、完全多项式时间近似方案的概念、设计与证明方法。
-
●13.1绝对近似
介绍近似算法分类，近似性能比的概念，绝对近似算法的设计与证明。
-
●13.2相对近似（上）
介绍相对近似算法的设计与证明方法：贪心、组合技术。
-
●13.3相对近似（下）
介绍相对近似算法的设计与证明方法：定价法、线性规划和舍入。
-
●13.4近似方案
介绍多项式时间近似方案、完全多项式时间近似方案的概念和设计方法。