算法设计与分析（Python版）| 教学大纲

算法设计与分析

Design and Analysis of Algorithms

适用范围：2018本科人才培养方案

课程编号：0604808150

学    分：3学分

学    时：52学时（其中：讲课学时：40；实验学时：12）

开课学期：5

先修课程：程序设计基础、离散数学、数据结构

适用专业：计算机科学与技术

建议教材：《算法设计与分析》，王秋芬等主编，清华大学出版社，2011

开课单位：计算机与信息工程学院

大纲版本：1

课程性质：算法的设计与分析属于专业平台必修课，是计算机科学的核心问题之一。算法涉及的范围十分广泛，不论是从事计算机硬件设计，还是从事计算机软件设计，都需要认真研究算法。该课程系统地介绍计算机算法的设计方法与分析技巧，通过课程学习，为独立地设计算法和对算法进行分析奠定坚实的知识基础，对从事计算机软件和计算机应用的研究者来说是非常重要和必不可少的。

课程任务：通过学习该课程，使学生在知识方面要求： 掌握算法的定义及基本概念、计算模型和复杂度的衡量；为分析算法的复杂性做准备，要了解相应的数学知识；掌握算法设计的过程和方法；掌握算法的时间复杂度、空间复杂度和稳定性的分析；具有问题抽象和建模的初步能力。在能力方面要求：通过本课程的学习，学生要掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法概率算法、线性规划和网络流法和NP完全性理论与近似算法等，并会分析算法的效率，能够用所学方法解决实际问题。算法设计与分析能够有效锻炼学生的逻辑思维能力和想象力，更重要的是培养学生的创造性思维能力；培养学生在理论的指导下，分析、解决实际问题的能力。这正是计算机科学与技术专业培养目标的核心所在。

（一）课程具体目标

目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现。

目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力；

目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案。

（二）课程目标与专业毕业要求的关系

本课程对专业毕业要求及其指标点的支撑

课程目标

支撑的毕业要求

支撑的毕业要求指标点

目标1

毕业要求1：能够将数学、自然科学、工程基础和计算机科学与技术专业知识用于解决计算机工程领域内的复杂工程问题。

指标点1-2：掌握算法分析与程序设计等计算机科学与技术专业知识，能将其用于计算机复杂工程问题模型的实现。

目标2

毕业要求2：能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机工程领域的复杂工程问题，以获得有效结论。

指标点2-3：能够基于数学、自然科学和计算机科学与技术的基本原理，对计算机复杂工程问题进行提炼、定义、建模、分析和评价。

目标3

毕业要求4：能够基于计算机学科相关的原理并采用科学方法对计算机工程领域的复杂工程问题进行研究，包括设计实验、分析与解释数据，并通过信息综合得到合理有效的结论。

指标点4-1：针对计算机复杂工程问题，能够基于计算机学科原理，通过调研和分析，设计合适的研究方案。

（三）课程对解决复杂工程问题能力的培养

在课程理论知识讲授环节，不但注重培养学生对算法设计与分析的深入理解，使学生掌握解决计算机应用领域复杂工程问题所需的基本理论以及了解相关技术对社会等的影响，而且跟踪行业发展前沿，探讨当前热点问题激发学生的学习兴趣。并通过适当的课后作业锻炼和检验学生解决复杂工程问题的能力。在实验教学环节，以培养学生解决复杂工程问题的能力为目标，围绕课程支撑的课程目标安排实验项目，设计实验内容，明确实验要求，指导实验实施，严格实验成果考核。在课程考核环节，根据课程支撑的课程目标选择合适的考核方式，考题设置完全覆盖课程目标，考题设计应充分考虑学生解决复杂工程问题所需知识和能力。总之，本课程的教学通过在理论讲授、课后作业、课内实验、课程考核等环节充分贯彻培养学生解决复杂工程问题能力的理念和要求，实现本课程支撑课程目标的达成。

