Swift常用算法经典计算机科学问题的Swift实现 pdf下载

《Swift常用算法 经典计算机科学问题的Swift实现》通过探究基本的编码技术和算法，进一步提高读者的Swift编程技能。读者在领略书中关于搜索、聚类、图等领域的示例时，脑海中将会重现一些已经淡忘的重要内容，并将找到“新”问题的经典解决方法。作者David Kopec具有出众的能力，将计算机科学的核心原理与诸如应用、数据、性能甚至通过工作面试等现实问题加以关联。
特色内容:
◆　宽度优先、深度优先、A*搜索算法
◆　约束满足问题
◆　使用图算法来解决问题
◆　神经网络、遗传算法等
◆　全部代码示例采用Swift 4.1编写

David Kopec是佛蒙特州伯灵顿的尚普兰学院计算机科学与创新专业的副教授。他是一名经验丰富的iOS开发人员，也是Dart for Absolute Beginners(Apress出版社，2014年出版)一书的作者。David拥有达特茅斯学院的经济学学士学位和计算机科学硕士学位。

目　　录

第1章 小型问题 1
1.1 斐波那契数列 1
1.1.1 尝试递归方法 1
1.1.2 利用基本情形 2
1.1.3 计算缓存技术 4
1.1.4 保持斐波那契简单 5
1.2 简单数据压缩 6
1.3 牢不可破的加密 9
1.3.1 数据排序 10
1.3.2 加密和解密 11
1.4 π的计算 12
1.5 汉诺塔 13
1.5.1 汉诺塔的建模 14
1.5.2 解决汉诺塔问题 15
1.6 实际应用 16
1.7 练习 17
第2章 搜索问题 19
2.1 DNA搜索 19
2.1.1 存储DNA 20
2.1.2 线性搜索 21
2.1.3 二分搜索 22
2.1.4 泛型示例 24
2.2 迷宫求解 25
2.2.1 生成随机迷宫 25
2.2.2 其他迷宫细节 26
2.2.3 深度优先搜索 28
2.2.4 广度优先搜索 32
2.2.5 A*搜索 34
2.3 传教士和食人族 39
2.3.1 问题表示 39
2.3.2 问题解决 42
2.4 实际应用 43
2.5 练习 44
第3章 约束满足问题 45
3.1 构建约束满足问题的解决 框架 46
3.2 澳大利亚地图着色问题 50
3.3 八皇后问题 53
3.4 单词搜索问题 55
3.5 SEND+MORE=MONEY问题 59
3.6 电路板布局问题 61
3.7 实际应用 61
3.8 练习 62
第4章 图问题 63
4.1 构建图框架 65
4.1.1 Edge的具体实现 70
4.1.2 Graph的具体实现 70
4.2 寻找最短路径 73
4.2.1 定义路径 73
4.2.2 广度优先搜索(BFS)回顾 74
4.3 最小化网络建设成本 77
4.3.1 权 77
4.3.2 寻找最小生成树 82
4.4 在带权图中寻找最短路径 88
4.5 实际应用 93
4.6 练习 94
第5章 遗传算法 95
5.1 生物学背景知识 95
5.2 预备知识 96
5.3 通用遗传算法 98
5.4 简单测试 105
5.5 重新讨论SEND+MORE=MONEY问题 108
5.6 遗传算法面临的挑战 112
5.7 实际应用 112
5.8 练习 113
第6章 k-均值聚类算法 115
6.1 预备知识 115
6.2 k-均值聚类算法 120
6.3 基于年龄和地理经度的州长聚类算法 124
6.4 k-均值聚类问题及其扩展 128
6.5 实际应用 129
6.6 练习 130
第7章 简单神经网络 131
7.1 来自生物学的灵感 131
7.2 人工神经网络 133
7.2.1 神经元 133
7.2.2 层 134
7.2.3 反向传播 135
7.2.4 整体情况 137
7.3 预备知识 138
7.3.1 借助随机化 138
7.3.2 快速算法 140
7.4 激活函数 141
7.5 构建神经网络 142
7.5.1 实现神经元 143
7.5.2 层的实现 144
7.5.3 神经网络的实现 146
7.6 分类问题 149
7.6.1 归一化数据 149
7.6.2 经典的iris(鸢尾属植物)数据集 150
7.6.3 葡萄酒分类问题 154
7.7 神经网络问题及其扩展 156
7.8 实际应用 157
7.9 练习 158
第8章 其他问题 159
8.1 背包问题 159
8.2 旅行推销员问题 163
8.2.1 简单方法 164
8.2.2 深层考虑 170
8.3 电话号码助记符 170
8.4 井字棋 172
8.4.1 管理状态 173
8.4.2 极小极大算法 175
8.5 实际应用 179
8.6 练习 180
附录A 术语表 181
附录B 更多资源 187
附录C Swift简史 193

