课程代码:16158603

《算法分析与设计》教学大纲

Analysis & Design of Algorithm

开课专业: 数据科学与大数据技术专业本科生

制定人: 尹华

审核人: 李汇熙

制定时间: 2025年5月10日

《算法分析与设计》课程教学大纲

一、课程基本信息

课程代码:16158603

课程名称:算法分析与设计

英文名称:Analysis & Design of Algorithm

课程类别:专业课

学 时:48(课堂教学36，实验教学12)

学 分:3

适用对象: 计算机科学与技术专业、数据科学与大数据技术专业本科生

考核方式:考试/考查

先修课程:C 或 JAVA语言、数据结构

二、课程简介

《算法分析与设计》是软件开发人员必修专业课，软件的效率和稳定性取决于软件中所采用的算法技术和算法思想，例如，贪心的算法技术和思想、分治的算法技术和思想、动态规划的算法技术和思想，以及分支限界算法思想、对NPC或NP-hard类难题的近似算法思想，等等；对于一般程序员和软件类专业学生，学习算法设计与分析课程，可以开阔编程思路，使得在各类软件系统的开发与设计过程中，找到相关问题的高效求解算法，从而提高程序的时间效率和空间效率。

《Analysis and Design of Algorithms》 is a compulsory specialty course for software developers. The efficiency and stability of software system depends on mainly the algorithm techniques. For example, the greedy algorithm technique, the divide and conquer algorithm technique, the dynamic programming algorithm technique and branch and bound algorithm, the approximation algorithm design for solving the NPC or NP-hard problems, etc. As coders or programmers, it is very important to learning this course, which could help them to expand their programming views, to design more efficient algorithms, to highlight the time and complexities as well.

三、课程性质与教学目的

通过对常用的、有代表性的算法的研究，让学生们理解并掌握算法设计的基本技术。培养学生掌握分析算法时间复杂度的基本方法，锻炼学生的计算机程序逻辑的思维能力和解决算法问题的创新能力。同时，使得学生们能够站在数字计算机的角度来理解现实问题的难易程度及相应的问题分类，掌握算法理论的基本要点，了解算法理论的基本框架，并使得学生们能够以辩证唯物主义告诉我们的“真理是客观的，同时又是绝对的和相对的”这样的思想角度，深入理解计算机科学与技术专业中的NP完全理论体系；使学生具备运用算法技术和相关的知识，去解决系统开发过程中的实际问题，从而培养学生的独立科研的能力和理论联系实践的能力。

课程目标1:能够运用数学工具（渐进符号、递归方程等）分析算法的时间复杂度和空间复杂度，建立算法性能的量化评价模型。

观测点:

运用渐进符号（O、Ω、Θ）描述算法复杂度

利用主定理分析递归算法的计算效率

建立不同输入规模下算法性能的数学推导模型

支撑毕业要求:毕业要求1（工程知识）。

课程目标2:能够识别复杂工程问题的特征，通过分治、动态规划等策略分解问题，并设计对应的算法解决方案。

观测点:

识别最优子结构、重叠子问题等动态规划适用条件

设计分治法的递归框架与合并策略（如归并排序）

针对背包问题、图最短路径等案例推导状态转移方程

支撑毕业要求:毕业要求2（问题分析）、毕业要求4（研究）。

课程目标3:能够设计满足特定需求的算法解决方案，综合考虑时间效率、空间约束及工程伦理因素。

观测点:

在贪心算法中权衡局部最优与全局最优的关系

在NP难问题中设计近似算法并分析误差边界

在隐私保护（如加密算法）等场景中评估算法的社会影响

支撑毕业要求:毕业要求3（设计/开发解决方案）、毕业要求6（工程与社会）、毕业要求7（环境与可持续发展）。

课程目标4:能够使用现代工具（Python/Java编程、算法可视化平台）对算法进行仿真、测试与效率验证。

观测点:

利用编程语言实现经典算法（如动态规划、回溯法）

使用性能分析工具（如PyCharm Profiler）验证算法复杂度

通过LeetCode等平台完成算法优化实战

支撑毕业要求:毕业要求5（使用现代工具）、毕业要求11（项目管理）。

课程目标5:能够在团队协作中承担算法设计与实现任务，并通过文档、报告等形式清晰表达技术方案。

观测点:

撰写算法设计文档（如伪代码、流程图）

在团队项目中分工完成模块设计与集成测试

通过答辩展示算法优化策略与实验结果

支撑毕业要求:毕业要求9（个人和团队）、毕业要求10（沟通）。

课程目标6:能够自主学习新兴算法技术（如量子算法、AI优化算法），并评估其适用性与局限性。

观测点:

