新書推薦：
《
神灵衰落：祈雨与乾隆朝的信仰危机
》
售價：NT$
498.0
《
深度营销：成就营销领导力的12大原则（麦肯锡年度经管好书，12大原则揭秘营销本质，带好团队就是从领导力到影响力！）
》
售價：NT$
325.0
《
新质生产力：发展新动能
》
售價：NT$
493.0
《
状态比能力更重要：108个状态调整法
》
售價：NT$
308.0
《
中国上市公司担保行为的影响因素及其效应研究
》
售價：NT$
202.0
《
企业级数据架构：核心要素、架构模型、数据管理与平台搭建 李杨
》
售價：NT$
554.0
《
政和元年：宋辽金夏的国运博弈与谍战风云
》
售價：NT$
381.0
《
黄金圈法则
》
售價：NT$
437.0
|
| 內容簡介： |
|
本书介绍了各种广泛使用的算法，用纯函数式编程语言表达它们，使读者更清楚地理解它们的结构和操作。在第1章中，介绍了构成使用的格式变体的特殊符号。第2章介绍了函数式编程中许多更简单、更通用的模式。第3～7章介绍和解释数据结构、排序、组合结构、图表和子列表搜索。在整本书中，作者用Scheme编程语言的纯函数版本介绍了算法。本书配有练习题，适用于编程技术方面的本科和研究生课程。
|
| 目錄：
|
出版者的话
译者序
前言
第1章 基本符号1
1.1 简单值1
1.2 标识符和表达式3
1.3 函数和过程4
1.4 算术函数5
1.4.1 加法5
1.4.2 减法5
1.4.3 乘法6
1.4.4 除法6
1.4.5 幂运算7
1.4.6 过程总结7
1.5 过程调用9
1.6 λ表达式10
1.6.1 变元过程11
1.6.2 构建列表13
1.6.3 返回多个值13
1.6.4 没有结果的计算14
1.7 谓词15
1.7.1 分类谓词16
1.7.2 相等谓词16
1.7.3 相等和类型16
1.8 条件类型表达式19
1.8.1 条件表达式19
1.8.2 合取表达式与析取表达式19
1.9 定义21
1.9.1 过程定义21
1.9.2 递归定义22
1.10 局部绑定23
1.10.1 局部过程24
1.10.2 局部递归24
1.10.3 收纳表达式25
第2章 工具箱27
2.1 列表映射27
2.2 常量过程28
2.3 过程节选29
2.3.1 invoke过程30
2.3.2 卡瑞化31
2.4 耦合器32
2.4.1 过程复合32
2.4.2 并行应用33
2.4.3 调度34
2.5 适配器35
2.5.1 选择35
2.5.2 重排36
2.5.3 预处理和后处理36
2.6 递归管理器38
2.6.1 recur过程39
2.6.2 递归谓词40
2.6.3 迭代41
2.7 欧几里得算法44
2.8 高阶布尔过程47
2.8.1 布尔值和谓词上的操作47
2.8.2 ^if过程47
2.9 自然数和递归49
2.9.1 数学归纳法49
2.9.2 自然数上的递归49
2.9.3 计数53
2.9.4 有界推广54
第3章 数据结构56
3.1 建模56
3.2 空值57
3.3 和类型57
3.3.1 枚举57
3.3.2 可区分并集58
3.3.3 递归类型方程59
3.4 有序对60
3.4.1 命名对61
3.4.2 积类型61
3.4.3 再议可区分并集62
3.4.4 重新实现自然数62
3.5 盒64
3.6 列表66
3.6.1 选择过程67
3.6.2 同构列表68
3.6.3 列表的递归过程69
3.6.4 列表归纳原理70
3.6.5 列表递归管理71
3.6.6 展开73
3.7 列表算法77
3.7.1 元数扩展77
3.7.2 筛选和划分79
3.7.3 子列表80
3.7.4 位置选择81
3.7.5 列表元素上的谓词扩展到列表82
3.7.6 转置、压缩和解压缩83
3.7.7 聚合多个结果84
3.8 源89
3.9 多元组98
3.9.1 建立模型99
3.9.2 记录类型99
3.10 树101
3.10.1 树归纳原理103
3.10.2 树递归管理103
3.11 灌木109
3.11.1 灌木归纳原理110
3.11.2 灌木递归管理110
3.12 包113
3.12.1 基本包过程114
3.12.2 包操作115
3.12.3 包递归管理116
3.13 等价关系120
3.14 集合123
3.14.1 集合递归管理124
3.14.2 筛选和划分125
3.14.3 其他集合运算126
3.14.4 并集、交集和差集127
3.15 表132
3.16 缓冲区138
第4章 排序142
4.1 序关系142
4.1.1 隐式定义的等价关系142
4.1.2 测试一个列表是否有序143
4.1.3 查找极值143
4.1.4 复合序关系145
4.1.5 字典序145
4.2 排序算法148
4.2.1 插入排序149
4.2.2 选择排序149
4.2.3 快速排序150
4.2.4 归并排序150
4.3 二叉搜索树153
4.3.1 测试二叉搜索树不变量154
4.3.2 从二叉搜索树中提取一个值155
4.3.3 二叉搜索树排序156
4.4 红黑树158
4.4.1 实现红黑树159
4.4.2 颜色翻转和旋转160
4.4.3 插入161
4.4.4 查找163
4.4.5 删除163
4.4.6 用红黑树实现表168
4.5 堆175
4.5.1 折叠和展开堆178
4.5.2 堆排序178
4.6 序统计量181
第5章 组合构造183
5.1 笛卡儿积183
5.1.1 笛卡儿积排序185
5.1.2 排位和去排位186
5.2 列表选择189
5.2.1 子列表189
5.2.2 分组193
5.2.3 子序列和选择194
5.3 包选择199
5.4 排列201
5.5 划分204
5.5.1 包划分204
5.5.2 划分自然数206
第6章 图208
6.1图的实现208
6.1.1图的构造209
6.1.2图与关系211
6.1.3图的性质212
6.1.4其他图访问方法213
6.1.5无向图215
6.2深度优先遍历221
6.2.1图的遍历221
6.2.2深度优先222
6.2.3拓扑排序223
6.2.4可到达结点223
6.3路径225
6.4广度优先遍历227
6.5生成树229
6.6最短路径233
6.6.1Bellman-Ford算法233
6.6.2Dijkstra算法234
6.6.3Floyd-Warshall算法235
6.7流网络239
第7章 子列表搜索244
7.1简单低效的算法244
7.2Knuth-Morris-Pratt算法246
7.3Boyer-Moore算法253
7.4Rabin-Karp算法255
附录A 推荐读物260
附录B afp primitives库261
附录C 如何使用AFP库263
|
| 內容試閱：
|
算法的研究源于人类寻求问题答案的渴望。我们更喜欢找到问题的真相，而且是使用客观的方法得出的答案。这种偏好的原因是很实际的。如果能够了解世界的本真面目，我们的行动就更有可能取得令人满意的结果，因此我们不断探求真理。如果人们能够独立地验证问题的答案，那么就更容易为实现共同目标达成共识与合作，因此在探求真理时，我们使用他人可验证的方法。
有时我们会发现许多问题都有相似的结构，而且都是同一类问题的实例。在这种情况下，可能存在一种能够解决这类问题的共同方法。这种方法就是算法：一种有效的、逐步求解的计算方法。依照这种方法，人们可以获得一般的、形式化的问题的任何实例的答案。
在计算机出现之前，执行一个需要大量步骤或大量数据的算法，需要非凡的耐心、细心和执着。即便如此，所得的结果往往也是有缺陷的。例如，从1853年到1873年，一位名叫威廉·尚克斯（William Shanks）的计算狂热爱好者把他大部分的业余时间都用在计算π的高精度值上，并且计算到小数点后707位。直到1944年，人们才发现尚克斯犯了一个错误，影响了第528位和所有随后的数字，在这之前，尚克斯一直保持着这个计算的记录。在没有机械辅助的情况下，人类有史以来进行的最大规模的计算可能是1880年的美国人口普查，它花了七八年的时间才完成，几乎可以肯定的是，其中充满了错误的结果。
电子存储程序计算机的发明和发展在很大程度上消除了这种对计算复杂性的限制。我们现在可以在几分之一秒内算出π的707位值，而完成1880年的美国人口普查计算或许只需要耗时一分钟。如今的大规模计算可能是诸如计算π的5000亿位数这样的任务，我们希望计算的结果是完全正确的。如今的大规模数据集可能是以太字节（terabyte）为单位计量的。
直到20世纪中叶，算法的发明和应用的另一个障碍是缺少用于记录算法的清晰易懂的通用符号。用日常语言描述算法时，人们常常难以确切地表述实现的方法。这样的描述往往会遗漏细节，无法解释对特殊情况的处理，或者需要实现者猜测某些关键的过程。例如，如果你学过长除法（其中除数包含多位数字）的手动演算，你可能还记得计算时必须估计商的下一位数字，如果估计错误，则必须返回修正。
高级编程语言的发明和发展也在很大程度上消除了这一障碍。对于算法的发明者来说，以计算机程序的形式准确、完整、明确地表达算法现在已经司空见惯。
然而，人类读者在第一次看到算法时，可能无法从执行算法的计算机程序源代码中判断出算法的底层结构。对于人类读者来说，其中一个阅读难点是许多高级编程语言都基于同一种计算模型，在这种计算模型中，程序通过反复改变适当初始化的存储设备的状态来实现计算。理解这些变化的相互作用和累积效应往往是很困难的。
解决这一难点的办法是使用不同的计算模型。在纯函数程序设计语言中，人们认为计算是数学函数应用于参数值，并给出结果值。如果一个计算又长又复杂，那么可以用其他简单的函数来定义这个数学函数，而这些简单的函数又可以用其他更简单的函数来定义。但是，在每个级别上，这些函数都是无状态的，在给定相同的参数时，它们会返回相同的结果。一旦我们理解了函数能够根据输入参数返回计算结果的规则，就可以将函数视为具有固定和可预测行为的可靠组件。这种模块化的思想使得大型程序的设计和构建更简单，也使得人们能更容易地理解大型程序。
此外，函数程序设计语言使函数间交互的一般模式的识别和抽象变得更容易，因此人们可以在语言本身内描述和操作这些模式。函数本身可以作为参数传递给其他函数，也可以作为函数的结果值返回。使用高阶函数可以更容易地表述和理解常用的算法。
本书旨在向读者展示一系列广泛使用的算法，并用纯函数程序设计语言进行表达，从而帮助读者更好地阅读和理解它们的结构和操作。函数程序设计的其他优点也将在这一过程中展现出来。
我们用Scheme程序设计语言的一个纯函数版本来描述算法，附录B中描述了（afp primitives）库的实现。本书代码已经在《算法语言Scheme第7版修订报告》的Chibi-Scheme、
Larceny和Racket实现下做了详细测试，并可在作者的网站上下载，网址为http：unity.homelinux.netafp。
本书代码在GNU通用公共许可证（第3版或更高版本）下供读者自由使用（http：www.gnu.orgcopyleftgpl.html）。
致谢
感谢格林内尔学院给我写这本书提供了时间和资源；感谢我的同事Henry Walker、Samuel Rebelsky、Ben Gum、Janet Davis、Jerod Weinman、Peter-Michael Osera和Charlie Curtsinger的耐心和支持；感谢Karen McRitchie和Jeff Leep给予我的帮助；感谢莱斯大学给我提供了工作环境；感谢Springer-Verlag的编辑Wayne Wheeler和Ronan Nugent；感谢Matthias Felleisen和Shriram Krishnamurthi阅读了本书早期的手稿，并帮助我避免了许多错误。感谢大家的支持！
在这本书的各个草稿中纠正了几千个错误之后，我很不安地意识到，书中可能还存在许多错误。因此，我提前向读者表示感谢，感谢你们提醒我，让我可以在我的网站上更正这些错误。我会关注你发至reseda@grinnell.edu的电子邮件，并立即回复你。
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