（一）理论教学

第1章 算法概述（4学时）

1．教学内容

（1）算法的基本概念。

（2）算法设计的一般过程。

（3）算法分析的概念及渐进意义下的记号。

（4）时间复杂度和空间复杂度建立的依据。

（5）递推方程求解方法。

2．基本要求

（1）理解算法的基本概念、复杂度的衡量。

（2）掌握渐进复杂的概念及渐进意义下的记号。

（3）掌握时间复杂度建立的依据和递推方程求解的方法。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”，使学生了解算法的基本概念、复杂度的衡量，掌握渐进复杂的概念及渐进意义下的记号，掌握时间复杂度建立的依据和递推方程求解的方法，为解决实际工程问题奠定基础。

替代式教学策略和案例教学法，让学生理解算法的基本概念及算法复杂度的分析方法，掌握渐进复杂度表示及递推方程求解方法。

第2章 贪心算法（6学时）

1．教学内容

（1）贪心法的基本思想及基本要素。

（2）会场安排问题、最优装载问题。

（3）单源最短路径问题。

（4）哈夫曼编码。

（5）最小生成树。

（6）背包问题

2．基本要求

（1）了解贪心法的应用范围，理解贪心法的基本思想、特点。

（2）掌握典型问题的精巧贪心算法（如会场安排问题、最短路径问题的Dijkstra算法、求最小生成树的Kruskal算法和Prim算法等）的基本思想，能利用贪心算法解决实际工程中遇到的问题。通过这些应用，掌握使用贪心策略设计算法的关键步骤、熟悉算法的分析方法及算法正确性的证明方法。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解贪心算法的基本思想，掌握典型问题的精巧贪心算法，能利用贪心算法解决实际工程中遇到的问题。

启发式和任务驱动相结合，让学生算法设计的过程及算法复杂度的分析方法，掌握贪心法的基本要素，如何使用贪心法解决实际问题。采用任务驱动，充分调动学生的积极性。

第3章 分治算法（6学时）

1．教学内容

（1）分治法基本思想。

（2）分治法的求解步骤。

（3）二分查找。

（4）选第二大元素。

（5）循环赛日程表。

（6）合并排序。

（7）快速排序。

（8）线性时间选择。

2．基本要求

（1）了解分治法的适用范围，理解其基本思想、特点。

（2）掌握设计分治算法的基本步骤；掌握使用分治策略设计的典型问题的精巧算法（如二分搜索算法、排序算法、选择问题算法等）。

（3）理解算法的设计思想、分析方法及复杂度结论，能在给定问题实例上模拟算法的执行。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

”。使学生了解分治法的适用范围，理解其基本思想，掌握使用分治策略设计的典型问题的精巧算法，能够利用分治算法解决实际工程问题。

分组讨论和启发式教学，让学生理解分治算法的基本思想，掌握分治法分与治两个要点。启发学生回顾以前的哪些算法使用了分治策略，生活中哪些事情也是分治。

第4章 动态规划（10学时）

1．教学内容

（1）动态规划的基本思想及要素。

（2）矩阵连乘问题。

（3）最优凸多边形三角剖分。

（4）最长公共子序列问题。

（5）加工顺序问题。

（6）0-1背包问题。

（7）最优二叉查找树。

2．基本要求

（1）了解动态规划法的适用范围，理解其基本思想、特点，设计算法的基本步骤。

（2）掌握典型问题（如最长公共子序列问题、矩阵连乘、加工顺序、0/1背包及最优二叉查找树等问题）的动态规划算法，能在给定问题实例上模拟算法的执行。

（3）能通过这些典型应用，熟练地掌握使用态规划法设计算法的关键步骤。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解动态规划法的适用范围，理解其基本思想、特点，设计算法的步骤，掌握典型问题的动态规划算法求解方法，能够熟练应用动态规划算法为解决计算机应用的工程项目问题。