对比经典算法与新兴算法（如传统排序 vs. 神经网络排序）

分析算法在大数据、分布式场景中的扩展性瓶颈

通过文献研究提出改进方案（如并行化改造）

支撑毕业要求:毕业要求8（职业规范）、毕业要求12（终身学习）。

表1 课程目标对毕业要求的支撑

四、教学内容及要求

第一章 算法引论

(一) 目的与要求

1. 掌握算法、算法复杂度等的基本概念；
2. 掌握时间复杂度的递进主要层次。

(二) 教学内容

1. 算法与程序
   1. 主要内容

算法特征、算法与程序的区别

• 1. 基本概念和知识点

算法的定义、算法的五大特征

程序+数据结构+算法=编程

• 1. 问题与应用

思考:只要是计算机程序，便是算法的实现吗?

1. 算法描述
   1. 主要内容

算法的表示与规范化描述方法

• 1. 基本概念和知识点

Seduocode，算法描述的基本格式

• 1. 问题与应用

思考:算法描述到什么程度，其描述粒度便是合适的?

1. 算法复杂性分析
   1. 主要内容

算法的时间复杂性、空间复杂性，渐进表达式

• 1. 基本概念和知识点

算法的时间复杂性、空间复杂性，渐进表达式

• 1. 问题与应用

掌握算法复杂度的基本概念及时间复杂度的估算方法。

函数的渐进表达式。

在算法复杂性分析的教学中，要重点介绍时间复杂性从O(1)逐渐演化到O(2^n)，也即“从易到难”的过程，并引出对“一分为二，这是个普遍的现象，这就是辩证法。”（《毛泽东选集》第5卷第498页）这个哲学思想在计算机算法设计中的体现、在算法时间复杂性研究和讨论中的体现。

(三) 思考与实践

思考:时间复杂度的主要数学表达式，是否能与现实生活中的解决问题的手法相对应或相类似呢?

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

第二章 递归与分治策略

（一）目的与要求

1. 掌握递归的概念，学会用递归方法解决实际问题；
2. 熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。

（二）教学内容

1. 递归的概念
2. 主要内容

递归概念，递归的程序实现，分治法思想和算法设计技术

1. 基本概念和知识点

递归思想，分而治之的技术和思想方法

1. 问题与应用

从易到难举例:指数算法、阶乘算法；Hanoi问题

1. 分治法的基本思想
   • 1. 主要内容

分治法基本思想、子问题与子问题相互独立性

• • 1. 基本概念和知识点

分治思想及其应用

• • 1. 问题与应用

二分搜索技术，大整数乘法，棋盘覆盖问题

1. 应用实例
   • 1. 主要内容

矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择

• • 1. 基本概念和知识点

各类应用实例的分治思维方法

• • 1. 问题与应用

掌握递归的概念，学会用递归方法解决实际问题，熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。

算法设计:CHESS COVERING问题、子段和问题

(三) 思考与实践

思考:是否可以把分治法思想看成是“一分为二”的哲学思想在计算机算法设计中的一个应用?

实践:CHESS COVERING问题以及子段和问题的算法设计与实现

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

第三章 动态规划

（一）目的与要求

1．熟练掌握利用动态规划方法解决问题的基本思想；

2．学会如何将问题化为子问题的方法；

3．能对具体问题写出正确的递推公式。

（二）教学内容

1. 动态规划算法的基本要素
2. 主要内容

动态规划的基本要素、动态规划思想、动态规划算法步骤

1. 基本概念和知识点

动态规划思想、最优子结构性质、子问题重叠性质、动态规划算法的时间复杂性分析

1. 问题与应用

思考:动态规划与分治法思想的区别与比较

通过对动态规划和分治法思想这两种算法思想的比较，从算法效率的角度，引出“科学是第一生产力”这个重要论断！并从生产力的“劳动者、劳动工具和劳动对象”这三大要素中，把计算机这个劳动工具进一步理解到算法层面。

1. 最长公共子序列
2. 主要内容

LCS问题的定义、LCS问题的DP求解思路

1. 基本概念和知识点

LCS、自底向上的编程思维、算法时间复杂性分析

1. 问题与应用

串的各种运算及其比较

1. 矩阵连乘问题
2. 主要内容

矩阵连乘问题

1. 基本概念和知识点

矩阵连乘、算法时间复杂性分析

1. 问题与应用

矩阵连乘问题的算法设计

1. 其他应用
2. 主要内容

最大子段和，凸多边形最优三角剖分，图像压缩，电路布线，流水作业调度，0-1背包问题

1. 基本概念和知识点

各类问题的定义、DP思想的递推方程

1. 问题与应用

如何设计能够应用DP算法的递推方程?

