单元一:基础知识

学时:6

支撑课程目标:LO1,LO4

教学内容

1．课程简介:课程的学科地位、教学内容、学习目标、学习方法和考核方式等

2．有关算法的基本概念

3. 算法的伪码描述

4. 算法分析的基本方法

5．算法分析的数学基础:函数的渐近界、求和方法、递归方程求解方法

学习目标

1. 能够正确使用渐近表示算法复杂度的记号。

2. 能够推导常用求和公式，用定积分方法近似求和，求解简单常见的递归关系。

3. 能够运用算法分析的基本方法和数学知识去分析和求解具体算法的时间复杂度。

教学方式

1. 课堂教学:采用PPT讲授理论知识，辅以板书展示分析和推理过程。

2. 作业:布置算法分析作业题。

3. 思政教育:

（1）算法复杂度用于度量算法运行期间的时空开销，算法设计与分析目的是为了用较少的资源解决问题。由此增强学生节约资源、提高效率意识。

（2）算法运行时间与算法空间开销一个主要区别是时间不可重复使用，空间可重复使用。引导学生感悟时间的宝贵，逝去的青春不再来，要珍惜现在读书学习的好时光。

（3）算法的渐近复杂度，比如O(n)和O(log¹⁰n)，对于较小的n而言，n小于log¹⁰n，但对于较大的n，n大于log¹⁰n，且随着n增大，其差距越来越大。引导学生感悟大小和高低不能仅看短期效应，要看得长远。

评价方式

1. 算法分析作业:渐近表示算法复杂度记号的使用、递归方程的求解、具体算法时间复杂度的分析。

2．期末考核:算法分析和算法优化的相关试题。

支撑理由

1. 支撑课程目标LO1: 作业题和期末考核中有关算法分析的相关题目旨在检验能否正确使用算法相关概念和算法分析基本方法和相关数学知识。

2. 支撑课程目标LO4: 期末考核中算法设计类试题旨在检验能否通过比较分析逐步改进和优化算法。

单元二:分治策略

学时:6

支撑课程目标:LO1,LO2,LO4

教学内容

1．分治策略的基本思想

2．分治算法的分析技术

3．改进分治算法的途径

4．典型实例

4.1快速排序算法

4.2选择问题

4.3 n-1次多项式在全体2n次方根上的求值

学习目标

1. 能够使用分治策略设计求解某些问题的分治算法，并能够在问题实例上模拟算法的执行。

2. 能够分析分治算法的时间复杂度，并能够尝试通过减少子问题数目或减少合并步骤的时间等策略来改进分治算法。

3. 能够领悟三个典型应用的精巧分治算法的设计思想，能编程实现算法。

教学方式

1. 课堂教学:采用PPT讲授理论知识，辅以动画展示算法执行过程。

2. 作业和编程实践:布置在线编程作业题。

3. 思政教育:

分而治之是解决问题的一种常见策略。分治法中如果不对几个环节采用优化措施，可能与穷举法法时间复杂度一样。引导学生感悟日常处理问题中采用表面上不同的处理方法不一定能导致理想的结果，还是要利用问题的特征针对各环节做得最好。

评价方式

1. 算法分析作业:分治算法的设计和时间复杂度分析。

2. 编程实践作业:

（1）编程实现数据结构中几个经典的排序算法（包括选择排序、插入排序、归并排序、快速排序等），观察每个算法在n=1000,5000,10000,50000的随机算例上的比较次数和运行时间，并分析其运行时间、比较次数与算法复杂度的关系。

（2）针对具体问题，设计分治算法并实现算法。

3．期末考核:分治算法设计和分析试题。

支撑理由

1. 支撑课程目标LO1:作业题中分治算法的分析题、编程实践中典型分治算法的实现及性能测试题旨在检验能否分析和比较常见算法的性能。

2. 支撑课程目标LO2:编程实践中分治算法设计及实现题旨在检验能否设计求解简单问题的分治型算法且能有效实现算法。

3. 支撑课程目标LO4:期末考核中分治算法设计类试题旨在检验能否通过问题分析来逐步改进和优化算法。

单元三:动态规划

学时:8

支撑课程目标:LO2,LO3,LO4

教学内容

1．动态规划的设计思想

2．动态规划算法的设计要素

3．动态规划算法的典型应用

3.1 投资问题

3.2 背包问题

3.3 最长公共子序列LCS

3.4 图像压缩

3.5 最大子段和

3.6 最优二分检索树

3.7 生物信息学中的动态规划算法

学习目标

1. 能够判断一个具体问题是否适合用动态规划方法求解。

2. 能够采用动态规划方法设计出求解具体问题的算法，并能够有效地实现算法，能够在问题实例上模拟算法的执行。

3. 能够领悟几个典型应用的动态规划算法的设计思想，能编程实现算法。

4. 能够领悟并感受动态规划方法所蕴含的哲理。

教学方式

1．课堂教学:采用PPT讲授理论知识，辅以动画展示算法执行过程。

2. 作业和编程实践:布置在线编程作业题。

3. 思政教育:

动态规划法基本思想是为了避免重复计算，利用空间来换时间。对于这种技术，可以适时教育学生要厉行节约，节省时间资源，提高工作效率。