案例教学法，让学生了解为什么要使用动态规划，理解动态规划算法的基本要素，掌握动态规划最优子结构分析及递归式的设计方法。任务驱动教学法，让学生动手进行算法实现和分析。

第5章 回溯法（6学时）

1．教学内容

（1）回溯法的算法框架及思想。

（2）子集树。

（3）排列树。

（4）满m叉树。

2．基本要求

（1）了解回溯法，理解其基本思想、特点。

（2）掌握针对具体问题设计回溯算法的基本步骤和方法。

（3）通过在典型问题（如旅行商问题、0-1背包问题等）上的应用，较熟练掌握使用回溯法求解问题的基本步骤和方法，并能熟练编程序实现算法。

（4）了解回溯算法估计方法。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解回溯法、分支限界法的应用范围，掌握针对具体问题设计回溯算法的基本步骤和方法，并能熟练编程序实现算法，为解决实际工程问题奠定基础。

分组讨论和案例教学法，让学生掌握回溯法及算法框架；回溯法的算法设计模式；回溯法及分支限界法的效率分析。布置任务，提高学生动手实践能力。

第6章 分支限界法（4学时）

1．教学内容

（1）分支限界法的基本思想。

（3）0/1背包问题。

（3）旅行商问题。

（4）图的m着色问题。

（5）分支限界法与回溯法的比较。

2．基本要求

（1）了解分支限界法的应用范围，理解其基本思想、特点。

（2）掌握针对具体问题设计分枝限界算法的基本步骤和方法。

（3）通过在典型问题（如m着色问题、旅行商问题、0-1背包问题等）上的应用，较熟练掌握使用分枝限界法求解问题的基本步骤和方法，并能熟练编程序实现算法。

（4）了解分枝限界算法的效率估计方法。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解回溯法、分支限界法的应用范围，掌握针对具体问题设计分枝限界算法的基本步骤和方法，并能熟练编程序实现算法，为解决实际工程问题奠定基础。

分组讨论和案例教学法，让学生掌握分支限界法算法框架；分支限界法的算法设计模式；分支限界法的效率分析。布置任务，提高学生动手实践能力。

第7章 线性规划问题与网络流（8学时）

1．教学内容

（1）线性规划的基本概念、定理及单纯形算法。

（2）最大网络流问题的解法。

（3）最小费用流问题的解法。

2．基本要求

（1）了解线性规划模型的特点、线性规划问题的标准型及退化处理。

（2）掌握线性规划问题解的概念、有关解的基本定理。

（3）掌握单纯形法的原理和求解方法。

（4）掌握最大网络流问题的求解方法和最小费用流问题的求解方法。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生解线性规划模型的特点、线性规划问题的标准型及退化处理，掌握单纯形法的原理和求解方法，掌握最大网络流问题的求解方法和最小费用流问题的求解方法，能够利用最大流算法解决实际工程问题。

案例教学和启发式教学法，让学生理解线性规划和网络流的基本思想，掌握单纯形算法；最大网络流问题；最小费用流问题的求解方法。启发学生动手动脑，解决布置的任务。

第8章 随机化算法（6学时）

1．教学内容

（1）随机化算法的类型及特点。

（2）随机数发生器。

（3）数值随机化算法。

（4）蒙特卡罗算法。

（5）拉斯维加斯算法。

（6）舍伍德算法。

2．基本要求

（1）了解随机化算法的基本特征。

（2）理解数值随机算法、舍伍德算法、拉斯维加斯算法、蒙特卡洛算法的特点和适用范围。

（3）掌握素数测试、整数的因子分解等随机化算法。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”，使学生了解随机化算法的基本特征，掌握素数测试、整数的因子分解等随机化算法，体会随机化算法在工程项目中的应用，为解决实际工程问题奠定基础。

启发式教学法，让学生理解什么是随机化算法，掌握四种随机化算法的特点和适用范围，启发学生思考生活中的随机化例子，鼓励学生动手实现。