(三) 思考与实践

思考:解决问题的方法中，往往是“由简入繁”，那么，你能够从这个角度来思考“动态规划”算法思想的技术特点吗?

实践:Triangle problem 以及LCS problem的算法设计与实现

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

第四章 贪心算法

(一) 目的与要求

1．掌握利用贪心算法解决问题的基本思想；

2．会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。

(二) 教学内容

1. 贪心算法的基本要素
2. 主要内容

贪心选择性质、最优子结构性质

1. 基本概念和知识点

贪心选择、最优子结构、算法时间复杂性分析

1. 问题与应用

贪心算法与动态规划算法的差异

1. 单源最短路径
2. 主要内容

算法基本思想、算法的正确性和计算复杂性

1. 基本概念和知识点

单源最短路径、算法时间复杂性分析

1. 问题与应用

单源最短路径的程序实现

1. 其他应用
2. 主要内容

活动安排问题，最优装载，多机调度。

1. 基本概念和知识点

问题的描述与理解

1. 问题与应用

实现以上各类问题的程序、分析各类问题的算法时间复杂性

贪心算法在问题具有什么特征下，才是正确的?

(三) 思考与实践

思考:应当说，能够应用贪心算法求解的问题，一般都比较简单。那么，对于比较难的问题，贪心算法有没有应用的价值了呢?

实践:活动安排问题的算法设计与实现。

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

第五章 回溯法

(一) 目的与要求

1．掌握利用回溯法解决问题的基本思想；

2．会用回溯法解决:n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。

(二) 教学内容

1. 回溯法思想
2. 主要内容

回溯法的算法思想及其框架

1. 基本概念和知识点

回溯法、回溯法的算法思想及其框架

1. 问题与应用

思考旅行售货员问题的回溯法求解思路。

1. 回溯法应用
2. 主要内容

n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，连续邮资问题，电路板排列问题。

1. 基本概念和知识点

各类问题的理解、回溯法思想的应用

1. 问题与应用

掌握利用回溯法解决问题的基本思想。

(三) 思考与实践

思考:回溯法思想，能否应用于求解AI中的问题?为什么?

实践:8后问题的算法设计与实现。

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

第六章 分支限界法

(一) 目的与要求

1. 掌握利用分支限界法解决问题的基本思想；

2. 能用多种不同方法解法同一问题，并分析各方法的效率。

(二) 教学内容

1. 分支限界法的算法思想
2. 主要内容

分支限界法的算法思想、解决问题的算法时间复杂性特征

1. 基本概念和知识点

分支限界法的算法思想、剪枝限界

1. 问题与应用

从时间复杂性来说，一般是什么类型的问题需要用分支限界法?

分支限界法与回溯法的异同?

1. 0-1背包问题
2. 主要内容

0-1背包问题的理解、用分支限界法求解

1. 基本概念和知识点

0-1背包问题、背包问题

1. 问题与应用

0-1背包问题与背包问题的异同点?两个问题的时间复杂性分析?

1. 其他应用
2. 主要内容

单源最短路径，布线问题，批处理作业调度问题。

1. 基本概念和知识点

各类问题的定义、算法应用

1. 问题与应用

用多种方法求解

(三) 思考与实践

思考:分支限界法与回溯法，其算法思想有什么异同之处?

实践: 0-1背包问题的分支限界法算法设计与实现。

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

第七章 概率算法

(一) 目的与要求

1. 基本掌握用概率来解决问题的基本思想；

2. 基本了解三种传统的概率算法的基本思想和特点。

(二) 教学内容

1. 随机数
2. 主要内容

掌握随机数、伪随机数的概念

1. 基本概念和知识点

随机数、伪随机数

1. 问题与应用

从时间复杂性来说，一般是什么类型的问题需要用算法?

1. 数值概率算法
2. 主要内容

用随机概率算法，分析设计某些数值问题的算法，如∏的计算、定积分的计算等等。

1. 基本概念和知识点

数值类问题与离散类问题

1. 问题与应用

用数值概率算法设计求解非线性方程组。

1. 舍伍德算法
2. 主要内容

舍伍德算法的思想与特点。

1. 基本概念和知识点

理解舍伍德算法的求解思路和特点。

1. 问题与应用

应用舍伍德算法求解线性时间选择问题，并分析其优点。

1. 拉斯维加斯算法
2. 主要内容

拉斯维加斯算法的思想与特点。

1. 基本概念和知识点

理解拉斯维加斯算法的求解思路和特点。

1. 问题与应用

应用拉斯维加斯算法求解n后问题。

1. 蒙特卡罗算法
2. 主要内容

蒙特卡罗算法的思想与特点。

1. 基本概念和知识点

