改变未来的九大算法

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

前言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第九章

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

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

结语 更多在你指尖的精灵

致 谢

注 释