第9章 NP完全理论（2学时）

1．教学内容

（1）P类和NP类问题。

（2）NP完全问题。

（3）NP完全问题的近似算法。

2．基本要求

（1）了解P类和NP类问题。

（2）理解NP完全问题及近似算法。

3．支撑的课程目标

本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”，使学生了解P类和NP类问题，理解NP完全问题及近似算法，为解决实际工程问题奠定基础。

分组讨论和启发式教学法，让学生理解P类和NP类问题、NP完全问题，及近似算法的设计与可靠性分析。启发学生思考以前学过的算法属于什么问题类型。

（二）实验教学

实验项目1．贪心算法应用（2学时）

1．实验内容

（1）给出背包问题的贪心算法。

（2）给出会议安排问题的贪心算法。

（3）给出算法复杂度分析。

2．基本要求

（1）理解和掌握贪心算法的基本思想和步骤。

（2）掌握贪心算法的复杂性分析方法。

（3）能够利用贪心算法解决实际工程问题。

3．支撑的课程目标

本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

本实验通过问题启发式引导学生依据所掌握的相关知识点，熟悉某一具体问题的贪心算法求解方法，加深对贪心算法的理解，达到课程目标的要求。

实验项目2．分治算法应用（2学时）

1．实验内容

（1）给出合并排序算法和程序。  

（2）给出快速排序算法和程序。

（3）给出算法复杂度分析。

2．基本要求

（1）熟悉分治算法的分解与治理方法。

（2）掌握分治法的应用场景和递归求解的方法。

（3）锻炼利用分治法解决实际问题的能力。

3．支撑的课程目标

本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

本实验通过问题启发式引导学生依据所掌握的相关知识点，熟悉某一具体问题的分治算法求解方法，加深对分治算法的理解，达到课程目标的要求。

实验项目3．动态规划算法应用（2学时）

1．实验内容

（1）给出最优三角剖分的动态规划算法和程序。  

（2）给出最优二叉树的动态规划算法和程序。

（3）给出算法复杂度分析。

2．基本要求

（1）理解动态规划算法的适用场景。

（2）掌握动态规划问题的算法设计与实现方法。

（3）掌握动态规划算法的复杂度分析方法。

3．支撑的课程目标

本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

本实验通过启发式方式引导学生依据所掌握的相关知识点，根据具体问题设计动态规划算法并分析优化，达到课程目标的要求。

实验项目4．搜索算法应用（2学时）

1．实验内容

（1）给出最大团问题的回溯算法和程序。

（2）给出旅行商问题的分支限界算法和程序。

（3）掌握搜索算法的复杂度分析方法。

2．基本要求

（1）理解和掌握搜索算法的算法设计框架。

（2）理解和掌握搜索算法解决实际问题的过程和算法设计优化方法。

3．支撑的课程目标

本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

本实验通过启发式方式引导学生依据所掌握的相关知识点，根据具体工程项目设计搜索算法并分析优化，达到课程目标的要求。

实验项目5．随机化算法应用（2学时）

1．实验内容

（1）给出n皇后问题的随机化算法和程序。

（2）给出随机快速排序的算法和程序。

（3）掌握随机化算法的复杂度分析方法。

2．基本要求

（1）熟悉随机化算法的类型和特点。

（2）根据具体问题设计随机化算法。

3．支撑的课程目标

本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”。

本实验通过启发式方式，引导学生掌握在计算机应用项目中设计随机化算法解决实际问题，达到课程目标的要求。

实验项目6．网络流算法应用（2学时）

1．实验内容

（1）给出飞行员配对问题的算法和程序。

（2）给出太空实验室计划的算法和程序。

（3）掌握网络流算法的复杂度分析方法。

2．基本要求

（1）理解并体会具体问题分析抽象的过程。

（2）运用网络流算法解决实际问题。

