编辑推荐
党的二十大报告指出:教育、科技、人才是全面建设社会主义现代化国家的基础性、战
略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力,深入实施科教
兴国战略、人才强国战略、创新驱动发展战略,这三大战略共同服务于创新型国家的建设。
高等教育与经济社会发展紧密相连,对促进就业创业、助力经济社会发展、增进人民福祉具
有重要意义。
算法在计算机科学中扮演着重要角色,算法设计与分析课程是计算机科学与技术等相
关专业的核心必修课,其目标是培养学生分析问题和解决问题的能力,使学生掌握算法设计
的基本技巧和算法分析的基本技术,并能熟练运用常用算法设计策略解决一些较综合的问
题,为学生进一步学习后续课程奠定良好的基础。本书是依据上述课程目标并参考ACM/
IEEE计算课程体系规范 CC2020算法领域的4个绩效能力(验证理论结果、对程序设计问题
能给出解决方案、能开发出概念验证性程序和判断是否能开发出更快的解决方案)所编
写的。
1 ．本书内容
全书由12章构成,各章的内容如下:
第1章为绪论,介绍算法的概念、算法分析方法和STL在算法设计中的应用。
第2章为递归算法设计技术,介绍递归的概念、递归模型、递归算法设计方法和递归的 经典应用示例,包括直接插入排序、0/1背包问题和求表达式值,以及递推式计算方法,包括 直接展开法、递归树方法、主方法和特征方程方法。
第3章为穷举法,介绍穷举法的特点、各种列举方法和穷举法的经典应用示例,包括求 幂集、求全排列、0/1背包问题和旅行商问题等。
第4章为分治法,介绍分治法的特点、分治法的基本步骤和分治法的经典应用示例,包 括快速排序、二路归并排序、二分查找及其扩展、求优选连续子序列和、棋盘覆盖问题、循环 日程安排问题和旅行商问题等。
第5章为回溯法,介绍解空间概念、回溯法解空间类型、子集树回溯算法框架、排列树回 溯算法框架和回溯法的经典应用示例,包括构造表达式、图着色问题、子集和问题、0/1背包 问题、接近背包问题、n 皇后问题、任务分配问题和旅行商问题等。
第6章为分支限界法,介绍广度优先搜索的特性、分支限界法的特点、分支限界法的主
要类型和分支限界法的经典应用示例,包括图的单源最短路径、0/1背包问题、任务分配问
题和旅行商问题等,以及A* 算法的原理及其应用。
第7章为动态规划,介绍动态规划的特点、动态规划求解问题应具有的性质、动态规划 的求解步骤、滚动数组的应用和动态规划的经典应用示例,包括求优选连续子序列和、最长 递增子序列、三角形最小路径和、最长公共子序列、编辑距离、0/1背包问题、接近背包问题、 扔鸡蛋问题、资源分配问题、旅行商问题、最少士兵数问题和矩阵连乘问题等。
第8章为贪心法,介绍贪心法的特点、贪心法求解问题应具有的性质和贪心法的经典应 用示例,包括区间问题、背包问题、田忌赛马问题、零钱兑换问题和哈夫曼编码,以及拟阵的 概念、带期限和惩罚的任务调度问题的求解过程。
第9章为图算法,讨论构造图最小生成树的两种算法(Prim 和Kruskal)、求图的最短路
径的4种算法(Dijkstra、Bellman-Ford、SPFA和Floyd)和网络流的相关概念,以及求优选流
的相关算法。
第10章为计算几何,介绍计算几何中常用的向量运算,以及求解凸包问题、最近点对问 题和最远点对问题的典型算法。
第11章为计算复杂性,介绍易解问题和难解问题、图灵机计算模型、P类和NP类问题 以及NP接近问题。
第12章为概率算法和近似算法,介绍这两类算法的特点和基本的算法设计方法。 书中带“*”符号的部分作为选学内容。
2 ．本书特色
本书具有如下鲜明的特色。
(1)由浅入深,循序渐进。每种算法设计策略从设计思想和算法框架入手,由易到难地 讲解相关经典问题的求解过程,使读者既能学到求解问题的方法,又能通过对算法设计策略 的反复应用掌握其核心原理,以收到融会贯通之效。
(2)示例丰富,重视启发。书中列举大量经典示例和有代表性的在线编程示例(选自 LeetCode、LintCode、POJ和 HDU),深入剖析其求解思路,展示其算法设计的清晰过程,并举 一反三,激发读者学习算法设计的兴趣。
(3)注重求解问题的多维性。同一个问题采用多种算法策略实现,例如0/1背包问题 采用递归法、穷举法、回溯法、分支限界法和动态规划求解,旅行商问题采用穷举法、分治法、 回溯法、分支限界法和动态规划求解。通过比较不同算法策略,使读者体会每种算法策略的 特点,以提高利用不同算法策略解决复杂问题的能力。
(4)强调算法实现和对动手能力的培养。算法设计仅会“纸上谈兵”是不够的,必须具
备从问题建模、算法设计、算法实现到验证的能力,书中精选了大量难度适中的在线编程实
验题,通过这些题目的训练,不仅可以提高读者的编程能力,还可以帮助读者直面各类竞赛
和求职市场。
(5)本书配套有《算法设计与分析(第3版)学习指导》和《算法设计与分析(第3版)在
线编程实验指导》(李春葆等,清华大学出版社,2024),涵盖所有练习题和在线编程题的参考
答案。
3 ．教学资源
为了方便教师教学和学生学习,本书提供了全面且丰富的教学资源,包括以下内容。
Ⅱ
(1)教学PPT:提供全部教学内容的精美PPT课件,供任课教师在教学中使用。
(2)程序源代码:所有源代码按章组织,例如ch2文件夹中存放第2章的源代码(在 DevC++ 5 11中调试通过)。
(3)教学大纲和电子教案:包含32和48课堂讲授学时的教学内容安排及相应的实验 教学内容安排,供教师参考。
(4)与各章知识点对应的题库:包括单项选择题、填空题和算法设计的上机实验题。
(5)绝大部分知识点的教学视频:视频采用微课碎片化形式组织,含170个视频,累计 超过34小时。
资源下载提示
课件等资源:扫描封底的“课件下载”二维码,在公众号“书圈”下载。 素材(源码)等资源:扫描目录上方的二维码下载。
在线自测题:扫描封底的作业系统二维码,再扫描自测题二维码在线做题。
微课视频:扫描封底的文泉云盘防盗码,再扫描书中相应章节的视频讲解二维码,可以 在线学习。
4 ．致谢
本书的编写得到教育部101计划和武汉大学计算机学院相关课程教学研究项目的大力
支持,清华大学出版社的魏江江分社长和王冰飞老师提供了全方位的帮助和精心的编辑工
作,LeetCode和相关在线编程平台给予了无私的帮助,编者在此一并表示衷心的感谢。
尽管编者不遗余力,但由于水平所限,本书仍存在疏漏和不足之处,敬请教师和同学们 批评指正。
编 者
2024年1月
Ⅲ
