011146.03 2025年秋季 算法基础

教学大纲

学分 3.5 学时90 考核方式 笔试（闭卷）第一堂课 2025-9-12 最后一课 2026-1-9

教材

l  算法导论第3版Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein； 殷建平，徐云，王刚，刘晓光，苏明，邹恒明，王宏志 译机械工业出版社2013年1月

参考书

l  《Algorithm Design》影印版（中文名：算法设计）Jon Kleinberg，Eva Tardos 著， 清华大学出版社 

l  《Algorithmics—The Spirit of Computing》影印版（中文名：算法学—计算精髓） David Harel，Yishai Feldman 著，清华大学出版社 

l  《算法技术手册》，George T. Heineman，Gary Pollice，Stanley Selkow 著， 杨晨，李明 译， 机械工业出版社 

l  《The Algorithm Design Manual》影印版（中文名：算法设计手册）Steven S. Skiena 著 清华大学出版社 

l  《算法概论》 Sanjoy Dasgupta，Christos Papadimitriou，Umesh Vazirani 著 注释版： 钱枫，邹恒明　注释，机械工业出版社； 中文版： 王沛 唐扬斌 刘齐军 译，清华大学出版社

中文简介

l  在计算机科学中，算法（Algorithm）可以理解为求解问题的一个具体计算步骤。本课程主要介绍算法的基本概念，以及算法设计和分析的基本方法和技巧。课程包含了高级数据结构和算法的若干基本内容：算法分析的基本技术、排序、堆和优先队列、红黑树、平摊分析、二项堆、分离集合、分治法、动态规划、贪心法、快速富利叶变换、图论算法、串匹配等，和典型计算问题的求解算法。

英文简介

l  In the Computer Science, the Algorithm is a computational procedure (or a sequence of computational steps) for solving a computational problem (with computers). This course introduces basic concepts of algorithms, and techniques for algorithm design and analysis,. The course will discuss several topics about advanced data structure and algorithms, such as basic analysis techniques, sorting, heap and priority queues, red-block trees, amortized analysis, binomial heaps, disjoint sets，divide-and-conquer, dynamic programming, greedy algorithms, DFT and FFT, graph algorithms, string matching, and some concrete algorithms for typical computational problems that are efficiently solvable.

教学目标和基本要求（理论）

l  教学目标：本课程是高等学校计算机系各专业的基础课, 其要求是使学生了解和掌握有关算法设计和分析的基本内容, 知道设计算法的基本策略、方法和技术, 学会分析算法性能的具体方法和技巧, 为计算机应用和科学研究工作中有效求解问题, 以及为今后进一步学习打下基础。

l  基本要求：通过该课程的学习，学生能够对算法的时、空复杂性有一定的分析能力，能够针对具体的应用问题， 选择合适的数据结构并设计结构清晰、正确、有效的求解算法。

重难点

l  教学重点：算法设计的基本思想和策略, 算法性能分析的方法，算法性能优化的技巧，分析问题和利用算法设计思想、方法、策略求解问题能力的培养。

l  教学难点：算法性能的度量，算法平均性能分析的技巧，综合运用算法知识解决实际问题，将算法优化的思想贯穿到算法设计过程，以及数据结构对算法性能的影响等。 

课程章节主要内容及学时分配 （打 * 号的章节视情况选择讲或不讲）

l  第一讲：算法概念                     4 课时

n  第 1 章 算法的作用

n  第 2 章 算法入门

l  第二讲：渐近记号与递归方程           4 课时       

n  第 3 章 函数的增长   

n  第 4 章 递归方程   4.1 替代法   4.2 递归树方法   4.3 主方法

l  第三讲：基于比较的排序               5 课时

n  简单排序和 Shell排序(补充)：简单选择排序  冒泡排序  Shell排序

n  第 6 章 堆排序   

n  第 7 章 快速排序

l  第四讲：线性时间排序和次第计算       4 课时

n  第 8 章 线性时间排序

n  第 9 章 选择和顺序统计

l  第五讲：高级数据结构                 8 课时

n  第 12 章 二分检索树

n  第 13 章 红黑树

n  第 14 章 数据结构的扩张

l  第 19 章 二项堆

n  *第 20 章Fibonacci堆

n  第 21 章 分离集合数据结构

l  第六讲：算法设计基本策略             9课时

n  第 15 章 动态规划法

n  第 16 章 贪心算法   16.1 活动按排问题   16.2 贪心策略基础   16.3 Huffman编码

n  第 17 章 平摊分析

n  分治应用经典(汇集、补充)：大整数的乘法（补充）28.2 Strassen矩阵乘法   33.4 最近点对

n  第30章  多项式和FFT

l  第七讲：图论算法                     8 课时

n  第 19 章 图的基本算法

n  第 20 章 最小生成树

n  第 21 章 单源最短路径

n  第 22 章 所有点对最短路径

n  *第 23 章 最大流

l  第八讲：串匹配算法                   8 课时

n  串匹配算法概述      蛮力法   Knuth-Morris-Pratt 算法SHIFT-OR算法        Boyer-Moore 算法    Boyer-Moore-Horspool算法Quick Search 算法   Karp-Rabin算法

l  第九讲：NP完全性简介                 4 课时

n  第 34 章 NP完全性

n  第 35 章 近似算法

教学目标和基本要求（实验）

• 掌握典型算法的基本性能，对算法性能有感性认识；

• 掌握算法设计的基本策略，能设计算法求解具体的计算问题；

• 充分认识影响算法性能的主要因素，掌握提高算法性能的主要方法和技巧；

• 掌握算法实现的技巧，对底层数据结构的作用和选取有充分的了解。

实验项目及学时分配

序号	实验项目	学时
1	排序算法及性能对比	5
2	高级数据结构：红黑树、数据结构扩张、二项堆。	5
3	动态规划法：LCS、矩阵链乘、最优二分检索树。	5
4	贪心算法：区间覆盖、K进制编码、活动按排、普通背包问题。	5
5	图论算法：所有点对最短路径、强连通分量	5
6	串匹配算法-KMP、BM、KR、Quick Search	5