（3）培养学生的系统思维，提升解决复杂工程问题所需的问题分析和系统设计能力。

3．支撑的课程目标

本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

本实验通过启发式方式，引导学生依据所掌握的相关知识点，培养具备学生根据具体工程项目问题进行网络流算法设计的能力，达到课程目标的要求。

（一）教学方式

课程目标与教学环节

序号

课程目标

教学环节

讲授

作业

实验

1

掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现

ü

ü

ü

2

目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力

ü

ü

ü

3

目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案。

ü

ü

ü

以课堂讲授为主，结合课堂讲授内容安排课内实验及课后作业，加深对理论教学内容的理解和认识，培养工程实践能力。

（二）教学方法

本课程贯彻“以学生为主体，以教师为主导”的教学思想，采用“互动、开放”的课堂形式，具体以课堂教学为主，结合自学、课后作业和实验教学，采用启发式、问题式的教学方法，基于项目的实际问题，提高学生解决复杂计算机算法应用问题的能力，达到课程目标的要求。相关课程目标支撑如下：

课堂教学主要讲解与算法设计与分析有关的基本概念、基本理论以及基本分析方法，并将日常生活中所遇到的算法问题、智能应用系统案例融入基本理论的讲解，使同学们更好地熟悉或掌握算法的基本原理，提高学生对算法的兴趣、熟悉算法设计分析及优化、思维方式和研究方法。课堂教学尽量引入互动环节，通过问题导入教学，引导学生寻找解决方案，提高教学效果，达到“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”的要求。

通过实验教学增强学生理解理论知识，动手寻找答案，以培养学生解决数据库应用问题的能力，达到“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

课堂讨论以及课后作业，能培养同学们的综合能力，熟悉运用所学知识的能力，锻炼表达能力，并通过合作客观评价相关工程对社会、经济等影响，发表自己的见解。达到“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”的要求。

（三）课时安排

本课程总学时52学时，其中：讲授40学时，实验（或上机或综合练习）12学时，具体教学安排如下表。

学时分配与教学方法

序号

教学内容

学时分配

教学方法

1

算法概述

4

讲授

2

贪心算法

6

讲授

3

分治算法

6

讲授

4

动态规划

10

讲授

5

回溯法

6

讲授

6

分支限界法

4

讲授

7

线性规划和网络流

8

讲授

8

随机化算法

6

讲授

9

NP完全理论

2

讲授

10

实验一：贪心算法应用

2

实验

11

实验二：分治算法应用

2

实验

12

实验三：动态规划算法应用

2

实验

13

实验四：搜索算法应用

2

实验

14

实验五：随机化算法应用

2

实验

15

实验六：网络流算法应用

2

实验

合计

64

（一）考核方式及具体要求

最终成绩由平时作业成绩、上机与实验成绩和期末成绩等组合而成，各部分所占比例如下：

平时作业成绩（占30%）：包括章节测试、作业。其中，作业：教师评判作业并根据作业内容的正确性、完成认真度及规范性给出评定成绩。

上机与实验（占20%）：主要考核根据常见的问题进行算法设计能力、算法分析的能力、算法优化的能力，学生可根据任课教师布置的实验题目与目标，通过结合算法的理论知识，进行设计、代码编写、测试与分析，给出一定形式的实验结果及分析说明。上机与实验考核：根据实验结果正确性的完成情况及实验报告的规范性给出评定成绩。

期末考试成绩（占50%）：在考核算法基础知识掌握程度的基础上，重点考核理论知识的应用能力，以及解决计算机应用工程项目中相关复杂工程问题的能力。期末考试采用书面闭卷形式，主要题型可以是选择题、填空题、简答题、算法设计题、综合应用题等。

课程考核能够针对学生对专业核心知识的掌握情况、运用理论知识解决计算机应用的能力、客观评价算法优化及智能算法领域对社会、文化等影响的能力和能及时跟踪相关行业发展状况，就当前的热点问题发表自己见解的能力等方面进行考核，支持“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。