前 言

感谢购买《Swift常用算法 经典计算机科学问题的Swift实现》。Swift正处于一个激动人心的发展阶段。随着这门语言的日趋稳定和普及，有必要让传统的计算机科学教育内容接触到这门语言。这本中级编程书籍所涉及的问题将有助于经验丰富的程序员深入学习Swift语言，也能帮助新手程序员加快自己的计算机技术学习进度。《Swift常用算法 经典计算机科学问题的Swift实现》涵盖大量用以解决问题的技术，每个人都能够从中找到自己所需。
《Swift常用算法 经典计算机科学问题的Swift实现》不是对Swift语言的基本介绍。苹果公司出版了一本优秀的免费书籍来满足入门需求 。相反，《Swift常用算法 经典计算机科学问题的Swift实现》假设读者已经掌握Swift语法的基本知识，但不要求精通Swift。事实上，《Swift常用算法 经典计算机科学问题的Swift实现》的内容基于以下假设：可以作为学习材料来帮助人们精通Swift。另一方面，《Swift常用算法 经典计算机科学问题的Swift实现》不适合初学者使用。
为什么选择Swift
苹果公司的Swift是一门令人兴奋的新型编程语言，它在面向对象和函数范式之间建立联系。Swift的创造者在这两个领域之间取得了惊人的平衡，许多人甚至认为达到了最佳效果。Swift通过苹果公司的开发工具获得了广泛部署，它符合现代的语法规范，融合了其他语言的优秀特性，拥有精心设计的范式平衡，具有作为iOS和Mac应用主要开发语言的发展前景。以上种种因素，决定了现在是学习Swift的好时机。
苹果公司宣称Swift是第一门面向协议的语言，这是由于其强大的协议特性集合以及该集合在其标准库中得到广泛使用 。然而，许多长期从事Objective-C和Java开发的人缺乏函数式编程经验，更不用说面向协议的编程技术。与此同时，一些函数式程序员进入Swift社区，他们尝试按照自己在Haskell或Scheme中的编程方式来解决问题，有时缺少更优雅的、面向对象的解决方案。
《Swift常用算法 经典计算机科学问题的Swift实现》的目的是通过使用Swift解决资深程序员(以及新程序员)应该熟悉的经典问题，而不是固守单一的语法范式，充当这些领域之间的桥梁。因而，读者对于各个领域的内容都会有所体验。不同领域的结合是掌握Swift的正确途径，而搭建桥梁则是社区前进的方式。
什么是经典的计算机科学问题
有人说计算机对于计算机科学而言，就像望远镜对于天文学一样。如果是这样的话，那么编程语言就像望远镜的镜头吗？不管怎样比拟，《Swift常用算法 经典计算机科学问题的Swift实现》中“计算机科学问题”这个术语是指“计算机科学本科课程中的典型编程问题”。
一些提供给新程序员解决的编程问题，无论是在攻读(计算机科学、软件工程等)学士学位的课堂环境里，还是在中级编程教材(例如，关于人工智能或算法的入门教材)里涉及，这些问题司空见惯，足以被视为“经典”。《Swift常用算法 经典计算机科学问题的Swift实现》就是这些问题的汇聚。
这包括通过数行代码即可解决的琐碎问题，乃至需要跨越多章内容构建系统的复杂问题。有些问题涉及人工智能，还有一些问题只需要常识。有些问题存在于现实世界之中，而有些问题则是凭空想象出来的。
《Swift常用算法 经典计算机科学问题的Swift实现》涵盖的问题类型
第1章介绍多数读者可能都熟悉的问题解决技巧，诸如递归、记忆法/计算缓存和模拟等内容是后面各章要探讨的其他技术的基本构建模块。
第2章重点说明搜索问题。搜索主题涵盖广泛，甚至可以将《Swift常用算法 经典计算机科学问题的Swift实现》中的大部分问题都置于其范畴之内。第2章介绍最基本的搜索算法，包括二分搜索、深度优先搜索、广度优先搜索和A*搜索。这些算法在《Swift常用算法 经典计算机科学问题的Swift实现》的其余部分都会重复用到。
第3章构建一类广泛问题的解决框架，这类问题由具有约束条件且具有有限定义域的变量加以抽象定义，包括经典的“八皇后问题”“澳大利亚地图着色问题”和密码算法“SEND+MORE=MONEY”。
第4章探索图算法。对于门外汉来说，这类算法的适用性极为广泛。本章将构建图的数据结构，然后用它来解决多个经典的优化问题。
第5章探索遗传算法，这种技术与书中介绍的大多数技术相比具有更多的不确定性，但有时可以解决传统算法无法在合理的时间内解决的问题。
第6章涵盖k-均值聚类，这或许是《Swift常用算法 经典计算机科学问题的Swift实现》中在算法方面涉及最具体的一章。这种聚类技术实现简单，易于理解，具有广泛的适用性。
第7章阐述神经网络的概念，并让读者对于极简单的神经网络有所感受。本章并不寻求能够全面涵盖这个令人兴奋、不断发展的领域。
最后，第8章讨论不适于编入前面各章的一些值得关注的有趣问题。
《Swift常用算法 经典计算机科学问题的Swift实现》的目标读者
《Swift常用算法 经典计算机科学问题的Swift实现》既适合中级程序员，也适合经验丰富的资深程序员。想学习Swift的专业程序员会从《Swift常用算法 经典计算机科学问题的Swift实现》中发现他们在计算机科学或编程教育中熟知的问题。编程新手将通过自己选定的Swift语言接触到这些经典的问题。准备接受编程面试的开发人员可能会发现《Swift常用算法 经典计算机科学问题的Swift实现》是很有价值的备用材料。
除了专业程序员之外，对Swift感兴趣的计算机科学专业大学生也可能会发现《Swift常用算法 经典计算机科学问题的Swift实现》很有帮助。它没有试图严谨地介绍数据结构和算法——它并非数据结构和算法教科书——书中没有big-O符号的证明或广泛运用。相反，《Swift常用算法 经典计算机科学问题的Swift实现》被定位为易于使用、可亲手实践解决问题的技术教程，而这些技术应该是数据结构、算法和人工智能课程的最终产物。
再次重申，《Swift常用算法 经典计算机科学问题的Swift实现》假定读者具备Swift语法和语义的基本知识。没有编程经验的读者很难从《Swift常用算法 经典计算机科学问题的Swift实现》中获益。没有接触过Swift的程序员也肯定会大费周章。换句话说，《Swift常用算法 经典计算机科学问题的Swift实现》可以称为又一部关于Swift的极好书籍。
Swift的版本控制和工具
《Swift常用算法 经典计算机科学问题的Swift实现》中的源代码遵循Swift 4.1版本规范。该版本与Xcode 9.3一起由苹果公司于2018年初发布。书中代码的GitHub库的网址是https://github.com/davecom/
ClassicComputerScienceProblemsInSwift。
《Swift常用算法 经典计算机科学问题的Swift实现》中的大部分源代码能够原封不动地在Linux(以及移植了Swift的其他平台)上运行，因为它们只依赖于Foundation(而不是AppKit/UIKit)。源代码文件作为Xcode的Swift基础组成部分进行发布，但是其中包含的原始.swift文件可以提取出来在Linux上使用。跨平台兼容性是《Swift常用算法 经典计算机科学问题的Swift实现》的目标之一，但对大多数读者来说，Mac之上的便利性是更大的目标。
《Swift常用算法 经典计算机科学问题的Swift实现》没有说明如何使用Xcode、构建Swift项目或使用Playground。关于这些主题，网上和纸质出版物中都有很多优质资源。《Swift常用算法 经典计算机科学问题的Swift实现》假定读者已具备完成这些任务的能力。
没有图形，也没有用户界面代码
《Swift常用算法 经典计算机科学问题的Swift实现》并不讲解UIKit或AppKit，书中的例子也不需要用到它们。《Swift常用算法 经典计算机科学问题的Swift实现》中的示例不会产生图形化结果，这是因为我们希望能够使用尽可能简明易读的解决方案来解决书中提出的问题。很多时候，处理图形会造成阻碍，或者会极大增加各种解决方案在阐释技术或算法时的复杂性。
此外，为了在Linux上实现Swift的跨平台兼容性，也不能使用UIKit和AppKit。在《Swift常用算法 经典计算机科学问题的Swift实现》撰写之际，只有Foundation被移植到Linux上。书中给出的解决方案很大程度上只依赖于Swift标准库，在标准库功能薄弱的领域则将Foundation 作为补充。
《Swift常用算法 经典计算机科学问题的Swift实现》并不讲授如何编写完整的应用程序，但会介绍使用Swift进行软件开发的基础知识。书中的内容仅限于《Swift常用算法 经典计算机科学问题的Swift实现》主题范围。