算法设计与分析是计算机专业的核心课程。学习该课程对学习其他专业课奠定了扎实的基础，也对培养计算思维和求解问题的能力起到重要作用。面对各个应用领域的大量实际问题，最重要的是分析问题的性质并选择正确的求解思路，即找到一个好的算法。特别是在当今复杂、海量信息的大数据处理中，一个好的算法往往起到决定性的作用。
本课程注重针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。课程主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程"算法设计与分析（高级）"中加以介绍。
课程的内容分成两大部分：算法的基础知识和通用算法设计技术与分析方法。
算法基础知识部分主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。
通用算法设计技术与分析方法部分主要介绍分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术。重点介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。
本课程从算法复杂性分析的基本方法和原理入手，以讲授算法设计的基本方法和原理、算法优化的基本方法和技巧为主，通过典型的问题及其相应的求解算法，以及算法复杂性的分析，达到完善学生的知识体系、培养学生的分析能力、拓展学生的思维方法，并鼓励学生把理论与实践相结合。
第一周 基础知识（1）：算法的基本概念及伪码描述，函数的渐近的界
1.1 本周教学内容简介
1.2 算法设计的两个例子
1.3 问题的计算复杂度：排序问题
1.4 货郎问题与计算复杂性
1.5 算法及其时间复杂度
1.6 算法的伪码表示
1.7 函数的渐近的界
1.8 有关函数渐近的界的定理
1.9 几类重要函数
作业测验
第二周 基础知识（2）：序列求和方法，递推方程求解
2.1 本周教学内容简介
2.2 序列求和的方法
2.3 递推方程与算法分析
2.4 迭代法求解递推方程
2.5 差消法化简递推方程
2.6 递归树
2.7 主定理及其证明
2.8 主定理的应用
作业测验
第三周 分治策略（1）
3.1 本周教学内容简介
3.2 分治策略的设计思想
3.3 分治策略的一般描述和分析方法
3.4 芯片测试
3.5 快速排序
3.6 幂乘算法及应用
3.7 改进分治算法的途径1：减少子问题数
3.8 改进分治算法的途径2：增加预处理
作业测验
第四周 分治策略（2）
4.1 本周内容简介
4.2 选最大与最小
4.3 选第二大
4.4 一般选择问题的算法设计
4.5.选择问题的算法分析
4.6 卷积及应用
4.7 卷积计算
4.8 快速傅立叶变换FFT算法
4.9 平面点集的凸包
作业测验
第五周 动态规划（1）
5.1 本周教学内容简介
5.2 动态规划算法的例子
5.3 动态规划算法设计
5.4 动态规划算法的递归实现
5.5 动态规划算法的迭代实现
5.6 投资问题
5.7 背包问题
5.8 最长公共子序列
作业测验
第六周 动态规划（2）
6.1 本周教学内容简介
6.2 图像压缩
6.3 最大子段和
6.4 最优二叉检索树的概念
6.5 最优二叉检索树的算法
6.6 RNA二级结构预测
6.7 序列比对
作业测验
第七周 贪心法（1）
7.1 本周教学内容简介
7.2 贪心法的例子
7.3 贪心法的正确性证明
7.4 最优装载问题
7.5 最小延迟调度
7.6 得不到最优解的处理方法
作业测验
第八周 贪心法（2）
8.1 本周教学内容简介
8.2 最优前缀码及哈夫曼算法
8.3 哈夫曼算法的正确性证明
8.4 最小生成树
8.5 Prim算法
8.6 Kruskal算法
8.7 单源最短路径问题及算法
8.8 Dijkstra算法的证明
单元作业
第九周 回溯与分支限界（1）
9.1 本周教学内容简介
9.2 几个回溯算法的例子
9.3 回溯算法的设计思想和适用条件
9.4 回溯算法实现及实例
9.5 图的着色
9.6 搜索树结点数的估计
作业测试
第十周 回溯与分支限界
10.1 本周教学内容简介
10.2 分支限界
10.3 最大团问题
10.4 货郎问题
10.5 圆排列问题
10.6 连续邮资问题
10.7 课程总结
作业测试
程序设计基础、数据结构与算法、高等数学、高等代数
为积极响应国家低碳环保政策， 2021年秋季学期开始，中国大学MOOC平台将取消纸质版的认证证书，仅提供电子版的认证证书服务，证书申请方式和流程不变。
电子版认证证书支持查询验证，可通过扫描证书上的二维码进行有效性查询，或者访问 https://www.icourse163.org/verify，通过证书编号进行查询。学生可在“个人中心-证书-查看证书”页面自行下载、打印电子版认证证书。
完成课程教学内容学习和考核，成绩达到课程考核标准的学生（每门课程的考核标准不同，详见课程内的评分标准），具备申请认证证书资格，可在证书申请开放期间（以申请页面显示的时间为准），完成在线付费申请。
认证证书申请注意事项：
1. 根据国家相关法律法规要求，认证证书申请时要求进行实名认证，请保证所提交的实名认证信息真实完整有效。
2. 完成实名认证并支付后，系统将自动生成并发送电子版认证证书。电子版认证证书生成后不支持退费。
《算法设计与分析（第2版）》 屈婉玲、刘田、张立昂、王捍贫编著 清华大学出版社
教授
副教授
副教授
由高教社联手网易推出，让每一个有提升愿望的用户能够学到中国知名高校的课程，并获得认证。
网上有害信息举报（涉未成年人）：网站 https://www.12377.cn 邮箱（涉未成年人） youdao_jubao@rd.netease.com
粤B2-20090191-26
| 京ICP备12020869号-2 |
京公网安备44010602000207
©2014-2025
浙公网安备 33010802012594号