（二）成绩评定办法及依据

1.平时成绩

章节测试成绩由网络教学平台自动批阅评定。

平时成绩评分标准（作业）

分值

观测点

90-100分

70-89分

60-69分

0-59分

得分

作业完成程度

（权重10%）

按时全部

完成

延时全部

完成

按时部分

完成

延时部分

完成

算法基础知识掌握及复杂算法问题应用系统解决方案的分析

（权重45%）

概念清晰，分析得当

主要概念清晰，但部分分析有误

部分概念清晰，分析中有明显错误

基本概念不清，分析错误

应用算法设计的基本理念，在计算机应用工程项目中的解决方案的正确性

（权重45%）

所提方案能够解决问题，思路清晰，计算正确

所提方案的主要思路、过程和计算过程正确

方案部分可行

不能制定方案

总分

2.实验成绩

实验成绩评分标准

分值

观测点

90-100分

70-89分

60-69分

0-59分

得分

算法基础理论

（权重10%）

对实验所需的理论知识非常清楚

对实验所需的理论知识较为清楚

对实验所需的理论知识基本清楚

对实验所需的理论知识不清楚

实验方案选择及分析

（权重40%）

查阅相关资料选择实验方案科学合理，分析正确

查阅相关资料选择实验方案较为科学合理，分析正确

查阅相关资料选择实验方案合理，分析有误

查阅相关资料选择实验方案不合理，分析错误

实验结果分析与总结

（权重40%）

实验数据、结果、分析和总结完整准确

实验数据、结果、分析和总结较为完整准确

实验数据、结果、分析和总结部分完整

实验数据、结果、分析和总结有错误

实验报告质量

（权重10%）

实验报告规范完整

实验报告较为规范完整

实验报告规范但不完整

实验报告不规范完整

总分

3.考试成绩

课程考试根据课程目标设计相关试题，综合检验学生对课程相关知识的掌握、综合应用及解决复杂工程问题的能力；每次考试试题不同，根据每次考试题目设计相应评分标准。

4.综合成绩

考核方式在各课程目标中的比例

课程目标

考核方式/占比

目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现。

考试/50%

作业、章节测试/50%

目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力。

考试/50%

实验/50%

目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案。

作业、章节测试/30%

实验/70%

课程目标达成采用定量和定性两种方式进行评价，相互印证课程目标的达成情况；定量评价采用课程目标考核成绩分析法，方法如下：

课程某分目标达成度=

定性评价根据课程目标设计相应的问题，针对本课程全体学生进行问卷调查，以学生为主体，评价自己通过课程学习达成课程目标情况。

[1]《算法设计与分析》，赵端阳等编著，清华大学出版社，2015年。

[2]《算法设计与分析（第2版）》，屈婉玲等编著，清华大学出版社，2016年。

制定人：  

审核人：   

批准人： 

制定时间：

审核时间：

批准时间： 

本书主讲贪心算法、分治算法、动态规划算法、回溯算法、网络流、随机化算法、近似算法，侧重用具体实例图解演示算法运行过程及python语言实现。本书特色：深入浅出地从问题分析，到数据结构选择、算法设计、Python实战，提供问题解决的全程式指导；提供实例构造、详细图解，带领学习者直观、形象地逐步运行算法，看到算法单步运行结果；提供算法的Python语言实现，让算法在学习者心里落地生根。

上下滚动查看 ↓

目录

第1章算法概述

1.1什么是算法

1.2为什么学习算法

1.3算法的描述方式

1.4算法设计的一般过程

1.5算法分析

1.5.1算法分析的概念

1.5.2时间复杂度和空间复杂度

1.5.3渐近复杂性态

1.5.4渐近意义下的记号

1.5.5算法的运行时间T(n)建立的依据

1.5.6算法所占用的空间S(n)建立的依据

1.6递推方程求解方法

