| 开本：16开 |
| 纸张：胶版纸 |
| 包装：平装-胶订 |
| 是否套装：否 |
| 国际标准书号ISBN：9787111775102 |
| 所属分类：图书>计算机/网络>程序设计>算法 |
《函数式程序设计》姊妹篇，牛津大学名誉教授 最后一部作品
编辑推荐
本书专门介绍了算法设计的五项主要原则：分而治之、贪心算法、减而治之、动态规划和穷举搜索。这些原则是用这种纯函数式语言来阐述的，与使用命令式语言相比，解释更简单，程序更短。书中还配有精心挑选的例子（既有新示例，也有标准示例），展示了算法之间的共性和差异。算法开发在适用的情况下使用等式推理，阐明适用性条件和正确性论证。每章最后都附有习题（共近道），每道习题都有完整的答案，便于读者巩固理解，并将这些技术应用于一系列问题。本书适用于计算机科学与技术及软件工程相关专业学生（包括本科生和研究生）、研究人员、教师和专业人士，可以帮助他们进一步了解如何设计和实现优秀的算法，以及如何用纯函数术语来表达这些算法。
前 言
译者序
如果真有一门绝世武功，“招式”和“内功”孰轻孰重？如果说这个问题真有答案，那么在我讲授语言程序设计多年之后，开始与本书相遇相知时似乎逐渐找到了。
长久以来，函数式编程因为侧重原理而被认为更接近于“内功”。由于某些情况下的性能问题以及学习资料的缺乏，函数式编程一直没有成为主导。近年来，计算机硬件性能的提升带来了转机，我们看到旧语言逐渐引入函数式的特性、新语言在构建之初就考虑更多函数式的设计。
在这本书里，当分而治之、贪心算法、减而治之、动态规划、穷举搜索这些算法用纯函数式语言来实现时，简短的代码体现出了科学思想与工程优雅。外化于形、内化于心的交相辉映令人沉醉！无论对于程序设计，还是对于语言程序设计，“招式”和“内功”的兼收并蓄都是一个更高的境界！
本书的作者是牛津大学的 和 教授。令人遗憾的是， 教授在年月日离开了我们，他一生致力于推广函数式编程，对算法和程序设计做出了伟大贡献。在翻译这本书的过程中，我深感他文字之魅力和思想之深邃。大家在阅读此书时产生不同编程思维碰撞的电光火石是对最好的缅怀。译者序
如果真有一门绝世武功，“招式”和“内功”孰轻孰重？如果说这个问题真有答案，那么在我讲授语言程序设计多年之后，开始与本书相遇相知时似乎逐渐找到了。
长久以来，函数式编程因为侧重原理而被认为更接近于“内功”。由于某些情况下的性能问题以及学习资料的缺乏，函数式编程一直没有成为主导。近年来，计算机硬件性能的提升带来了转机，我们看到旧语言逐渐引入函数式的特性、新语言在构建之初就考虑更多函数式的设计。
在这本书里，当分而治之、贪心算法、减而治之、动态规划、穷举搜索这些算法用纯函数式语言来实现时，简短的代码体现出了科学思想与工程优雅。外化于形、内化于心的交相辉映令人沉醉！无论对于程序设计，还是对于语言程序设计，“招式”和“内功”的兼收并蓄都是一个更高的境界！
本书的作者是牛津大学的 和 教授。令人遗憾的是， 教授在年月日离开了我们，他一生致力于推广函数式编程，对算法和程序设计做出了伟大贡献。在翻译这本书的过程中，我深感他文字之魅力和思想之深邃。大家在阅读此书时产生不同编程思维碰撞的电光火石是对最好的缅怀。
万琳
前言
本书的目的是使用纯函数方法来介绍算法设计的原理。我们选择的语言是，所以我们设计的所有算法都将用函数来表示。有很多结构化函数定义的特性，但是我们只会使用其中的一小部分。
使用函数代替循环和赋值语句来表达算法会改变一切。首先，以函数形式表达的算法会由其他更基本的函数组成，而这些基本函数可以被单独研究并重用在其他算法中。例如，排序算法可以通过构建并使用某种树的结构来实现，而我们可以将构建树的函数与使用树的函数分开研究。此外，可以使用简单的等式属性来捕获这些基本函数中每个函数的特性以及它们与其他函数的关系。在此基础上，人们可以用一种命令式代码不容易实现的方式来探讨和推理算法的“深度”结构。可以肯定的是，我们可以通过在谓词演算中形式化命令程序的规范并使用循环不变式来证明它们是正确的，从而对命令程序进行形式化推理。但这同时也是函数式编程的关键所在，即不能轻松地直接根据命令代码的语言来推断命令式程序的属性。因此，关于形式化程序设计的书与关于算法设计的书有很大的不同：它们要求人们精通谓词演算和必要的命令性术语。相比之下，许多关于算法设计的书通常都会对算法进行逐步介绍，并使用非形式化陈述的循环不变式来帮助人们理解为什么算法是正确的。
函数式编程使得我们不再需要考虑两种独立的语言，可以通过简单的等式推理过程愉快地计算出更好的算法版本，或算法的一部分，而这也许就是本书的主要贡献。尽管本书包含了相当多的等式推理，但我们会尽量简化以保证阅读体验。实际情况往往是，计算做起来很有趣，但大量的公式读起来会很无聊。尽管命令式算法是用、还是伪代码来表示并不是很重要，但如果用函数式来表示算法，那情况就完全不同了。
本书讨论的许多问题，特别是在后面的部分中，都会从任务的规范开始，表示为标准函数的组合，如映射、过滤器和叠，以及其他函数，如用于计算列表所有排列的、用于计算所有分区的和用于构建特定种类的树的。然后以各种方式将这些组件函数进行组合或融合，以构建具有所需时间复杂性的最终算法。最终排序算法可能不会涉及底层树，但是树仍然存在于算法的结构中。融合的概念主导了设计过程的技术和数学方面，同时也是这本书真正的驱动力。
对于任何采用函数式方法的作者来说，像这样的函数式语言的缺点是，它们不像主流的过程式语言那样广为人知，所以必须花时间来解释它们。这也会大大增加本书的篇幅。这个问题的简单解决办法就是假设读者已经掌握了必要的知识。关于等语言的教材越来越多，包括我们自己的 （剑桥大学出版社，），我们假设读者已经读过相关内容。事实上，这本书是作为前一本书的姊妹篇设计的。在第章中，我们会简要概述我们的假设，并简要回顾一些基本思想，但是你可能无法从第章了解到足够的知识来理解本书其余部分的内容。即使你对函数式编程有所了解，但并不了解等式推理是如何进入这一领域的（一些关于函数式编程的书籍根本就没有提到等式推理），你可能仍然需要参考我们的前一本书。在任何情况下，等式推理所涉及的数学既不新鲜，也不算困难。
关于算法设计的书籍传统上涵盖个广泛的领域：设计原则的集合、有用数据结构的研究，以及几个世纪以来发现的一些有趣的算法。有时这些书的内容是按照原则组织的，有时是按照主题（如图算法，或文本算法）组织的，有时是混合使用两种方式。本书主要采用第一种方法，专注于许多有效算法背后的五大主要设计策略：分而治之、贪心算法、减而治之、动态规划和穷举搜索。这些是每个认真的程序员都应该知道的设计策略。其中减而治之这一策略较为新颖，并在许多问题中被视为动态规划的替代方案。
在本书中，每种设计策略都有专门一部分与之对应，每部分都涵盖相关策略的各种已知算法和新算法。本书没有过多介绍数据结构方面的内容，虽然在本书的第一部分中，我们会讨论一些基本的数据结构，但我们将结合一些实用的数据结构库进行介绍。这样做的一个原因是我们希望控制这本书的篇幅，另一个原因是 的著作 （剑桥大学出版社，）已涵盖大量相关内容。自我们开始写这本书以来，其他关于函数式数据结构的书籍已经相继出版，更多的相关书籍也在筹备之中。
本书的另一个特点是，不仅描述了一些受欢迎的算法，还描述了一些通常不会出现在算法设计类书籍中的算法。其中一些算法改编自 （）。引入这些新颖的算法是为了让这本书更加有趣，同时也更有教育意义。一般来说，有三种人会阅读算法设计方面的书籍：需要参考资料的学者、正在学门课程的本科生或研究生，以及对算法感兴趣的专业程序员。大多数专业程序员并不设计算法，而只是从库中获取它们。尽管如此，他们也是本书的目标读者，因为有时专业程序员会想了解更多关于构建优秀算法的方法和思路。
现实生活中的算法要比这本书中介绍的复杂得多。卫星导航系统中的最短路径算法也比算法设计教材中的最短路径算法复杂得多。现实生活中的算法必须处理规模问题，有效地使用计算机硬件、用户界面，并考虑许多其他与设计良好且实用的产品相关的因素。本书不会涉及这些方面的内容，实际上，大多数专门讨论算法设计原则的书也不会涉及这些方面的内容。
本书还有一个值得一提的特点：所有的练习都附有答案，即使有的答案比较简短。练习是本书的重要组成部分，即使不做练习，也要阅读问题和答案。本书没有在全书的最后提供完整的参考书目，而是在每一章的结尾列出与该章相关的一些书籍和文章等参考文献。
本书的大部分主要程序都可以在网站上找到。你还可以通过这个网站查看勘误表，并报告新的错误。我们也欢迎读者提出改进建议，包括有关新练习的想法。
致谢
本书的编写得益于 、 与 的仔细审阅。手稿是使用 和 的系统编写的，该系统完美地呈现了代码，并允许进行提取和类型检查。然后我们使用 和 开发的工具对提取的代码进行测试。代码的类型检查和快速检查帮我们减少了许多错误，当然，限于作者水平，书中疏漏在所难免，任何遗留的错误都是我们自己的责任。
我们也要感谢剑桥大学出版社的 和他的团队，他们的建议和辛勤工作促成了本书的最终出版。
显示全部信息
目 录
译者序
前言
第一部分基础知识
第章函数式编程
基本类型与函数
处理列表
归纳与递归的定义
融合
累积与串联
章节注释
参考文献
练习第章时间
渐近表示法
估计运行时间译者序
前言
第一部分基础知识
第章函数式编程
基本类型与函数
处理列表
归纳与递归的定义
融合
累积与串联
章节注释
参考文献
练习第章时间
渐近表示法
估计运行时间
上下文中的运行时间
均摊运行时间
章节注释
参考文献
练习第章实用的数据结构
对称列表
随机访问列表
数组
章节注释
参考文献
练习第二部分分而治之
第章二分查找
一维查找
二维查找
二叉搜索树
动态集
章节注释
参考文献
练习第章排序
快速排序
归并排序
堆排序
桶排序及基数排序
排序总和
章节注释
参考文献
练习第章选择
最大和最小
单集合中的选择
双集合中的选择
从补集中选择
章节注释
参考文献
练习
第三部分贪心算法
第章列表的贪心算法
通用贪心算法
贪心排序算法
硬币兑换问题
中的十进制小数
不确定性函数和精化
总结
章节注释
参考文献
练习第章树的贪心算法
最小高度树
哈夫曼编码树
优先队列
章节注释
参考文献
练习第章图的贪心算法
图和生成树
算法
不相交集和联合查找算法
算法
单源最短路径
算法
慢跑者问题
章节注释
参考文献
练习
第四部分减而治之
第章简化算法介绍
基本理论
分层网络中的路径
再论硬币兑换
背包问题
一种通用的简化算法
章节注释
参考文献
练习第章片段和子序列
最长上升子序列
最长公共子序列
和最大子段
章节注释
参考文献
练习第章划分
划分的生成方法
管理两个银行账户
段落问题
章节注释
参考文献
练习
第五部分动态规划
第章高效递归
两个数字的例子
再论背包问题
最小代价编辑序列
再论最长公共子序列
穿梭巴士问题
章节注释
参考文献
练习第章最佳划分
立方时间复杂度的算法
平方时间复杂度的算法
复杂度算法示例
单调性证明
最佳二叉搜索树
算法
章节注释
参考文献
练习第六部分穷举搜索
第章搜索方法
隐式搜索和后问题
给定和的表达式
深度优先搜索与广度优先搜索
登月问题
预先规划
高峰时间问题
章节注释
参考文献
练习第章启发式搜索
乐观启发式搜索
单调启发式搜索
仓库导航
数码问题
章节注释
参考文献
练习附录练习答案
显示全部信息
作者简介
理查德·伯德（ ）牛津大学名誉教授，著有多部广受好评的相关书籍，包括《函数式程序设计》和《函数式算法设计珠玑》。
杰里米·吉本斯（ ）牛津大学计算机科学教授，在该校教授软件工程非全日制专业硕士课程。他是 的联合主编、 的前任主席以及 的前任副主席。
编辑推荐
本书专门介绍了算法设计的五项主要原则：分而治之、贪心算法、减而治之、动态规划和穷举搜索。这些原则是用这种纯函数式语言来阐述的，与使用命令式语言相比，解释更简单，程序更短。书中还配有精心挑选的例子（既有新示例，也有标准示例），展示了算法之间的共性和差异。算法开发在适用的情况下使用等式推理，阐明适用性条件和正确性论证。每章最后都附有习题（共近道），每道习题都有完整的答案，便于读者巩固理解，并将这些技术应用于一系列问题。本书适用于计算机科学与技术及软件工程相关专业学生（包括本科生和研究生）、研究人员、教师和专业人士，可以帮助他们进一步了解如何设计和实现优秀的算法，以及如何用纯函数术语来表达这些算法。
前 言
译者序
如果真有一门绝世武功，“招式”和“内功”孰轻孰重？如果说这个问题真有答案，那么在我讲授语言程序设计多年之后，开始与本书相遇相知时似乎逐渐找到了。
长久以来，函数式编程因为侧重原理而被认为更接近于“内功”。由于某些情况下的性能问题以及学习资料的缺乏，函数式编程一直没有成为主导。近年来，计算机硬件性能的提升带来了转机，我们看到旧语言逐渐引入函数式的特性、新语言在构建之初就考虑更多函数式的设计。
在这本书里，当分而治之、贪心算法、减而治之、动态规划、穷举搜索这些算法用纯函数式语言来实现时，简短的代码体现出了科学思想与工程优雅。外化于形、内化于心的交相辉映令人沉醉！无论对于程序设计，还是对于语言程序设计，“招式”和“内功”的兼收并蓄都是一个更高的境界！
本书的作者是牛津大学的 和 教授。令人遗憾的是， 教授在年月日离开了我们，他一生致力于推广函数式编程，对算法和程序设计做出了伟大贡献。在翻译这本书的过程中，我深感他文字之魅力和思想之深邃。大家在阅读此书时产生不同编程思维碰撞的电光火石是对最好的缅怀。译者序
如果真有一门绝世武功，“招式”和“内功”孰轻孰重？如果说这个问题真有答案，那么在我讲授语言程序设计多年之后，开始与本书相遇相知时似乎逐渐找到了。
长久以来，函数式编程因为侧重原理而被认为更接近于“内功”。由于某些情况下的性能问题以及学习资料的缺乏，函数式编程一直没有成为主导。近年来，计算机硬件性能的提升带来了转机，我们看到旧语言逐渐引入函数式的特性、新语言在构建之初就考虑更多函数式的设计。
在这本书里，当分而治之、贪心算法、减而治之、动态规划、穷举搜索这些算法用纯函数式语言来实现时，简短的代码体现出了科学思想与工程优雅。外化于形、内化于心的交相辉映令人沉醉！无论对于程序设计，还是对于语言程序设计，“招式”和“内功”的兼收并蓄都是一个更高的境界！
本书的作者是牛津大学的 和 教授。令人遗憾的是， 教授在年月日离开了我们，他一生致力于推广函数式编程，对算法和程序设计做出了伟大贡献。在翻译这本书的过程中，我深感他文字之魅力和思想之深邃。大家在阅读此书时产生不同编程思维碰撞的电光火石是对最好的缅怀。
万琳
前言
本书的目的是使用纯函数方法来介绍算法设计的原理。我们选择的语言是，所以我们设计的所有算法都将用函数来表示。有很多结构化函数定义的特性，但是我们只会使用其中的一小部分。
使用函数代替循环和赋值语句来表达算法会改变一切。首先，以函数形式表达的算法会由其他更基本的函数组成，而这些基本函数可以被单独研究并重用在其他算法中。例如，排序算法可以通过构建并使用某种树的结构来实现，而我们可以将构建树的函数与使用树的函数分开研究。此外，可以使用简单的等式属性来捕获这些基本函数中每个函数的特性以及它们与其他函数的关系。在此基础上，人们可以用一种命令式代码不容易实现的方式来探讨和推理算法的“深度”结构。可以肯定的是，我们可以通过在谓词演算中形式化命令程序的规范并使用循环不变式来证明它们是正确的，从而对命令程序进行形式化推理。但这同时也是函数式编程的关键所在，即不能轻松地直接根据命令代码的语言来推断命令式程序的属性。因此，关于形式化程序设计的书与关于算法设计的书有很大的不同：它们要求人们精通谓词演算和必要的命令性术语。相比之下，许多关于算法设计的书通常都会对算法进行逐步介绍，并使用非形式化陈述的循环不变式来帮助人们理解为什么算法是正确的。
函数式编程使得我们不再需要考虑两种独立的语言，可以通过简单的等式推理过程愉快地计算出更好的算法版本，或算法的一部分，而这也许就是本书的主要贡献。尽管本书包含了相当多的等式推理，但我们会尽量简化以保证阅读体验。实际情况往往是，计算做起来很有趣，但大量的公式读起来会很无聊。尽管命令式算法是用、还是伪代码来表示并不是很重要，但如果用函数式来表示算法，那情况就完全不同了。
本书讨论的许多问题，特别是在后面的部分中，都会从任务的规范开始，表示为标准函数的组合，如映射、过滤器和叠，以及其他函数，如用于计算列表所有排列的、用于计算所有分区的和用于构建特定种类的树的。然后以各种方式将这些组件函数进行组合或融合，以构建具有所需时间复杂性的最终算法。最终排序算法可能不会涉及底层树，但是树仍然存在于算法的结构中。融合的概念主导了设计过程的技术和数学方面，同时也是这本书真正的驱动力。
对于任何采用函数式方法的作者来说，像这样的函数式语言的缺点是，它们不像主流的过程式语言那样广为人知，所以必须花时间来解释它们。这也会大大增加本书的篇幅。这个问题的简单解决办法就是假设读者已经掌握了必要的知识。关于等语言的教材越来越多，包括我们自己的 （剑桥大学出版社，），我们假设读者已经读过相关内容。事实上，这本书是作为前一本书的姊妹篇设计的。在第章中，我们会简要概述我们的假设，并简要回顾一些基本思想，但是你可能无法从第章了解到足够的知识来理解本书其余部分的内容。即使你对函数式编程有所了解，但并不了解等式推理是如何进入这一领域的（一些关于函数式编程的书籍根本就没有提到等式推理），你可能仍然需要参考我们的前一本书。在任何情况下，等式推理所涉及的数学既不新鲜，也不算困难。
关于算法设计的书籍传统上涵盖个广泛的领域：设计原则的集合、有用数据结构的研究，以及几个世纪以来发现的一些有趣的算法。有时这些书的内容是按照原则组织的，有时是按照主题（如图算法，或文本算法）组织的，有时是混合使用两种方式。本书主要采用第一种方法，专注于许多有效算法背后的五大主要设计策略：分而治之、贪心算法、减而治之、动态规划和穷举搜索。这些是每个认真的程序员都应该知道的设计策略。其中减而治之这一策略较为新颖，并在许多问题中被视为动态规划的替代方案。
在本书中，每种设计策略都有专门一部分与之对应，每部分都涵盖相关策略的各种已知算法和新算法。本书没有过多介绍数据结构方面的内容，虽然在本书的第一部分中，我们会讨论一些基本的数据结构，但我们将结合一些实用的数据结构库进行介绍。这样做的一个原因是我们希望控制这本书的篇幅，另一个原因是 的著作 （剑桥大学出版社，）已涵盖大量相关内容。自我们开始写这本书以来，其他关于函数式数据结构的书籍已经相继出版，更多的相关书籍也在筹备之中。
本书的另一个特点是，不仅描述了一些受欢迎的算法，还描述了一些通常不会出现在算法设计类书籍中的算法。其中一些算法改编自 （）。引入这些新颖的算法是为了让这本书更加有趣，同时也更有教育意义。一般来说，有三种人会阅读算法设计方面的书籍：需要参考资料的学者、正在学门课程的本科生或研究生，以及对算法感兴趣的专业程序员。大多数专业程序员并不设计算法，而只是从库中获取它们。尽管如此，他们也是本书的目标读者，因为有时专业程序员会想了解更多关于构建优秀算法的方法和思路。
现实生活中的算法要比这本书中介绍的复杂得多。卫星导航系统中的最短路径算法也比算法设计教材中的最短路径算法复杂得多。现实生活中的算法必须处理规模问题，有效地使用计算机硬件、用户界面，并考虑许多其他与设计良好且实用的产品相关的因素。本书不会涉及这些方面的内容，实际上，大多数专门讨论算法设计原则的书也不会涉及这些方面的内容。
本书还有一个值得一提的特点：所有的练习都附有答案，即使有的答案比较简短。练习是本书的重要组成部分，即使不做练习，也要阅读问题和答案。本书没有在全书的最后提供完整的参考书目，而是在每一章的结尾列出与该章相关的一些书籍和文章等参考文献。
本书的大部分主要程序都可以在网站上找到。你还可以通过这个网站查看勘误表，并报告新的错误。我们也欢迎读者提出改进建议，包括有关新练习的想法。
致谢
本书的编写得益于 、 与 的仔细审阅。手稿是使用 和 的系统编写的，该系统完美地呈现了代码，并允许进行提取和类型检查。然后我们使用 和 开发的工具对提取的代码进行测试。代码的类型检查和快速检查帮我们减少了许多错误，当然，限于作者水平，书中疏漏在所难免，任何遗留的错误都是我们自己的责任。
我们也要感谢剑桥大学出版社的 和他的团队，他们的建议和辛勤工作促成了本书的最终出版。
显示全部信息
目 录
译者序
前言
第一部分基础知识
第章函数式编程
基本类型与函数
处理列表
归纳与递归的定义
融合
累积与串联
章节注释
参考文献
练习第章时间
渐近表示法
估计运行时间译者序
前言
第一部分基础知识
第章函数式编程
基本类型与函数
处理列表
归纳与递归的定义
融合
累积与串联
章节注释
参考文献
练习第章时间
渐近表示法
估计运行时间
上下文中的运行时间
均摊运行时间
章节注释
参考文献
练习第章实用的数据结构
对称列表
随机访问列表
数组
章节注释
参考文献
练习第二部分分而治之
第章二分查找
一维查找
二维查找
二叉搜索树
动态集
章节注释
参考文献
练习第章排序
快速排序
归并排序
堆排序
桶排序及基数排序
排序总和
章节注释
参考文献
练习第章选择
最大和最小
单集合中的选择
双集合中的选择
从补集中选择
章节注释
参考文献
练习
第三部分贪心算法
第章列表的贪心算法
通用贪心算法
贪心排序算法
硬币兑换问题
中的十进制小数
不确定性函数和精化
总结
章节注释
参考文献
练习第章树的贪心算法
最小高度树
哈夫曼编码树
优先队列
章节注释
参考文献
练习第章图的贪心算法
图和生成树
算法
不相交集和联合查找算法
算法
单源最短路径
算法
慢跑者问题
章节注释
参考文献
练习
第四部分减而治之
第章简化算法介绍
基本理论
分层网络中的路径
再论硬币兑换
背包问题
一种通用的简化算法
章节注释
参考文献
练习第章片段和子序列
最长上升子序列
最长公共子序列
和最大子段
章节注释
参考文献
练习第章划分
划分的生成方法
管理两个银行账户
段落问题
章节注释
参考文献
练习
第五部分动态规划
第章高效递归
两个数字的例子
再论背包问题
最小代价编辑序列
再论最长公共子序列
穿梭巴士问题
章节注释
参考文献
练习第章最佳划分
立方时间复杂度的算法
平方时间复杂度的算法
复杂度算法示例
单调性证明
最佳二叉搜索树
算法
章节注释
参考文献
练习第六部分穷举搜索
第章搜索方法
隐式搜索和后问题
给定和的表达式
深度优先搜索与广度优先搜索
登月问题
预先规划
高峰时间问题
章节注释
参考文献
练习第章启发式搜索
乐观启发式搜索
单调启发式搜索
仓库导航
数码问题
章节注释
参考文献
练习附录练习答案
显示全部信息
作者简介
理查德·伯德（ ）牛津大学名誉教授，著有多部广受好评的相关书籍，包括《函数式程序设计》和《函数式算法设计珠玑》。
杰里米·吉本斯（ ）牛津大学计算机科学教授，在该校教授软件工程非全日制专业硕士课程。他是 的联合主编、 的前任主席以及 的前任副主席。