评价方式

1. 编程实践作业:针对较简单的应用问题，直接设计动态规划算法并编程实现。针对较复杂的实际应用问题，从计算思维角度，对问题进行分析、建模、设计算法并实现算法。

2．期末考核:动态规划算法设计与分析题。

支撑理由

1. 支撑课程目标LO2:编程实践中针对简单问题的编程题旨在检验能否用动态规划方法设计求解问题的算法并编程实现算法。

2. 支撑课程目标LO3:编程实践中针对较复杂的实际应用问题的编程题旨在检验能否从计算思维的角度，对问题进行分析、建模、设计算法并实现算法。

3. 支撑课程目标LO4:期末考核中动态规划算法试题旨在检验能否通过问题分析逐步实现对算法进行优化。

单元四:贪心法

学时:5

支撑课程目标:LO1,LO2,LO3

教学内容

1．贪心算法的设计思想

2．关于贪心算法的正确性证明

3．对贪心算法得不到最优解情况的处理

4．贪心算法的典型应用

4.1 最优前缀码

4.2 最小生成树

4.3 单源最短路径

学习目标

1. 能够判断一个具体问题是否适合用贪心法求解，能够针对具体问题设计其贪心算法并能尝试证明算法的正确性。

2. 能够针对贪心法不能得到正确解的问题，尝试设计动态规划算法或其它算法来求解。

3. 能够领悟几个典型应用的贪心算法的设计思想，能编程实现算法，并能在问题实例上模拟算法的执行。

教学方式

1. 课堂教学:采用PPT讲授理论知识，辅以动画展示算法执行过程。

2. 编程实践作业:布置在线编程作业题。

3. 思政教育:

针对一个问题通常可以设计出多种不同的贪心算法，这些贪心算法都是依据局部信息做出的当前最好选择，但不是所有贪心算法都能最终导出全局最优解。引导学生感悟个人利益的考虑要长远来看，符合集体利益、国家利益才是最好的。

评价方式

1. 编程实践作业:针对具体应用问题，设计其贪心算法并编程实现。

2．期末考核:贪心算法设计、正确性证明及在问题实例上模拟算法执行。

支撑理由

1. 支撑课程目标LO1:期末考核中贪心算法证明类试题旨在检验能否分析和证明贪心算法的正确性。

2. 支撑课程目标LO2:期末考核中贪心算法设计类试题旨在检验能否设计求解问题的贪心算法。

3. 支撑课程目标LO3:编程实践中针对实际应用问题的贪心算法编程题旨在检验能否从计算思维的角度，对问题进行分析、建模、设计算法并实现算法。

单元五:回溯与分支限界

学时:5

支撑课程目标: LO2,LO3,LO4

教学内容

1. 回溯算法的基本思想和适用条件

2. 回溯算法的设计步骤

3. 回溯法的效率估计和改进途径

4. 分支限界

4.1背包问题

4.2 最大团问题

4.3 货郎问题

4.4 圆排列问题

4.5 连续邮资问题

学习目标

1. 能够使用回溯算法求解具体问题，并能熟练编程序实现算法。

2．能够用随机方法对回溯算法进行效率评估及算法改进。

3. 能够使用分支限界算法求解具体问题，并能熟练编程序实现算法。

4. 能够领悟几个典型应用的分支限界算法的设计思想，能编程实现算法，并能在问题实例上模拟算法的执行。

教学方式

1. 课堂教学:采用PPT讲授理论知识，辅以动画展示算法执行过程。

2. 实验教学:布置在线编程作业题。

3. 思政教育:

（1）针对回溯法的基本思想，引导学生感悟日常处理问题中如何提高效率，避免做无用功。

（2）针对典型应用中的分支限界算法，启发学生感悟其代价函数中所蕴含的哲学思想，思考这些思想如何推广去求解其他问题实例。

评价方式

1. 编程实践作业:回溯法和分支限界法的应用编程。

2．期末考核:回溯和分支限界算法的设计和优化，在问题实例上模拟算法的执行。

支撑理由

1. 支撑课程目标LO2:编程实践中针对简单应用问题的编程题旨在检验能否用设计回溯算法求解问题并编程实现算法。

2. 支撑课程目标LO3:编程实践中针对较复杂的实际应用问题的编程题旨在检验能否从计算思维的角度，对问题进行分析、建模、设计算法并实现算法。

3. 支撑课程目标LO4:编程实践和期末考核中涉及到对较复杂工程问题的求解旨在检验能否通过对问题深入分析逐步优化算法。

课程总复习课

学时:2

支撑课程目标:LO1,LO2,LO3,LO4

教学内容

1. 复习各单元的主要知识点。

2. 讲评各单元的相关练习题。

学习目标

1. 能够通过复习课梳理清楚本课程的主要知识点。

2. 能够通过讲评练习题巩固算法设计与分析的典型方法和技术。

教学方式

课堂教学:采用PPT讲授，回顾主要知识点，并讲评相关练习题的解题思路。

评价方式

期末考核试题

支撑理由

期末考核试题中包含了本课程的主要知识点和相关习题中用到的方法和技术方法，覆盖了所有课程目标。