前言
党的二十大报告指出,教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力,深入实施科教兴国战略、人才强国战略、创新驱动发展战略,开辟发展新领域新赛道,不断塑造发展新动能新优势。
用计算机求解问题是将特定问题的求解过程转换为计算机可以执行的程序。能够设计好的程序是计算机专业学生的基本功。在计算机教学体系中涉及编程的主要课程有“高级程序设计语言”“数据结构”“算法设计与分析”。这些课程相互承接,程序设计语言是求解问题的工具,数据结构是求解问题的基础,算法设计是求解问题的关键。
“算法设计与分析”课程是计算机科学与技术等专业的专业必修课,课程目的是通过学习、理解并掌握算法设计的主要策略和算法复杂性分析的方法,能熟练运用各种数据结构和常用算法策略设计高效算法,培养学生分析问题和解决复杂工程问题的能力,为学生进一步学习后续课程奠定良好的基础。
本书是编者长期从事“数据结构”“算法设计与分析”课程本科生和研究生教学的经验总结,凝聚了编者的教学体会和理念。
1. 本书内容
全书由9章构成,各章内容如下。
第1章为概论,介绍算法的概念、算法描述方法、算法设计步骤和算法时空分析方法。
第2章为常用数据结构及其应用,结合STL介绍线性表、字符串、栈、队列、双端队列、树、二叉树、二叉排序树、平衡二叉树、优先队列、并查集、图和哈希表等数据结构的原理和应用,讨论如何针对求解问题设计好的数据结构。
第3章为基本算法设计方法,介绍穷举法、归纳法、迭代法和递归法等常用的算法设计方法,讨论递推式计算等基本算法分析方法。
第4章为分治法,介绍分治法的原理和框架,讨论利用分治法求解排序问题、查找问题、组合问题、求xn和An问题,包括求最大连续子序列和、字符串匹配、楼梯问题、求幂集和求全排列等典型算法。
第5章为回溯法,介绍解空间概念和回溯法框架,根据解空间的类型分别讨论基于子集树框架的问题求解方法和基于排列树框架的问题求解方法,包括子集和问题、简单装载问题、0/1背包问题、n皇后问题、任务分配问题、出栈序列、图的m着色和货郎担问题等典型算法。
第6章为分支限界法,介绍分支限界法的要点和框架,讨论广度优先搜索、队列式分支限界法和优先队列式分支限界法,包括图的单源最短路径、0/1背包问题、任务分配问题和货郎担问题等典型算法。
第7章为贪心法,介绍贪心法的策略和要点,讨论采用贪心法求解组合问题、图问题、调度问题和哈夫曼编码,包括活动安排问题Ⅰ、Prim、Kruskal、Dijkstra和不带/带惩罚的调度问题等典型算法。
第8章为动态规划,介绍动态规划的原理和要点,讨论一维动态规划、二维动态规划、三维动态规划、字符串动态规划、背包动态规划、树形动态规划和区间动态规划算法设计方法,包括最大连续子序列和、最长递增子序列、活动安排问题Ⅱ、三角形最小路径和、Floyd算法、双机调度、最长公共子序列、编辑距离、0/1背包问题、完全背包问题和多重背包问题等典型算法。
第9章为NP完全问题,介绍P类、NP类和NP完全问题。
书中带“*”号的部分作为选学内容。
2. 本书特色
本书具有如下鲜明特色:
(1) 由浅入深,循序渐进。每种算法策略从设计思想、算法框架入手,由易到难地讲解经典问题的求解过程,使读者既能学到求解问题的方法,又能通过对算法策略的反复应用掌握其核心原理,以收到融会贯通之效。
(2) 示例丰富,重视启发。书中列举大量的具有典型性的求解问题,深入剖析采用相关算法策略求解的思路,展示算法设计的清晰过程,并举一反三,激发学生学习算法设计的兴趣。
(3) 注重求解问题的多维性。同一个问题采用多种算法策略实现,例如任务分配问题采用基于子集树框架和排列树框架以及分支限界法求解,0/1背包问题采用回溯法、分支限界法和动态规划求解等。通过不同算法策略的比较,使学生更容易体会到每种算法策略的设计特点和各自的优缺点,以提高算法设计的效率。
(4) 强调实践和动手能力的培养。书中以实战形式讨论了部分在线编程题的设计过程,包括求解问题的相关知识点、完整可通过的程序代码和提交结果,这些实战题来自力扣中国、北京大学POJ和杭州电子科技大学HDU网站,让学生体会到“学以致用”和解决实际问题的乐趣。
(5) 本书配套有《算法设计与分析基础(C++版)学习和实验指导》(李春葆等,清华大学出版社),涵盖所有练习题、上机实验题和在线编程题的参考答案。
3. 教学资源
为了方便教师教学和学生学习,本书提供了全面而丰富的教学资源,内容如下。
(1) “算法设计与分析”课程教学大纲(含课程思政)和电子教案: 包含教学目的、课程内容和学时分配(42学时),以及各章的课程思政要点和每个课时的教学内容安排。
(2) 教学PPT: 提供全部教学内容的精美PPT课件(947页),供任课教师在教学中使用。
(3) 源程序代码: 所有源程序代码按章组织,例如ch3文件夹存放第3章的源程序代码,其中perm.cpp为求全排列的源程序代码,Example\\exam33.cpp为例33的源程序代码,HDU1274.cpp为实战题HDU1274的源程序代码。
(4) “算法设计与分析”实验课程教学大纲: 包含课程介绍、教学目的、实验基本要求与方式、实验报告、实验内容与学时分配(15~21学时),以及每个实验可供选择的单机实验题和在线编程题。
(5) 本书配套有绝大部分知识点的教学视频,视频采用微课碎片化形式组织(含96个小视频,累计超过20小时)。
资源下载提示
课件等资源: 扫描封底的“课件下载”二维码,在公众号“书圈”下载。
素材(源码)等资源: 扫描目录上方的二维码下载。
在线作业: 扫描封底的作业系统二维码,登录网站在线做题及查看答案。
视频等资源: 扫描封底的文泉云盘防盗码,再扫描书中相应章节的二维码,可以在线学习。
本书第1、3、4章由中国劳动关系学院陈良臣编写,第2章和第9章由武汉大学喻丹丹编写,第5~8章由武汉大学李春葆编写,李春葆完成全书的规划和统稿工作。本书的出版得到清华大学出版社魏江江分社长的全力支持,王冰飞老师给予精心编辑,LeetCode、POJ和HDU网站提供了无私的帮助,编者在此一并表示衷心感谢。
尽管编者不遗余力,但由于水平所限,本书仍可能存在不足之处,敬请教师和同学们批评指正。
编者
2023年4月