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

课程教学目标

针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程中加以介绍。
课程内容安排
本课程的内容分成两大部分：算法的基础知识、通用算法设计技术与分析方法。
第一部分是算法基础知识，约占20%，主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。
第二部分是通用的算法设计技术与分析方法，主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。

What you will learn

算法基础

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

序列求和与递推方程

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

分治算法的设计与分析

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

分治算法的典型应用

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