课程教学目标 针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程中加以介绍。 课程内容安排 本课程的内容分成两大部分：算法的基础知识、通用算法设计技术与分析方法。 第一部分是算法基础知识，约占20%，主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。 第二部分是通用的算法设计技术与分析方法，主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。
动态规划是另一种常用的算法设计技术。首先通过矩阵相乘的例子介绍动态规划算法的设计思想、主要步骤、分析方法、迭代实现与存储表示等。然后通过投资、背包、最长公共子序列等典型问题展现不同的动态规划算法在子问题划分与迭代计算时的特点和提高算法效率的技巧。
首先我们介绍一下本周的教学内容。 本周呢，主要涉及到动态规划算法的设计和分析。 首先呢我们先给一个例子，用最短路径为例， 来说明动态规划算法的设计思想和必要的条件。 接着，我们介绍一个动态规划 算法的设计例子，矩阵链相乘。通过这个例子来给出动态规划的算法的设计要素， 究竟需要考虑哪些个步骤。 下面，我们介绍动态规划算法的递归实现。 同时，我们也给出了动态规划算法的迭代实现。 最后是一些动态规划算法的例子，包括投资问题、 背包问题以及最长公共子序列问题。 这是本章的主要内容。