1.6.1迭代法

1.6.2递归树

1.6.3差消法

1.6.4主方法

第2章贪心算法——贪心不足

2.1概述

2.1.1贪心算法的本质

2.1.2贪心算法的基本要素

2.2活动安排问题

2.2.1问题分析——贪心策略

2.2.2算法设计

2.2.3实例构造

2.2.4算法分析

2.2.5Python实战

2.3单源最短路径问题

2.3.1问题分析——贪心策略

2.3.2算法设计

2.3.3实例构造

2.3.4算法分析

2.3.5Python实战

2.4哈夫曼编码

2.4.1问题分析——贪心策略

2.4.2算法设计

2.4.3实例构造

2.4.4算法分析

2.4.5Python实战

2.5最小生成树——Prim算法

2.5.1问题分析——贪心策略

2.5.2算法设计

2.5.3实例构造

2.5.4算法分析

2.5.5Python实战

2.6最小生成树——Kruskal算法

2.6.1问题分析——贪心策略

2.6.2算法设计

2.6.3实例构造

2.6.4算法分析

2.6.5Python实战

2.7背包问题

2.7.1问题分析——贪心策略

2.7.2算法设计

2.7.3实例构造

2.7.4算法分析

2.7.5Python实战

第3章分治算法——分而治之

3.1概述

3.1.1分治算法的本质

3.1.2分治算法的求解步骤

3.2二分查找

3.2.1问题分析——分与治的方法

3.2.2算法设计

3.2.3实例构造

3.2.4算法分析

3.2.5Python实战

3.3选第二大元素

3.3.1问题分析——分与治的方法

3.3.2算法设计

3.3.3实例构造

3.3.4算法分析

3.3.5Python实战

3.4循环赛日程表

3.4.1问题分析——分与治的方法

3.4.2算法设计

3.4.3实例构造

3.4.4算法分析

3.4.5Python实战

3.5合并排序

3.5.1问题分析——分与治的方法

3.5.2算法设计

3.5.3实例构造

3.5.4算法分析

3.5.5Python实战

3.6快速排序

3.6.1问题分析——分与治的方法

3.6.2算法设计

3.6.3实例构造

3.6.4算法分析

3.6.5Python实战

3.7线性时间选择——找第k小问题

3.7.1问题分析——分与治的方法

3.7.2算法设计

3.7.3实例构造

3.7.4算法分析

3.7.5Python实战

第4章动态规划

4.1概述

4.1.1动态规划的基本思想

4.1.2动态规划的求解步骤

4.1.3动态规划的基本要素

4.2矩阵连乘问题

4.2.1问题分析——递归关系

4.2.2算法设计

4.2.3实例构造

4.2.4算法分析

4.2.5Python实战

4.3凸多边形最优三角剖分

4.3.1问题分析——递归关系

4.3.2算法设计

4.3.3实例构造

4.3.4算法分析

4.3.5Python实战

4.4最长公共子序列问题

4.4.1问题分析——递归关系

4.4.2算法设计

4.4.3实例构造

4.4.4算法分析

4.4.5Python实战

4.5加工顺序问题

4.5.1问题分析——递归关系

4.5.2算法设计

4.5.3实例构造

4.5.4算法分析

4.5.5Python实战

4.601背包问题

4.6.1问题分析——递归关系

4.6.2算法设计

4.6.3实例构造

4.6.4算法分析

4.6.5算法的改进

4.6.6Python实战

4.7最优二叉查找树

4.7.1问题分析——递归关系

4.7.2算法设计

4.7.3实例构造

4.7.4算法分析

4.7.5Python实战

第5章回溯法——深度优先搜索

5.1概述

5.2典型的解空间结构

5.2.1子集树

5.2.2排列树

5.2.3满m叉树

5.301背包问题——子集树

5.3.1问题分析——解空间及搜索条件

5.3.2算法设计

5.3.3实例构造

