德杰的九大算法 时刻，会让解释这些算法成为令人愉悦的经历，我希望你也能有此感受。 因为我会用到“把戏”(tick)这个词很多次，需要指出的是，我并非指 那些卑劣或骗人的把戏—那种孩子可能会用在弟弟或妹妹身上的把戏。 相反，本书中的把戏类似于交易诀窍或魔术：为达成目标而采用的聪明技 巧，否则目标很难或不可能达成。 因此，根据直觉，我选出了自认为是计算机科学世界中最精巧、最神 奇的把戏。在英国数学家高德菲·哈罗德·哈代(G.H.Hardy)的《 个数学家的辩白》(A Mathematician3 Apology）中，作者试图向公众解释 数学家从事数学的原因：“美是第一道测试：丑陋的数学在这个世界中无 永存之地。”这道美的测试也适用于计算机科学中蕴含的理论思想。因此， 选取在本书中出现的算法的最后一条标准，就是哈代的一也许可以这么 称呼—美的测试：希望我至少能成功地向读者展示部分美一我在每个 算法中感觉到的美。 接下来谈谈我选择展示的这些算法。搜索引擎的巨大影响，也许是算 法技术影响所有计算机用户最明显的例子，我自然也将部分互联网搜索的 核心算法收入了本书中。第二章描述了搜索引擎如何使用索引寻找与请求 的文件，而第三章则解释了网页排名(PageRank)算法一谷歌公司为 保证匹配度最高的文件出现在搜索结果列表顶部的原始算法。 即便我们不经常想这件事情，绝大多数人也能意识得到，为提供出人 意料的强大搜索结果，搜索引擎使用着一些深邃的计算机科学思想。相 反，其他一些伟大的算法也经常被用到，但计算机用户对此甚至都没有 意识到。第四章描述的公钥加密(public key cryptography）就是这样一 种算法。用户每次访问一个安全网站（地址以htps而非http开头），用 户都会用到公钥加密的一个方面一也就是众所周知的密钥交换(ky exchange)-一来展开一段安全对话。第四章解释了密钥交换过程的实现 原理。 第五章的主题是纠错码(error correcting codes),这是我们经常使用 PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
第一章前言一—计算机日常运用的卓越思想有哪些 但却没有意识到的另一类算法。事实上，纠错码极有可能是有史以来唯 一一个使用次数最频繁的伟大算法。纠错码可以让计算机识别并纠正在储 存或传输数据中出现的错误，而不必依靠备份或再次传输。纠错码无处不 在：它们被用于所有硬盘驱动器、众多网络传输、CD和DVD,甚至还存 在于一些计算机的内存。不过，纠错码的能力太强了，以至于我们意识不 到它们存在。 第六章稍微有点特殊，介绍了图形识别算法(pattern recognition algorithm)。图形识别算法也能进入伟大的计算机科学思想榜单，但却违 背了第一条标准：要被普通计算机用户每天用到。图形识别属于计算机 识别高度可变信息一如笔迹、讲话和人脸—的技术。事实上，在2 世纪的第一个十年，绝大多数日常计算并没有用到这些技术。但在2011 年，图形识别的重要性急刷增大：配备小型屏幕键盘的移动设备需要自 动纠错，平板设备必须识别手写输入，而且所有这些设备（特别是智能 手机)越来越趋向于语音操作。一些网站甚至使用图形识别来决定向用 户展示哪种广告。另外，我对图形识别也有偏好，因为它是我的研究领 域。因此，第六章描述了3种最有趣、最成功的图形识别技术：最近邻分 类器(nearest-neighbor classifier)、决策树(decision tree)以及神经网络 (neural network)。 第七章讨论了压缩算法。压缩算法组成了另一组使计算机变成我们指 尖精灵的伟大思想。计算机用户的确会时不时地直接进行压缩，也许是为 了节省磁盘空间，也许是为了缩减照片容量，以便用电子邮件寄出。不过 在私底下，压缩使用的频率要更高：我们根本没有意识到，我们的下载或 上传也可以通过压缩以节省带宽，而数据中心通常会压缩消费者的数据以 降低成本。电子邮件提供商提供给你的5GB空间，经压缩后很有可能只 占据电子邮件提供商5GB空间的很小一部分。 第八章讲到了数据库中运用的一些基础算法。这一章侧重为实现一 致性一指一个数据库中的关系不互相冲突—而采用的聪明技巧。没
泰的九大算法 有这些精巧的技术，我们的绝大部分在线生活（包括网络购物以及通过 Facebook之类的社交网站进行互动)就会消亡于众多计算机错误中。这 章解释了一致性真正的问题是什么，以及计算机科学家是如何解决这一问 题的。前提是不牺牲我们所期望的在线系统拥有的高效性。 在第九章，我们会了解理论计算机科学无可争议的瑰宝之一：数字签 名。乍看之下，用数字形式“签署”一份电子文档似乎不可能。你也许会 想，这种签名必须由数字信息组成，而任何想要伪造签名的人都可以毫不 费力地拷贝这些信息。这一悖论的解决方案，就是计算机科学取得的最令 人瞩目的成就之一 第十章采取了截然不同的视角：与其描述一个已经存在的伟大算法， 我们不如去了解一个假如存在则必然会伟大的算法。不过我们会震惊地 发现，这个特别伟大的算法不可能存在。这表明计算机解决问题的能力 存在一些绝对极限，而我们将简单地从哲学和生物学角度探讨这一结果的 应用。 第十一章我们会总结伟大算法的一些共性，花些时间畅想未来会怎样。 会有更多伟大算法出现吗？或者说，我们已经发现了所有的伟大算法？ 在此，不得不提前说一下本书的风格。任何科普作品都必须清楚地告 知来源，但引用会破坏文本的流畅性，并让读者产生学术的感觉。由于可 读性和易读性是本书的首要目标，所以本书正文不会出现引用。不过，我 清楚地记录了所有来源，并在本书末尾的“来源和延伸阅读”板块中列 出，并时不时附上拓展评论。这个板块还列出了一些额外材料，以便感兴 趣的读者能去寻找更多和计算机科学中伟大算法有关的东西。 既然提前说了本书的风格，我还要谈谈本书书名中采取的少量诗化。 本书无疑是革命性的，但真的有九种算法吗？这一说法值得探讨，因为要 取决于有多少算法被算作单独算法。让我们来算下“九”是怎么来的。除 了前言和结论两章外，本书还有九章，每一章都介绍了对一种计算任务产 生革命性影响的算法，例如加密、压缩、图形识别。因此，书名中的“九 PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
第一章前言—计算机日常运用的卓越思想有哪些 大算法”实际上指的是处理这九种任务的九类算法。 为什么我们要关注这些伟大的算法？ 希望对这些迷人思想的快速总结能让你渴望深入了解它们的运行方 式。不过，也许你仍然在思考：本书的终极目标是什么？让我简短地说下 本书的真正目的。这本书绝不是一本问答式操作手册。在读完本书后，你 不会成为计算机安全方面的专家，也不会成为人工智能或其他领域的专 家。你也许能学到一些有用的技能，这倒是真的。比如：你会对如何检查 “安全”网站凭证以及“已签名”软件包了解更多，你能针对不同任务在 有损和无损压缩之间做出明智选择；而且通过理解搜索引擎索引和排名技 术的某些方面，你能更高效地使用搜索引擎。 在读完本书后，你不会成为一名更加熟练的计算机用户。但你会更加 珍视每天在所有计算设备上不停使用的思想的美。 为什么这是件好事？我用类比的方式来说明。我肯定不是一位天文学 专家一事实上，我在这个项目上相当无知，我想知道更多。但每当我注 视夜空，我知道的少量天文学知识增强了我对这一经验的享受。有时，我 对自己看到事物的理解，让我产生了一种满足和惊奇的感觉。希望在读完 本书后，你在使用计算机时也能经常获得同样的满足和惊奇之感，这也是 我殷切的希望。你将真正珍视我们时代最常见、最神秘的黑盒子：你的个 人电脑，你指尖的精灵
PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com