pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 改变未来的九大算法 [美]约翰·麦考密克 著 管策 译 中信出版集团 pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 目录 所获赞誉 序 前言 计算机日常运用的卓越思想 第一章 搜索引擎索引 ——在世界上最大的草垛中寻针 第二章 PageRank ——让谷歌腾飞的技术 第三章 公钥加密 ——用明信片传输秘密 第四章 纠错码 ——自纠正的错误 第五章 图形识别 ——从经验中学习 第六章 数据压缩 ——有益无害 第七章 数据库 ——追求一致性的征程 第八章 数字签名 ——这个软件究竟由谁编写 第九章 并非万能的算法 ——有些程序不可能存在 结语 更多在你指尖的“精灵” 注释 致谢 pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 所获赞誉 荣获美国出版商协会“2012年计算机与信息科学最佳专业/学术图 书奖” 作者解释了数亿人每天使用的一些算法，不是如算术和排序这类简 单的算法，而是更复杂的事情——如何确定网页的重要性，以及无法被 计算的问题。我强烈推荐这本书。 ——查克·塞克（Chuck Thacker）， “图灵奖”得主 长久以来，没有哪本书能让我像十几岁时阅读霍金和费曼的书时那 样让我兴奋，而这本书做到了，它提醒了我，为什么我喜欢计算机科 学。 ——安德鲁·菲茨吉本（Andrew Fitzgibbon）， “艾美奖”得主（相机软件开发者） 作者揭示了计算机科学家对算法着迷的原因：它们如此实用、美观 和优雅。 ——保罗·柯曾（Paul Curzon）， 《科学》（Science） 一本关于关键算法的指南，阅读起来愉悦且轻松。它传达出一种奇 妙的感觉——让电脑发挥魔力的是美丽的科学，而非技术。 ——安德烈亚斯·特拉辛格（Andreas Trabesinger）， 《自然物理学》（Nature Physics） pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 尽管人们对计算机充满兴趣，但并不了解其核心思想。这本书在向 大众展示计算机科学这一艰巨的任务中取得了非凡的成就。 ——欧内斯特·戴维斯（Ernest Davis）， SIAM News（美国工业和应用数学学会的新闻期刊） 大多数人对电子支付的安全性，或者电影如何被“塞进”光盘知之甚 少，也不太关心，但作者认为它们富含惊人的独创性和创造力。 ——罗伯特·马修斯（Robert Matthews）， 《BBC聚焦》（BBC Focus，英国一本关于科学和技术的月刊） 作者用日常类比巧妙地解读核心算法，这对没有数学背景的读者来 说很有用。想钻研算法的数学和计算机科学的学生也会感到受益颇 深……这本书应该被图书馆珍藏。 ——阿特·吉特尔曼（Art Gittleman）， 就职于美国数学协会（MAA） 计算机专业人士和非专业人士都会对这本书感兴趣。作者并没有试 图“用科学迷惑我们”，也没有“卖弄”其数学才能。相反，他采用了我们 都能理解的简单类比。比如，作者用混合彩色颜料来类比公钥密码的原 理，这非常精彩。 ——克莱夫·马克斯菲尔德（Clive Maxfield）， 《电子工程时报》（EE Times） 这本书适合对信息系统的工作原理感兴趣的人。 ——约翰·吉尔比（John Gilbey）， 就职于泰晤士高等教育出版社（Times Higher Education） pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 序 计算机行业正在改变我们的社会，正如物理学和化学在前两个世纪 给社会带来的巨大改变一样。的确，数字技术几乎影响甚至颠覆了我们 生活的方方面面。鉴于计算机行业对现代社会的重要性，人们对让这一 切成为可能的基本概念却知之甚少，这显得有点儿自相矛盾。对这些概 念的研究是计算机科学的核心，而麦考密克的这本新书则是向大众展示 这些概念的少数书籍之一。 人们较少视计算机科学为一门学科，其中一个原因是，高中极少开 设计算机科学这门课程。虽然人们通常认为要强制开设物理学和化学这 两门基础课程，但作为独立学科的计算机科学，却通常只在大学阶段才 被开设。况且，学校讲授的“计算机”或“信息与通信技术”知识，通 常只是略高于使用软件的技能训练。因此，学生们认为计算机学科枯燥 也并不意外；而他们在娱乐和通信上使用计算机技术的天然热情，也因 为实现这类技术的学术深度而有所消退。这些问题被认为是导致过去10 年大学计算机科学专业学生人数下降一半的主要原因。考虑到数字技术 对现代社会的极度重要性，让人们重新领略计算机科学的奇妙之处已经 刻不容缓。 2008年，我很荣幸地被选为第180届英国皇家科学院圣诞讲座 （Royal Institution Christmas Lectures）的演讲人，该讲座由 迈克尔·法拉第（Michael Faraday）于1826年发起。2008年圣诞讲 座的主题首次涉及计算机科学。在准备这些讲座时，我花了很多时 间来思考如何向大众解释计算机科学，却发现能提供解决这一需求 问题的资源很少，几乎没有关于计算机科学的畅销书。因此，我特 别高兴能看到麦考密克的这本书。 麦考密克在面向大众介绍计算机科学的复杂思想方面做得非常好。 这其中的许多思想极其新颖，仅从这点上来看，它们就很值得关注。举 个例子：电子商务的爆炸式增长之所以成为可能，是因为它具备了能在 pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 互联网上秘密、安全地发送机密信息（如信用卡卡号）的能力。数十年 来，建立在“开放”通道上的保密通信被认为是一个科学难题。当人们 发现解决方法时，他们才发觉保密通信是精美的艺术。而麦考密克也以 精确的类比进行了解释，读者无须拥有计算机科学知识就能理解。这些 优点使这本书在科普读物领域做出了不可估量的贡献，我极力推荐这本 书。 克里斯·毕晓普（Chris Bishop） 微软剑桥研究院资深科学家 大不列颠皇家学院副院长 爱丁堡大学计算机科学教授 pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 前言 计算机日常运用的卓越思想 计算机科学中的伟大思想是如何诞生的？以下遴选部分思想进行介 绍： ● 20世纪30年代，在第一台数字计算机被发明以前，一位英国 天才开创了计算机科学研究领域。之后，这位天才还继续证明了， 不管未来建造的计算机运行多快、功能多强大、设计得多好，仍旧 有一些问题将是计算机不能解决的。 ● 1948年，一位供职于电话公司的科学家发表了一篇论文，由 此开创了信息理论研究领域。这位科学家的工作让计算机能以完美 的精确度传输信息，即便大部分数据都因为被干扰而遭受破坏。 ● 1956年，一群学者在达特茅斯（Dartmouth）举行会议。这 次会议的目标很清晰，也很大胆，那就是开创人工智能领域的研 究。在取得了许多重大成功，也经历了无数次失望之后，我们仍期 待出现一个真正的智能计算机程序。 ● 1969年，IBM（国际商业机器公司）的一名研究人员发明了 一种在数据库中组织信息的先进方法。目前，绝大多数在线交易都 使用该技术存储及检索信息。 ● 1974年，英国政府秘密通信实验室的研究人员发明了一种让 计算机实现安全通信的方法，即另一台计算机可以查看在计算机之 间交换的所有信息。这些研究人员为政府保密所限——不过幸运的 是，三名美国专家独立开发并拓展了这项重大发明，为互联网上所 有的安全通信打下了基础。 ● 1996年，斯坦福大学的两名博士生决定联手搭建一个互联网 搜索引擎。几年后，他们创办了谷歌公司——互联网时代的第一个 数字“巨头”。 pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 我们在享受21世纪技术惊人增长的同时，使用计算机设备——不管 是现有最强大的一组机器，还是最新、最时尚的手持设备——不可避免 地要依赖计算机科学的基础思想，而这些思想都诞生于20世纪。想一 想：你今天做过什么令人印象深刻的事情吗？好吧，这个问题的答案取 决于你怎么看。也许是你搜索了包含数十亿份文档的资料库，从中选出 两三份与你的需求最相关的文档？即便有能够影响所有电子设备的电磁 干扰，你在存储或传输数百万条信息的过程中，也没犯一点儿错误？你 是否成功地完成了一次在线交易，即便同时有成千上万名消费者在访问 同一个服务器？你是否在能够被其他数十台计算机嗅探到的线路中传输 了一些机密信息（比如信用卡卡号）？你是否运用过压缩的魔力，将数 兆的照片压缩成更易于管理的大小，以便附在电子邮件中发送？你是否 在手持设备上触发了人工智能，以自动纠正你在手持设备的小巧键盘上 输入的内容？ 这些令人印象深刻的壮举都有赖于之前提到的伟大发明或发现。然 而，绝大多数计算机用户每天都会多次运用这些天才的想法，却从没有 意识到！本书旨在向大众解释这些观点——我们每天使用的计算机科学 的伟大思想。在解释每一个观点时，我都假设读者不了解有关计算机科 学的任何知识。 算法：指尖“精灵”的构件 到目前为止，我一直在谈计算机科学的伟大“思想”，但计算机科 学家们会将许多重要思想形容为“算法”。那么思想和算法之间有什么 区别？究竟什么是算法？这一问题最简单的答案是，算法是一张精确的 处方，它按顺序详细列出了解决一个问题所需要的具体步骤。我们小时 候在学校学到的一种算法就是很好的例子：将两个大数字相加的算法。 如下例所示。这个算法涉及一连串的步骤，开始的步骤如下：“首先， 将两个数的最末位数相加，写下结果的最末位数，将剩下的数放到左侧 的下一栏；接着，将下一栏的数相加，再将除了结果末位数的数字和前 一栏余下的数相加……”依此类推。 pdf资源网 http://pdf.018zy.com 爱书网 http://www.aibook01.com 图1 将两个数字相加的算法的前两步 请注意算法步骤近乎机械化的感觉。事实上，这是算法的关键特点 之一：每步都必须绝对精确，没有任何人类意图或推测掺杂其中。这 样，每个完全机械化的步骤才能被编入计算机。算法的另一个重要特点 是，不管输入什么，算法总能运行。我们在学校学到的相加算法就拥有 这一特性：不管你想把哪两个数相加，运用算法最终都会得出正确答 案。比如，用这一算法将两个长达1 000位的数相加，你肯定能得到答