函数式算法设计的艺术

本书专门介绍了算法设计的五项主要原则：分而治之、贪心算法、减而治之、动态规划和穷举搜索。这些原则是用Haskell这种纯函数式语言来阐述的，与使用命令式语言相比，解释更简单，程序更短。书中还配有精心挑选的例子（既有新示例，也有标准示例），展示了算法之间的共性和差异。算法开发在适用的情况下使用等式推理，阐明适用性条件和正确性论证。每章最后都附有习题（共近300道），每道习题都有完整的答案，便于读者巩固理解，并将这些技术应用于一系列问题。
本书适用于计算机科学与技术及软件工程相关专业学生（包括本科生和研究生）、研究人员、教师和专业人士，可以帮助他们进一步了解如何设计和实现优秀的算法，以及如何用纯函数术语来表达这些算法。

本书介绍了算法设计的五个主要原则:分治法、贪婪算法、稀疏、动态程序设计和穷举搜索。让学生、教师、研究人员和专业人员更好地了解一个好的算法是如何组成的，以及如何用纯函数的形式表达这些算法。

译者序<br />前言<br />第一部分基础知识<br />第1章函数式编程<br />11基本类型与函数<br />12处理列表<br />13归纳与递归的定义<br />14融合<br />15累积与串联<br />章节注释<br />参考文献<br />练习第2章时间<br />21渐近表示法<br />22估计运行时间<br />23上下文中的运行时间<br />24均摊运行时间<br />章节注释<br />参考文献<br />练习第3章实用的数据结构<br />31对称列表<br />32随机访问列表<br />33数组<br />章节注释<br />参考文献<br />练习第二部分分而治之<br />第4章二分查找<br />41一维查找<br />42二维查找<br />43二叉搜索树<br />44动态集<br />章节注释<br />参考文献<br />练习第5章排序<br />51快速排序<br />52归并排序<br />53堆排序<br />54桶排序及基数排序<br />55排序总和<br />章节注释<br />参考文献<br />练习第6章选择<br />61最大和最小<br />62单集合中的选择<br />63双集合中的选择<br />64从补集中选择<br />章节注释<br />参考文献<br />练习<br />第三部分贪心算法<br />第7章列表的贪心算法<br />71通用贪心算法<br />72贪心排序算法<br />73硬币兑换问题<br />74TEX中的十进制小数<br />75不确定性函数和精化<br />76总结<br />章节注释<br />参考文献<br />练习第8章树的贪心算法<br />81最小高度树<br />82哈夫曼编码树<br />83优先队列<br />章节注释<br />参考文献<br />练习第9章图的贪心算法<br />91图和生成树<br />92Kruskal算法<br />93不相交集和联合查找算法<br />94Prim算法<br />95单源最短路径<br />96Dijkstra算法<br />97慢跑者问题<br />章节注释<br />参考文献<br />练习<br />第四部分减而治之<br />第10章简化算法介绍<br />101基本理论<br />102分层网络中的路径<br />103再论硬币兑换<br />104背包问题<br />105一种通用的简化算法<br />章节注释<br />参考文献<br />练习第11章片段和子序列<br />111最长上升子序列<br />112最长公共子序列<br />113和最大子段<br />章节注释<br />参考文献<br />练习第12章划分<br />121划分的生成方法<br />122管理两个银行账户<br />123段落问题<br />章节注释<br />参考文献<br />练习<br />第五部分动态规划<br />第13章高效递归<br />131两个数字的例子<br />132再论背包问题<br />133最小代价编辑序列<br />134再论最长公共子序列<br />135穿梭巴士问题<br />章节注释<br />参考文献<br />练习第14章最佳划分<br />141立方时间复杂度的算法<br />142平方时间复杂度的算法<br />143复杂度算法示例<br />144单调性证明<br />145最佳二叉搜索树<br />146GarsiaWachs算法<br />章节注释<br />参考文献<br />练习第六部分穷举搜索<br />第15章搜索方法<br />151隐式搜索和n皇后问题<br />152给定和的表达式<br />153深度优先搜索与广度优先搜索<br />154登月问题<br />155预先规划<br />156高峰时间问题<br />章节注释<br />参考文献<br />练习第16章启发式搜索<br />161乐观启发式搜索<br />162单调启发式搜索<br />163仓库导航<br />1648数码问题<br />章节注释<br />参考文献<br />练习附录练习答案