算法精粹 经典计算机科学问题的Python实现

1.计算机科学和算法问题具有非常广泛的应用领域，而且经常出现在程序员面试题中； 2.本书所采用的Python语言是当前最流行的程序设计语言，基于Python3.7版本； 3.将计算机科学与应用程序、数据、性能等现实问题深度关联。 看似新颖或独特的计算机科学问题，往往根植于经典算法、编码技巧和工程原理。经典方法仍然是解决这些问题的最佳途径！理解用Python实现的这些技巧，可以扩展你在Web开发、数据处理、机器学习等方面获得成功的潜力。 本书详细介绍一些经过时间验证的方案、练习和算法，以提升你解决计算机科学问题的技能。从二分搜索算法这种简单的任务，到用k 均值聚类算法对数据进行聚类，很多编码挑战都将迎刃而解。破解将计算机科学与应用、数据、性能等真实世界相关联的问题，会让你特别享受那种满足感，甚至可以让你在下一次工作面试中应对自如！ 本书主要内容 ● 搜索算法。 ● 图的常见技术。 ● 神经网络。 ● 遗传算法。 ● 对抗性搜索。 ● 始终使用类型提示。 本书适合中级Python 程序员阅读。

本书是一本面向中高级程序员的算法教程，借助Python语言，用经典的算法、编码技术和原理来求解计算机科学的一些经典问题。全书共9章，不仅介绍了递归、结果缓存和位操作等基本编程组件，还讲述了常见的搜索算法、常见的图算法、神经网络、遗传算法、k均值聚类算法、对抗搜索算法等，运用了类型提示等Python高级特性，并通过各级方案、示例和习题展开具体实践。本书将计算机科学与应用程序、数据、性能等现实问题深度关联，定位独特，示例经典，适合有一定编程经验的中高级Python程序员提升用Python解决实际问题的技术、编程和应用能力。

大卫·科帕克（David Kopec）是香普兰学院（Champlain College）的计算机科学与创新专业助理教授，该学院位于美国佛蒙特州的伯灵顿市。他是一位经验丰富的软件开发人员，也是Classic Computer Science Problems in Swift和Dart for Absolute Beginners的作者。他拥有达特茅斯学院（Dartmouth College）的经济学学士学位和计算机科学硕士学位。

第1章几个小问题1
1.1斐波那契序列1
1.1.1尝试第一次递归1
1.1.2基线条件的运用3
1.1.3用结果缓存来救场4
1.1.4自动化的结果缓存5
1.1.5简洁至上的斐波那契6
1.1.6用生成器生成斐波那契数7
1.2简单的压缩算法7
1.3牢不可破的加密方案12
1.3.1按顺序读取数据12
1.3.2加密和解密13
1.4计算(15
1.5汉诺塔15
1.5.1对塔进行建模16
1.5.2求解汉诺塔问题17
1.6现实世界的应用19
1.7习题20
第2章搜索问题21
2.1DNA搜索21
2.1.1DNA的存储方案22
2.1.2线性搜索23
2.1.3二分搜索24
2.1.4通用示例26
2.2求解迷宫问题28
2.2.1生成一个随机迷宫29
2.2.2迷宫的其他函数30
2.2.3深度优先搜索31
2.2.4广度优先搜索35
2.2.5A*搜索39
2.3传教士和食人族44
2.3.1表达问题45
2.3.2求解47
2.4现实世界的应用48
2.5习题49
第3章约束满足问题51
3.1构建约束满足问题的解决框架52
3.2澳大利亚地图着色问题55
3.3八皇后问题58
3.4单词搜索60
3.5字谜（SEND+MORE=MONEY）63
3.6电路板布局65
3.7现实世界的应用66
3.8习题67
第4章图问题69
4.1地图就是图69
4.2搭建图的框架71
4.3查找最短路径77
4.4最小化网络构建成本79
4.4.1权重的处理79
4.4.2查找最小生成树83
4.5在加权图中查找最短路径89
4.6现实世界的应用95
4.7习题96
第5章遗传算法97
5.1生物学背景知识97
5.2通用的遗传算法98
5.3简单测试105
5.4重新考虑SEND+MORE=MONEY问题107
5.5优化列表压缩算法111
5.6遗传算法面临的挑战113
5.7现实世界的应用114
5.8习题115
第6章k均值聚类117
6.1预备知识117
6.2k均值聚类算法119
6.3按年龄和经度对州长进行聚类124
6.4按长度聚类迈克尔·杰克逊的专辑128
6.5k均值聚类算法问题及其扩展130
6.6现实世界的应用131
6.7习题131
第7章十分简单的神经网络133
7.1生物学基础133
7.2人工神经网络135
7.2.1神经元135
7.2.2分层136
7.2.3反向传播137
7.2.4全貌139
7.3预备知识140
7.3.1点积140
7.3.2激活函数140
7.4构建神经网络142
7.4.1神经元的实现142
7.4.2层的实现143
7.4.3神经网络的实现145
7.5分类问题148
7.5.1数据的归一化148
7.5.2经典的鸢尾花数据集149
7.5.3葡萄酒的分类152
7.6为神经网络提速155
7.7神经网络问题及其扩展156
7.8现实世界的应用157
7.9习题157
第8章对抗搜索159
8.1棋盘游戏的基础组件159
8.2井字棋161
8.2.1井字棋的状态管理161
8.2.2极小化极大算法164
8.2.3用井字棋测试极小化极大算法167
8.2.4开发井字棋AI168
8.3四子棋169
8.3.1四子棋游戏程序170
8.3.2四子棋AI175
8.3.3用α-β剪枝算法优化极小化极大算法177
8.4超越α-β剪枝效果的极小化极大算法改进方案178
8.5现实世界的应用179
8.6习题179
第9章其他问题181
9.1背包问题181
9.2旅行商问题186
9.2.1朴素解法186
9.2.2进阶191
9.3电话号码助记符191
9.4现实世界的应用193
9.5习题194
附录A术语表195
附录B其他资料201
附录C类型提示简介205