5.3.4算法的改进

5.3.5算法分析

5.3.6Python实战

5.4最大团问题——子集树

5.4.1问题分析——解空间及搜索条件

5.4.2算法设计

5.4.3实例构造

5.4.4算法分析

5.4.5Python实战

5.5批处理作业调度问题——排列树

5.5.1问题分析——解空间及搜索条件

5.5.2算法设计

5.5.3实例构造

5.5.4算法分析

5.5.5Python实战

5.6旅行商问题——排列树

5.6.1问题分析——解空间及搜索条件

5.6.2算法设计

5.6.3实例构造

5.6.4算法分析

5.6.5Python实战

5.7图的m着色问题——满m叉树

5.7.1问题分析——解空间及搜索条件

5.7.2算法设计

5.7.3实例构造

5.7.4算法分析

5.7.5Python实战

5.8最小质量机器设计问题——满m叉树

5.8.1问题分析——解空间及搜索条件

5.8.2算法设计

5.8.3实例构造

5.8.4算法分析

5.8.5Python实战

第6章分支限界法——宽度优先或最小耗费(最大效益)优先搜索

6.1分支限界法的基本思想

6.201背包问题

6.3旅行商问题

6.4布线问题

6.4.1问题分析——解空间及搜索条件

6.4.2算法设计

6.4.3实例构造

6.4.4算法分析

6.4.5Python实战

6.5分支限界法与回溯法的比较

第7章线性规划问题与网络流

7.1线性规划问题

7.1.1一般线性规划问题的描述

7.1.2标准型线性规划问题的描述

7.1.3标准型线性规划问题的单纯形算法

7.2最大网络流

7.2.1基本概念

7.2.2增广路算法

7.2.3最大网络流的变换与应用

7.3最小费用最大流

7.3.1基本概念

7.3.2消圈算法

7.3.3最小费用最大流的变换与应用

第8章随机化算法

8.1概述

8.1.1随机化算法的类型及特点

8.1.2随机数发生器

8.2数值随机化算法

8.2.1计算π的值

8.2.2计算定积分

8.3蒙特卡罗算法

8.3.1主元素问题

8.3.2素数测试

8.4拉斯维加斯算法

8.4.1整数因子分解

8.4.2n皇后问题

8.5舍伍德算法

8.5.1随机快速排序

8.5.2线性时间选择

第9章NP完全理论

9.1易解问题和难解问题

9.2P类和NP类问题

9.2.1P类问题

9.2.2NP类问题

9.2.3P类问题和NP类问题的关系

9.3NP完全问题

9.3.1多项式变换技术

9.3.2典型的NP完全问题

9.4NP完全问题的近似算法

9.4.1顶点覆盖问题

9.4.2装箱问题

9.4.3旅行商问题TSP

9.4.4集合覆盖问题

参考文献

（1） 实例丰富、通俗易懂。针对每一种算法设计策略，通过实例图解算法运行过程，形象直观、通俗易懂。

　　（2） 完整的实战演练，易于上机操作。针对每个经典问题，在算法设计、实例构造的基础上，提供完整Python代码，学习者可以体验从理论到实践的快感。

　　（3） 注重算法实践。针对主要算法概念及算法设计策略，精心设计实践内容，便于学习者巩固算法设计与分析的方法。

　　（4） 网络资源丰富，便于教学、自学。网络资源包括本书所有Python源代码、习题解析、微视频、微课件、随堂测试等丰富的学习资源。

　　为便于教与学，本书配有微课视频、源代码、题库、教学课件、教学大纲、考试试卷、教学进度表、实验指导书等。

　　本书面向计算机科学与技术、软件工程、智能科学、数据科学与大数据等计算机类相关专业的教师、学生及广大科研工作者，计算机类算法相关工作的从业人员。

本书内容精炼、注释详尽、案例和配套资源丰富，图解详细，让读者体验一站式的算法乐趣。