改变未来的九大算法

　　计算机如何精确地传输海量数据，识别语音和笔迹；智能手机、平板电脑如何在几分之一秒内搜索整个页面；身处大数据时代的我们，究竟该如何应对变化莫测的世界。 计算机算法的底层建设为经济和产业发展提供了原始动力。在科技互联网时代，使用计算机和科技设备都不可避免地要依赖计算机科学的基础思想，而这些思想都诞生于20世纪。 《改变未来的九大算法》是一本科普读物，作者致力于将计算机科学的复杂思想为大众做深入浅出的解读。此书通过简明的语言和生动的例证，阐述了计算机王国的核心算法：搜索引擎、PageRank、公钥加密、纠错码、图形识别、数据压缩、数据库、数字签名等。在解释这些算法的同时，作者也向我们展示了充满科学原创精神的计算机世界：每一种算法的提出不但拓展了虚拟世界的领域，它同时也是人类智慧的彰显，可以被广泛运用于众多领域，以推动商业和社会文明的发展。

　　约翰·麦考密克（John MacCormick），计算机科学的领头人和导师。牛津大学博士，曾在惠普和微软从事研究工作。现任迪金森学院计算机学科的教授。多项专利所有者。

推荐序 计算机的算法之美      克里斯·毕晓普

前言

计算机日常运用的卓越思想

第一章 搜索引擎索引——在世界上最大的草垛中寻针

搜索引擎对我们的生活产生了深远影响。绝大多数人每天都进行多次搜索查询，但我们极少会停下来思考这个令人惊叹的工具是如何奏效的。

第二章 PageRank——让谷歌腾飞的技术

搜索引擎和网络垃圾制造者在进行一场军备竞赛。搜索引擎不断尝试完善算法，以便返回真实排名。

第三章 公钥加密——用明信片传输秘密

人们喜欢传谣，也喜欢了解秘密。而由于加密的目的就是传输秘密，所以我们都是天生的密码员。但人类进行秘密沟通要比计算机容易。本章将探究计算机的加密源头。

第四章 纠错码——自纠正的错误

没有纠错码，我们的计算机和通信系统会比现在慢很多，功能上弱许多，可靠性也会差很多。下次你在周末享受高清卫星电视时，不妨遐思一下这个令人回味的反讽：正是由于理查德·汉明在周末与早期计算机的斗争中产生了困扰，才有了我们现在周末的娱乐。

第五章 图形识别——从经验中学习

图形识别是人工智能的一部分，包括面部识别、物体识别、语音识别和笔迹识别等任务。本章描述的算法——最近邻分类器、决策树和神经网络，它们是图形识别系统的一些基础构件。不管你是否认为它们是真正的“智能”，你都将在未来数年中看到更多这些算法。

第六章 数据压缩——有益无害

几乎所有软件都是以压缩格式被下载——这意味着你下载和转移文件的速度，要比不压缩时快数倍。甚至当你对着电话讲话时，你的声音也经过了压缩：如果电话公司能在传输语音数据前进行压缩，它们就能对自己的资源实现超高利用率。

第七章 数据库——追求一致性的征程

我们将了解数据库背后三种美丽的基础思想：预写日志记录（write-ahead logging）、两阶段提交 （two-phase commit）和关系数据库（relational database）。这些思想让存储特定种类重要信息的数据库技术占据了绝对的主宰地位。

第八章 数字签名——这个软件究竟由谁编写

没有数字签名，我们所知的互联网就不会存在。数据仍可以通过加密安全交换，但要验证接收数据的来源就要困难得多。这一伟大思想和如此广泛的实际影响相结合，无疑让数字签名成为计算机科学中最伟大的成就之一。

第九章

什么可以计算——有些程序不可能存在

有些问题根本不可能通过计算机解决，不管计算机有多强大或人类程序员有多聪明。这些不可判定问题包括潜在的有用任务，如分析其他程序以发现它们是否会崩溃。

结语  更多在你指尖的精灵

致 谢

注 释