算法设计与分析 Design and Analysis of Algorithms

算法基础
-先通过几个典型的例子阐述算法设计与分析课程的学习内容及重要意义，接着介绍与算法有关的基本概念，如算法的伪码描述、时间复杂度函数的表示方法和一些常用的时间复杂度函数。

序列求和与递推方程
-介绍在算法分析中所需要的一些数学基础知识，如与程序迭代有关的序列求和公式，在估计递归计算工作量时常用的递推方程及其求解方法等。

分治算法的设计与分析
-分而治之是一种常用的算法设计技术。主要思想是将原始问题分解成若干个规模较小的独立的子问题，接着分别求解每个子问题，最后再将子问题的解综合以得到原始问题的解。通过本周的学习，你将了解分治算法的使用条件、主要的设计步骤、递归的实现技术、时间复杂度的分析方法、提高算法效率的途径等重要问题。

分治算法的典型应用
-在对分治算法有了基本的认识以后，进一步介绍一些典型的分治算法的成功案例，包括各种选择算法、涉及信号降噪处理的卷积计算与快速傅立叶变换、涉及图形学的平面点集凸包的计算等。

动态规划算法
-动态规划是另一种常用的算法设计技术。首先通过矩阵相乘的例子介绍动态规划算法的设计思想、主要步骤、分析方法、迭代实现与存储表示等。然后通过投资、背包、最长公共子序列等典型问题展现不同的动态规划算法在子问题划分与迭代计算时的特点和提高算法效率的技巧。

动态规划算法的典型应用
-在对动态规划算法有了基本认识之后，进一步介绍运用动态规划算法的一些成功案例，如用于黑白图片存储的变位压缩算法、最大子段和的计算、最优二分检索树的构造以及生物信息学中的RNA二级结构预测和序列比对算法等。

贪心法的设计
-贪心法是处理组合优化问题的常用算法。通过几个典型例子说明了贪心法的设计思想，同时重点阐述了贪心策略正确性的证明方法。针对某些不能保证对所有的输入都得到最优解的贪心策略讨论了其适用范围。

贪心算法的典型应用
-给出了贪心法应用的一些成功案例，如与最优前缀码设计有关的哈夫曼算法、应用广泛的最小生成树Prim算法和Kruskal算法、在网络路由中寻找单源最短路径的Dijkstra算法等。

回溯算法的设计思想
-回溯算法是一种基本的搜索技术，通过n后放置、0-1背包、货郎旅行、图的着色等问题介绍了回溯算法的设计思想、适用条件和实现方法，并给出了估计算法运行时间的一种抽样方法。

回溯算法的典型应用
-介绍提升回溯算法搜索效率的分支限界技术，给出求解最大团、货郎、圆排列、邮票设计等回溯算法的典型应用实例。

期末考试