前言 算法是计算机科学的灵魂，图灵奖（A.M Turing Award）的获得者，算法大师高德纳（Donald E.Knuth）说过： “计算机科学的研究就是算法的研究。”的确，计算机科学的每个领域——不管是软件、硬件，还是具体的应用，如集成电路的设计、操作系统的内存调度、计算机网络中的路由问题等——与算法密不可分。某个领域关键算法的改进直接关系到该领域的突破和进展。迄今为止，在72位图灵奖获得者中，因算法方面的贡献而获奖的就有40多位，可见算法的研究对推动计算机科学的发展起着至关重要的作用。 在厦门大学“算法设计与分析”课程的教学过程中，作者曾选用《算法导论》（Introduction to algorithms）和《算法设计技巧与分析》（Algorithms design techniques and analysis）这两本经典且权威的英文教材作为该课程的教材。在此基础上，作者还吸取了其他算法类教材的优点，最终确定本书的内容和风格。本书将目前计算机科学领域出现的一些经典及新颖的算法设计和分析技术合理地组织起来，并进行全面介绍，旨在帮助读者掌握基本的算法理论知识，提高解决和分析问题的能力，进而使读者对实际问题能够设计出简单有效的算法。 本书的主要内容如下。 第1章从问题入手，介绍了算法的基本概念及性质，计算模型的概念，以及算法时间复杂度的分析方法及算法正确性的证明方法。本章还介绍了问题下界的概念，以及如何衡量算法的效率，以便读者能够明白： 算法能否继续改进，何时才能达到最优。 第2章介绍了算法复杂度分析所需要用到的渐近符号及其含义。 第3章介绍了算法分析方法中常用的概率分析、分摊分析和实验分析方法。 第4章介绍了递归算法的设计及其证明方法，以及递归算法时间复杂度的求解方法。 第5章介绍了分治算法及其在排序、大整数乘法、矩阵乘法、残缺棋盘和快速傅里叶变换问题中的应用。 第6章介绍了动态规划算法的基本过程及性质，动态规划算法在装配线调度问题、矩阵链乘法问题、最长公共子序列问题、0/1背包问题、最优二叉搜索树问题中的应用。其中，最优子结构性质是能够用动态规划算法求解问题的必要条件，重叠子问题是提高动态规划算法效率的关键。 第7章通过活动选择问题引入贪心算法，介绍了贪心算法的过程，以及贪心选择性质的分析方法及证明，贪心算法在背包问题、哈夫曼编码问题、缓存维护问题中的应用。 第8章介绍了图算法的基本知识，重点强调了分摊分析在图算法时间复杂度分析中的应用及图算法正确性的证明方法，它们是网络流和匹配算法的基础。本章还进一步介绍了贪心算法和动态规划算法的应用。 第9章是图算法的扩展，介绍了网络流的最大流问题、最小费用流问题及匹配问题的求解算法。 第10章介绍了计算机、经济及管理领域中经常用到的线性规划问题，并介绍了这些问题的单纯型求解算法。 第11章介绍了NP完全理论，具体介绍了P、NP和NPC的定义及其分类，以及NP完全问题的证明方法。 第12章介绍了求解NP困难问题（NPhard problem）的回溯算法。通过回溯算法在装载问题、0/1背包问题、着色问题、n皇后问题、旅行商问题、流水作业调度问题、零件切割问题中的应用，介绍约束函数、限界函数的设计思路和方法，分析了提高回溯算法效率的关键因素。 第13章介绍了基于宽度优先，同时吸取了回溯算法优点的分支限界算法，特别介绍了两种分支限界算法在不同问题求解中的应用及剪支函数的设计。 第14章介绍了启发式搜索算法的设计，特别详细介绍了A*搜索算法和博弈搜索算法。 本书具有如下特色。 (1) 本书基本上涵盖了常用算法设计的主要内容。 (2) 算法的正确性是软件可靠性的保证，本书为不同类型的算法提供了算法正确性的证明思路。目前，已出版的大多数算法书是没有这部分内容的。 (3) 本书精选了大量的习题，使读者可以有选择性地练习。同时，精选了一些实际的工程项目作为实验题。书中的一些算法实现，读者可以访问算法课程实验网站进行练习。 (4) 本书不仅注重算法的应用设计，而且注重算法时间复杂度的分析。书中大部分算法都提供了具体案例，并进行了详尽分析，使读者加深对算法的理解。 (5) 本书还提供英文课件，便于双语教学。 特别感谢厦门大学现代教育技术与实践训练中心的罗淀老师，她对本书的文字和体例进行了校对，并建议不要写得太复杂，这奠定了本书的风格。没有她的帮助，本书不可能顺利出版。本书还作为中国大学MOOC（慕课）“算法设计与分析”课程的配套教材，我的同事林文水和卢杨两位老师也为慕课课程的建设付出了很多努力。 此外，本书的完成还受到“厦门大学第二批双语教学项目”“算法设计与分析课程”“厦门大学优秀教材出版项目”“福建省一流本科建设项目”“中国大学MOOC项目”的支持。 限于我们的水平和经验，书中难免有不妥之处，还望广大读者指正，在此先表感谢！ 谨以此书献给所有关心、鼓励和帮助过我们的人们。 编者 厦门大学计算机科学与技术系 2023年12月10日

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

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

版权图片链接