蒙特卡罗算法的求解思路和特点。

1. 问题与应用

应用蒙特卡罗算法求解深度搜索问题。

(三) 思考与实践

思考:概率算法得到的解，是否意味着不准确呢?

实践:概率算法广泛应用于人工智能问题的求解中。请通过INTERNET，找到一类应用问题，然后分析和总结其中所应用到的概率算法思想。

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

第八章 NP完全性理论与近似算法

(一) 目的与要求

1．了解NPC理论中的假设条件，并能够从“真理的相对性”角度，来阐述NP完全之所以能够成立的前提假设；

2．掌握P类与NP类问题的划分；

3．掌握利用近似算法解决问题的基本思想，能对其可靠性进行分。

(二) 教学内容

1. 问题分类
2. 主要内容

计算模型:确定性图灵机DTM、非确定性图灵机NDTM

问题的分类:P类与NP类问题、不可解问题

1. 基本概念和知识点

DTM与NDTM、P类与NP类问题

此内容的教学过程中，要介绍一下计算机之父A.M.Turing，及等价于计算机界的NOBEL奖地位的“图灵奖”得主中，姚期智教授，由于在计算理论包括伪随机数生成、密码学与通信复杂度等的突出贡献，美国计算机协会（ACM）把2000年度的图灵奖授予他。姚期智教授是图灵奖创立以来首位获奖的亚裔学者。姚期智教授放弃了自己在美国优厚的工作待遇，甚至是不惜变卖自己在美国的房产回国，充分展现了中华学子的爱国情怀！同时强调:姚期智教授在计算理论中所做出的突出贡献，充实和完善了NP完全理论的知识体系。

1. 问题与知识要点

问题及其分类，问题的难度与时间复杂性关系、NP类问题的证明

1. NPC问题与NP-hard问题
2. 主要内容

NP完全问题的定义、NP完全问题的证明，COOK定理

NP完全理论，是计算机科学与技术专业的理论，专业的大厦总是建立在理论成立的前提下的。从NP完全理论的定义讲解中，让学生明白:任何一个理论，必然基于至少一个的理论假设:而NP完全理论之所以成立，是在针对P类问题是否属于NP类问题这个七大千禧年难题之一，假设NP≠P的！ 通过NP完全理论的教学，可使得学生们对真理观有一个实际的感悟，即:“绝对真理是由发展中的相对真理的总和构成；相对真理是不依赖于人类而存在的客体的相对正确的反映；这些反映日趋正确；每一科学真理尽管有相对性，其中都含有绝对真理的成分。”

1. 基本概念和知识点

NPC、COOK定理、常见的NPC问题

1. 问题与应用

团问题、VC问题、SAT问题、IS问题的NPC证明

了解NP完全性问题，掌握P类与NP类问题的划分。

1. 近似算法
2. 主要内容

近似算法的基本思想及性能。

1. 基本概念和知识点

近似算法的基本思想、近似算法的性能评估、分析何类问题须用近似算法求解。

1. 问题与应用

顶点覆盖问题的近似算法，集合覆盖问题的近似算法，HAMILTON问题的近似算法。

掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。

(三) 思考与实践

思考:对于NPC类的问题，我们有什么的算法思考，从而得到这类问题的可行解?

实践:最小VC问题的近似算法设计与实现。

(四) 教学方法与手段

课堂讲授为主，多媒体教学，结合课堂讨论。

五、各教学环节学时分配

六、课程考核

（一）考核方式:考试/考查

（二）成绩构成

平时成绩占比:40% 期末考试占比:60%

（三）成绩考核标准

1.考核方式评价标准

填写说明:考核方式一栏填写具体的平时成绩评价项目，如作业、讨论、考试等。

1. 课程目标评价标准

填写说明:

1. 评价标准是对具体考核内容制定的不同观测点，不要混淆为评分细则。

课程目标评价标准中的课程目标与上述课程目标中的各目标点相对应。

七、推荐教材和教学参考资源

（1）推荐教材:《算法设计与分析》，王晓东，(第3版)，清华大学出版社，2018-08

（2）经典书目:《算法导论》，科曼(美) 著，机械工业出版社，2009-12-01

（3）参 考 书:

[1] 《计算机程序设计技巧》，D．E．Knuth著，管纪文译，国防工业出版社，1982

[2] 《计算机算法导引》，卢开澄，清华大学出版社，2000。

[3] 《算法艺术与信息学竞赛》，刘汝佳，黄亮 著，清华大学出版社，2004-01

八、其他说明

课后实验学时: 12

大纲修订人:冯俊健 尹华 修订日期:2025/05/11

大纲审定人:李汇熙 审定日期:2025/05/11