1. 能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机软件系统中的复杂工程问题，以获得有效结论。

毕业要求指标点2.1：能识别和判断软件系统中的涉及问题的主要算法类别和方法，识别和判断嵌入式系统中硬件设备涉及问题的主要原理。

目标1

算法的基本概念，递归与分治法

课内实验

期末考试

2. 能够针对计算机应用系统的复杂工程问题，开发、选择与使用恰当的技术、资源、现代工程工具和信息技术工具，实现对复杂工程问题的预测与模拟，理解其局限性。能够就计算机应用系统的复杂工程问题与业界同行及社会公众进行有效沟通和交流，具有一定的写作能力、表达能力和人际交往能力；掌握一门外语，具备一定的国际视野，能够在跨文化背景下进行沟通和交流。

毕业要求指标点5.2：能理解并使用前沿的测试工具；在一定的指导下，能够选择和使用恰当技术资源、现代工程工具和信息技术工具，解决计算机应用系统设计开发中的复杂工程问题。

毕业要求指标点10.2：能够就复杂工程问题与业界同行及社会公众进行有效沟通和交流，具有良好的语言表达能力、写作能力和人际交往能力。

目标2

动态规划，贪心算法，回溯法，分支限界

课内实验

期末考试

1

算法的基本概念

教学内容：

算法的定义、算法的5个基本特点及其内涵、算法的描述方法、算法的分类、算法性能的度量方法、算法的时间和空间复杂度的求解和度量方法。

以冒泡排序、基数排序和归并排序分析其算法的时间复杂度和空间复杂度。

理解算法的定义、算法的5个基本特点和分类；掌握常见的算法描述方法、算法时间复杂度的分析和度量方法。

重点：

算法的定义、算法的5个基本特点和分类、常见的算法描述方法以及算法时间复杂度的分析和度量。

难点：

算法时间复杂度的分析方法和度量结论的得出依据。

4

讲授

目标1

目标2

2

递归与分治法

递归的定义、递归的本质、递归和循环的关系、递归的特点。

以汉诺塔问题、杨辉三角和Fibonacci数列问题举例揭示递归的相关特点。

分治法的本质、分治法的设计思路、用递归法实现分治法和分治法的非递归实现方法。

以二分搜索、快速排序、线性时间选择和平面上的最近点对等问题为例讲解分治法的算法设计方法。

理解递归的本质和特点；掌握分治算法的设计方法和分治法的非递归实现方法。

重点：

递归的本质和特点；分治法的设计思想和要点。

难点：

分治算法的设计方法（关键在于合并子问题解的方法的设计）

8

讲授

案例

实验

目标1

目标2

3

动态规划

什么是动态规划、动态规划的2个基本要点和动态规划设计算法的方法。

用递归法和递推法实现动态规划时的特点和区别。

以矩阵乘法连、最大子段和、图像压缩问题和0~1背包问题等为例讲解动态规划的算法设计方法。

通过例示动态规划算法，学会判别一个问题是否适合用动态规划求解、能给出简单问题的动态规划状态转移方程。

重点：

动态规划的2个基本要点和动态规划设计算法的方法。

难点：

判别一个给定问题是否适合用动态规划求解、能给出问题的动态规划状态转移方程。

6

讲授

案例

实验

目标1

目标2

4

贪心算法

贪婪算法的本质和应用贪婪算法求解问题的2个要件。

贪婪算法与前述动态规划算法的区别。

以经典的最小生成树、单源最短路径和哈夫曼编码问题为例。

通过例示贪婪算法，学会判别一个问题是否适合用贪婪求解、能对给定问题设计出相应的贪婪算法。

重点：

贪婪算法的本质和应用贪婪算法求解问题的2个要件。

难点：

贪婪算法与前述动态规划算法的区别。

对给定问题设计出相应的贪婪算法。

4

讲授

案例

实验

目标1

目标2

5

回溯法

回溯法本质是枚举或者深度优先搜索，为了提高搜索效率加快搜索速度，引入了剪枝策略。

在枚举的算法框架中引入剪枝。

以经典的8皇后、圆排列和0~1背包问题的回溯法求解为例。

学会枚举搜索的算法设计方法，并学会使用剪枝的思想。理解判定性问题用回溯法一定可解。

重点：

深度优先搜索的算法设计方法。

难点：

设计有效的剪枝策略。

6

讲授

案例

实验

目标1

目标2

6

分支限界

分支限界本质也是枚举或者广度优先搜索，为了提高搜索效率加快搜索速度，引入了剪枝策略。

在广度优先搜索的算法框架中引入定界函数加快搜索速度。

以0~1背包问题的分支定界法求解为例。

学会枚举搜索的算法设计方法，并学会使用定界函数的思想。判定性问题和最优化可用分支定界的思想设计搜索算法。

重点：

广度优先搜索的算法设计方法。

难点：

设计有效的分支定界策略加快搜索速度，以及在此基础衍生出的双向广度优先搜索算法。

4

讲授

案例

实验

目标1

目标2

目标1：掌握算法的概念、算法的表示，算法的分类、算法的时间复杂度和空间复杂度，并能对指定的算法进行性能分析得出正确的时间复杂度和空间复杂度结论。

算法的基本概念

期末考试

10%

100%

B₁

递归

实验

20%

100%

A₁

目标2：掌握分治法、动态规划、贪心算法、回溯法、分支限界算法等常用算法的设计思想和相应的算法设计技巧。

分治法、动态规划、贪心算法、回溯法、分支限界法。

实验

20%

100%

A₂

根据具体问题，选择合适算法并完成代码实现。

期末考试

50%

100%

B₂

总评成绩（100%）= 实验（40%）+期末考试（60%）

100%

——

——

考查点

实验1 分治算法

实验2 动态规划

实验3 贪心算法

实验4 回溯与分支限界

总评分占比

10%

10%

10%

10%

评分标准

100%

至

90%

89.9%

至

80%

79.9

至

70%

69.9%

至

60%

59.9%至

0