前言 党的二十大报告中指出：教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，这三大战略共同服务于创新型国家的建设。高等教育与经济社会发展紧密相连，对促进就业创业、助力经济社会发展、增进人民福祉具有重要意义。 用计算机求解问题是将特定问题的求解过程转换为计算机可以执行的程序，能够设计好的程序是计算机专业学生的基本功。在计算机教学体系中编程类的主要课程有“高级程序设计语言”“数据结构”“算法设计与分析”等，这些课程相互承接，程序设计语言是求解问题的工具，数据结构是求解问题的基础，算法设计是求解问题的关键。 “算法设计与分析”课程是计算机科学与技术等专业的必修课，旨在通过学习理解掌握算法设计的主要策略和算法复杂性分析的方法，并能熟练运用各种数据结构和常用算法策略设计高效算法，培养学生分析问题和解决复杂工程问题的能力，为学生进一步学习后续课程奠定良好的基础。本书是编者长期从事“数据结构”与“算法设计与分析”课程本科生和研究生教学中的经验总结，凝聚了编者的教学体会和理念。 1. 本书内容全书由9章构成，各章内容如下。 第1章算法入门——概论： 介绍算法的概念、算法描述方法、算法设计步骤和算法时空分析方法。 第2章工之利器——常用数据结构及其应用： 结合Java中的各种集合介绍线性表、字符串、栈、队列、双端队列、优先队列、树和二叉树、图、并查集、二叉排序树和平衡二叉树、哈希表等数据结构的原理和应用。 第3章必备技能——基本算法设计方法： 介绍穷举法、归纳法、迭代法和递归法等常用的算法设计方法，讨论递推式计算等基本算法分析方法。 第4章分而治之——分治法： 介绍分治法的原理和框架，讨论利用分治法求解排序问题、查找问题和组合问题等，包括快速排序、二路归并排序、二分查找、假币问题、最大连续子序列和、多数元素和最近点对距离等典型算法。 第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） 强调实践和动手能力的培养。书中针对相关知识点以实战题形式讨论了LeetCode（力扣）网站部分在线编程题的设计思路和解决过程，让学生体会“学以致用”和解决实际问题的乐趣。实战题按难度分为3个级别，即★、★★和★★★，分别对应简单、中等和困难。 （5） 本书配套有《算法设计与分析基础（Java版）学习与上机实验指导》（李春葆等，清华大学出版社，2023），涵盖所有练习题、上机实验题和在线编程题的参考答案。 3. 教学资源为了方便教师教学和学生学习，本书提供全面而丰富的教学资源，包括的内容如下。 （1） 教学PPT： 提供全部教学内容的精美PPT课件，供任课教师在教学中使用。 （2） 源程序代码： 所有源代码按章组织，例如ch3文件夹存放第3章的源代码，其中perm.java为求全排列的源代码。 （3） 算法设计与分析课程教学大纲和电子教案： 包含教学目的、课程内容和学时分配（44学时），以及各章的课程思政要点、每个课时的教学内容安排。 （4） 算法设计与分析实验课程教学大纲： 包含课程介绍、教学目的、实验基本要求与方式、实验报告、实验内容与学时分配（15～21学时），以及推荐的在线编程题题目。 （5） 微课视频： 包含99个视频，总时长18小时。 资源下载提示 素材（源码）等资源： 扫描目录上方的二维码下载。 微课视频： 扫描封底的文泉云盘防盗码，再扫描书中相应章节的视频讲解二维码，可以在线学习。 本书的出版得到武汉大学计算机学院核心课程建设项目的资助和清华大学出版社魏江江分社长的全力支持，王冰飞老师给予精心编辑，力扣网站提供了无私的帮助，编者在此一并表示衷心感谢。尽管编者不遗余力，但由于水平所限，本书仍存在不足之处，敬请教师和同学们批评指正。 编者 2023年7月

• 课件下载
• 样章下载
• 网络资源

扫描二维码
下载APP了解更多

版权图片链接