函数式算法设计的艺术 [英] 理查德·伯德 [英]杰里米·吉本斯
定 价：139 元
- 作者：[英] 理查德·伯德 [英]杰里米·吉本斯
- 出版时间：2025/4/1
- ISBN：9787111775102
- 出 版 社：机械工业出版社
- 中图法分类：TP312
- 页码：
- 纸张：胶版纸
- 版次：
- 开本：16开
-
商品库位：
本书介绍了算法设计的五个主要原则:分治法、贪婪算法、稀疏、动态程序设计和穷举搜索。让学生、教师、研究人员和专业人员更好地了解一个好的算法是如何组成的，以及如何用纯函数的形式表达这些算法。
本书专门介绍了算法设计的五项主要原则：分而治之、贪心算法、减而治之、动态规划和穷举搜索。这些原则是用Haskell这种纯函数式语言来阐述的，与使用命令式语言相比，解释更简单，程序更短。书中还配有精心挑选的例子（既有新示例，也有标准示例），展示了算法之间的共性和差异。算法开发在适用的情况下使用等式推理，阐明适用性条件和正确性论证。每章最后都附有习题（共近300道），每道习题都有完整的答案，便于读者巩固理解，并将这些技术应用于一系列问题。本书适用于计算机科学与技术及软件工程相关专业学生（包括本科生和研究生）、研究人员、教师和专业人士，可以帮助他们进一步了解如何设计和实现优秀的算法，以及如何用纯函数术语来表达这些算法。
译者序
如果真有一门绝世武功，“招式”和“内功”孰轻孰重？如果说这个问题真有答案，那么在我讲授C语言程序设计多年之后，开始与本书相遇相知时似乎逐渐找到了。
长久以来，函数式编程因为侧重原理而被认为更接近于“内功”。由于某些情况下的性能问题以及学习资料的缺乏，函数式编程一直没有成为主导。近年来，计算机硬件性能的提升带来了转机，我们看到旧语言逐渐引入函数式的特性、新语言在构建之初就考虑更多函数式的设计。
在这本书里，当分而治之、贪心算法、减而治之、动态规划、穷举搜索这些算法用Haskell纯函数式语言来实现时，简短的代码体现出了科学思想与工程优雅。外化于形、内化于心的交相辉映令人沉醉！无论对于Haskell程序设计，还是对于C语言程序设计，“招式”和“内功”的兼收并蓄都是一个更高的境界！
本书的作者是牛津大学的Richard Bird和Jeremy Gibbons教授。令人遗憾的是，Richard Bird教授在2022年4月4日离开了我们，他一生致力于推广函数式编程，对算法和程序设计做出了伟大贡献。在翻译这本书的过程中，我深感他文字之魅力和思想之深邃。大家在阅读此书时产生不同编程思维碰撞的电光火石是对Richard最好的缅怀。
万琳
前言
本书的目的是使用纯函数方法来介绍算法设计的原理。我们选择的语言是Haskell，所以我们设计的所有算法都将用Haskell函数来表示。Haskell有很多结构化函数定义的特性，但是我们只会使用其中的一小部分。
使用函数代替循环和赋值语句来表达算法会改变一切。首先，以函数形式表达的算法会由其他更基本的函数组成，而这些基本函数可以被单独研究并重用在其他算法中。例如，排序算法可以通过构建并使用某种树的结构来实现，而我们可以将构建树的函数与使用树的函数分开研究。此外，可以使用简单的等式属性来捕获这些基本函数中每个函数的特性以及它们与其他函数的关系。在此基础上，人们可以用一种命令式代码不容易实现的方式来探讨和推理算法的“深度”结构。可以肯定的是，我们可以通过在谓词演算中形式化命令程序的规范并使用循环不变式来证明它们是正确的，从而对命令程序进行形式化推理。但这同时也是函数式编程的关键所在，即不能轻松地直接根据命令代码的语言来推断命令式程序的属性。因此，关于形式化程序设计的书与关于算法设计的书有很大的不同：它们要求人们精通谓词演算和必要的命令性术语。相比之下，许多关于算法设计的书通常都会对算法进行逐步介绍，并使用非形式化陈述的循环不变式来帮助人们理解为什么算法是正确的。
函数式编程使得我们不再需要考虑两种独立的语言，可以通过简单的等式推理过程愉快地计算出更好的算法版本，或算法的一部分，而这也许就是本书的主要贡献。尽管本书包含了相当多的等式推理，但我们会尽量简化以保证阅读体验。实际情况往往是，计算做起来很有趣，但大量的公式读起来会很无聊。尽管命令式算法是用C、Java还是伪代码来表示并不是很重要，但如果用函数式来表示算法，那情况就完全不同了。
本书讨论的许多问题，特别是在后面的部分中，都会从任务的规范开始，表示为标准函数的组合，如映射、过滤器和折叠，以及其他函数，如用于计算列表所有排列的perms、用于计算所有分区的parts和用于构建特定种类的树的mktrees。然后以各种方式将这些组件函数进行组合或融合，以构建具有所需时间复杂性的最终算法。最终排序算法可能不会涉及底层树，但是树仍然存在于算法的结构中。融合的概念主导了设计过程的技术和数学方面，同时也是这本书真正的驱动力。
对于任何采用函数式方法的作者来说，像Haskell这样的函数式语言的缺点是，它们不像主流的过程式语言那样广为人知，所以必须花时间来解释它们。这也会大大增加本书的篇幅。这个问题的简单解决办法就是假设读者已经掌握了必要的知识。关于Haskell等语言的教材越来越多，包括我们自己的Thinking Functionally with Haskell（剑桥大学出版社，2014），我们假设读者已经读过相关内容。事实上，这本书是作为前一本书的姊妹篇设计的。在第1章中，我们会简要概述我们的假设，并简要回顾一些基本思想，但是你可能无法从第1章了解到足够的Haskell知识来理解本书其余部分的内容。即使你对函数式编程有所了解，但并不了解等式推理是如何进入这一领域的（一些关于函数式编程的书籍根本就没有提到等式推理），你可能仍然需要参考我们的前一本书。在任何情况下，等式推理所涉及的数学既不新鲜，也不算困难。
关于算法设计的书籍传统上涵盖3个广泛的领域：设计原则的集合、有用数据结构的研究，以及几个世纪以来发现的一些有趣的算法。有时这些书的内容是按照原则组织的，有时是按照主题（如图算法，或文本算法）组织的，有时是混合使用两种方式。本书主要采用第一种方法，专注于许多有效算法背后的五大主要设计策略：分而治之、贪心算法、减而治之、动态规划和穷举搜索。这些是每个认真的程序员都应该知道的设计策略。其中减而治之这一策略较为新颖，并在许多问题中被视为动态规划的替代方案。
在本书中，每种设计策略都有专门一部分与之对应，每部分都涵盖相关策略的各种已知算法和新算法。本书没有过多介绍数据结构方面的内容，虽然在本书的第一部分中，我们会讨论一些基本的数据结构，但我们将结合一些实用的Haskell数据结构库进行介绍。这样做的一个原因是我们希望控制这本书的篇幅，另一个原因是Chris Okasaki的著作Purely Functional Data Structures（剑桥大学出版社，1998）已涵盖大量相关内容。自我们开始写这本书以来，其他关于函数式数据结构的书籍已经相继出版，更多的相关书籍也在筹备之中。
本书的另一个特点是，不仅描述了一些受欢迎的算法，还描述了一些通常不会出现在算法设计类书籍中的算法。其中一些算法改编自Pearls of Functional Algorithm Design（2010）。引入这些新颖的算法是为了让这本书更加有趣，同时也更有教育意义。一般来说，有三种人会阅读算法设计方面的书籍：需要参考资料的学者、正在学门课程的本科生或研究生，以及对算法感兴趣的专业程序员。大多数专业程序员并不设计算法，而只是从库中获取它们。尽管如此，他们也是本书的目标读者，因为有时专业程序员会想了解更多关于构建优秀算法的方法和思路。
现实生活中的算法要比这本书中介绍的复杂得多。卫星导航系统中的最短路径算法也比算法设计教材中的最短路径算法复杂得多。现实生活中的算法必须处理规模问题，有效地使用计算机硬件、用户界面，并考虑许多其他与设计良好且实用的产品相关的因素。本书不会涉及这些方面的内容，实际上，大多数专门讨论算法设计原则的书也不会涉及这些方面的内容。
本书还有一个值得一提的特点：所有的练习都附有答案，即使有的答案比较简短。练习是本书的重要组成部分，即使不做练习，也要阅读问题和答案。本书没有在全书的最后提供完整的参考书目，而是在每一章的结尾列出与该章相关的一些书籍和文章等参考文献。
本书的大部分主要程序都可以在网站www.cs.ox.ac.uk/publications/books/adwh上找到。你还可以通过这个网站查看勘误表，并报告新的错误。我们也欢迎读者提出改进建议，包括有关新练习的想法。
致谢
本书的编写得益于Sue Gibbons、HsiangShang Ko与 Nicolas Wu的仔细审阅。手稿是使用Ralf Hinze和Andres Lh的lhs2TEX系统编写的，该系统完美地呈现了Haskell代码，并允许进行提取和类型检查。然后我们使用Koen Claessen和John Hughes开发的QuickCheck工具对提取的代码进行测试。代码的类型检查和快速检查帮我们减少了许多错误，当然，限于作者水平，书中疏漏在所难免，任何遗留的错误都是我们自己的责任。
我们也要感谢剑桥大学出版社的David Tranah和他的团队，他们的建议和辛勤工作促成了本书的最终出版。
Richard BirdJeremy Gibbons
理查德·伯德（Richard Bird）牛津大学名誉教授，著有多部广受好评的Haskell相关书籍，包括《Haskell函数式程序设计》和《函数式算法设计珠玑》。
杰里米·吉本斯（Jeremy Gibbons）牛津大学计算机科学教授，在该校教授软件工程非全日制专业硕士课程。他是Journal of Functional Programming的联合主编、IFIP Working Group 2.1 on Algorithmic Languages and Calculi的前任主席以及ACM SIGPLAN的前任副主席。
译者序
前言
第一部分基础知识
第1章函数式编程
11基本类型与函数
12处理列表
13归纳与递归的定义
14融合
15累积与串联
章节注释
参考文献
练习第2章时间
21渐近表示法
22估计运行时间
23上下文中的运行时间
24均摊运行时间
章节注释
参考文献
练习第3章实用的数据结构
31对称列表
32随机访问列表
33数组
章节注释
参考文献
练习第二部分分而治之
第4章二分查找
41一维查找
42二维查找
43二叉搜索树
44动态集
章节注释
参考文献
练习第5章排序
51快速排序
52归并排序
53堆排序
54桶排序及基数排序
55排序总和
章节注释
参考文献
练习第6章选择
61最大和最小
62单集合中的选择
63双集合中的选择
64从补集中选择
章节注释
参考文献
练习
第三部分贪心算法
第7章列表的贪心算法
71通用贪心算法
72贪心排序算法
73硬币兑换问题
74TEX中的十进制小数
75不确定性函数和精化
76总结
章节注释
参考文献
练习第8章树的贪心算法
81最小高度树
82哈夫曼编码树
83优先队列
章节注释
参考文献
练习第9章图的贪心算法
91图和生成树
92Kruskal算法
93不相交集和联合查找算法
94Prim算法
95单源最短路径
96Dijkstra算法
97慢跑者问题
章节注释
参考文献
练习
第四部分减而治之
第10章简化算法介绍
101基本理论
102分层网络中的路径
103再论硬币兑换
104背包问题
105一种通用的简化算法
章节注释
参考文献
练习第11章片段和子序列
111最长上升子序列
112最长公共子序列
113和最大子段
章节注释
参考文献
练习第12章划分
121划分的生成方法
122管理两个银行账户
123段落问题
章节注释
参考文献
练习
第五部分动态规划
第13章高效递归
131两个数字的例子
132再论背包问题
133最小代价编辑序列
134再论最长公共子序列
135穿梭巴士问题
章节注释
参考文献
练习第14章最佳划分
141立方时间复杂度的算法
142平方时间复杂度的算法
143复杂度算法示例
144单调性证明
145最佳二叉搜索树
146GarsiaWachs算法
章节注释
参考文献
练习第六部分穷举搜索
第15章搜索方法
151隐式搜索和n皇后问题
152给定和的表达式
153深度优先搜索与广度优先搜索
154登月问题
155预先规划
156高峰时间问题
章节注释
参考文献
练习第16章启发式搜索
161乐观启发式搜索
162单调启发式搜索
163仓库导航
1648数码问题
章节注释
参考文献
练习附录练习答案
新书资讯![函数式算法设计的艺术 [英] 理查德·伯德 [英]杰里米·吉本斯](http://p.ceeol.cn/pic//images/noimages.gif)
