改变未来的九大算法

章节摘录

第一章 前言：计算机日常运用的卓越思想有哪些？此乃小技……为诗之诀在有气、有势、有情、有韵、有起、有承、有转、有合。——威廉姆•莎士比亚，《爱的徒劳》（Love’s Labour’s Lost）朱生豪译计算机科学中的伟大思想是如何诞生的？以下遴选部分思想进行介绍：•20世纪30年代，在第一台数字计算机被搭建出来以前，一名英国天才开创了计算机科学领域。之后，这位天才继续证明，不管未来建造的计算机运行多快，功能多强大，设计得多好，有一些问题都不是计算机能解决的。•1948年，一名供职于电话公司的科学家发表了一篇论文，开创了信息理论领域。这位科学家的工作让计算机能以完美的精确度传输消息，即便大部分数据都被干扰所破坏。•1956年，一群学者在达特茅斯举行会议。这次会议的目标很清晰，也很大胆，那就是开创人工智能领域。在取得了许多重大成功以及经历了无数失望之后，我们仍在等待出现一个真正的智能计算机程序。•1969年，IBM公司的一名研究人员发明了一种将信息组织进数据库中的优雅方法。目前，绝大多数在线交易都使用该技术存储及检索信息。•1974年，英国政府秘密通信实验室的研究人员们发明了一种让计算机安全通信的方法，即便另一台计算机能查看在计算机之间通过的所有东西。这些研究人员为政府保密所限——不过幸运的是，三名美国专家独立开发并拓展了这项重大发明，为互联网上所有的安全通信打下了基础。•1996年，两名斯坦福大学博士生决定联手搭建一个互联网搜索引擎。几年后，他们创办了谷歌公司——互联网时代第一个数字巨头。在我们享受21世纪技术令人震惊的增长的同时，使用计算机设备——不管是现有最强大的一组机器或是最新、最时尚的手持设备——都不可避免地要依赖计算机科学的基础思想，而这些思想都诞生于20世纪。想一想：你今天做过什么令人印象深刻的事吗？好吧，这个问题的答案取决于你怎么看。也许你搜索了包含数十亿份文档的语料库，从中选出两到三份和你的需求最相关的文档？存储或传输了数百万块信息，即便有能影响所有电子设备的电磁干扰也没犯一点错误？你是否成功地完成了一次在线交易，即便同时有成千上万名消费者在访问同一个服务器？你是否在能被其他数十台计算机嗅探到的线路中传输了一些机密信息（比如，信用卡卡号）？你是否运用过压缩的魔力，将数兆的照片压缩成更易于管理的大小，以便在电子邮件中发送？你是否在手持设备上触发了人工智能，自动纠正你在手持设备的小巧键盘上输入的内容？这些令人印象深刻的壮举都依赖于之前提到的伟大发现。然而，绝大多数计算机用户每天都会运用这些独创想法许多次，却经常没有意识到！本书旨在面向大众解释这些概念——我们每天使用的计算机科学的伟大思想。在解释每个概念时，我都假设读者没有任何计算机科学的知识。算法：指尖精灵的构件到目前为止，我一直在谈计算机科学的伟大“思想”，但计算机科学家们将许多重要思想形容为“算法”。那么思想和算法之间有什么区别呢？究竟什么是算法？这一问题最简单的答案是，将两个数字相加的算法的前两步。算法是一张精确的处方，按顺序详细列出了解决一个问题所需的具体步骤。我们小时候在学校学到的一个算法就是个很好的例子：将两个大数字相加的算法。如上例所示。这个算法涉及一连串步骤，开始的步骤如下：“首先，将两个数的最末位数相加，写下结果的最末尾数，将剩下的数放到左侧的下一栏；接着，将下一栏的数相加，再将除结果末位数之外的数字和前一栏余下的数相加……”依此类推。请注意算法步骤近乎机械化的感觉。事实上，这是算法的关键特点之一：每一步都必须绝对精确，没有任何人类意图或推测掺杂其中。这样，每一个完全机械化的步骤才能被编入计算机。算法的另一个重要特点是，不管输入是什么，算法总能运行。我们在学校学到的相加算法就拥有这一特性：不管你想把哪两个数相加，算法最终都会得出正确答案。比如，用这一算法将两个长达1000位的数相加，你肯定能得到答案，尽管这需要相当长的时间。对于把算法定义为一张精确、机械化的处方的说法，你也许会略感好奇。这张处方究竟要多精确？要进行哪些基本操作？比如，在上面的相加算法中，简单地说一句“把两个数相加”是不是就行了？还是说我们要在加法表上列出所有个位数字呢？这些细节看起来也许有点乏味，甚至会显得有点学究气，但其实离真相不远了：这些问题的真正答案正处于计算机科学的核心，并且也和哲学、物理学、神经科学以及遗传学有联系。有关算法究竟是什么的深层问题都归结于一个前提——也就是众所周知的邱奇—图灵论题（Church–Turing thesis）。我们将在第十章重温这些问题，届时我们还将讨论计算的理论极限，以及邱奇—图灵论题的一些方面。同时，将算法比作一张非常精确的处方这一非正式概念效果会非常好。现在我们知道了算法是什么，但算法和计算机有什么联系呢？关键在于，计算机需要用非常精确的指令编程。因此，在能让计算机为我们解决某个特定问题之前，我们需要为那个问题开发出一个算法。在数学和物理学等其他科学学科中，重要的结果通常由一个方程式获得。（著名的例子包括勾股定理a2+b2=c2，或爱因斯坦的质量守恒定理E=mc2）相反，计算机科学的伟大思想通常是形容如何解决一个问题——当然，是使用一个算法。因此，本书的主要目的是，解释让计算机成为了你的个人精灵的东西——计算机每天使用的伟大算法。

前言

计算机行业正在改变我们的社会，正如物理学和化学在前两个世纪给社会带来的巨大改变一样。的确，数字技术几乎影响甚至颠覆了我们生活的方方面面。鉴于计算机行业对现代社会的重要性，人们对让这一切成为可能的基本概念却知之甚少，这显得有点自相矛盾。对这些概念的研究是计算机科学的核心，而这本麦考密克的新书则是向大众展示这些概念的少数书籍之一。    人们较少视计算机科学为一门学科，其中一个原因是，高中极少开设计算机科学这门课程。虽然人们通常认为要强制开设物理学和化学基础，但作为独立学科的计算机科学，通常只有在大学阶段才开设此课程。况且，学校讲授的”计算机”或”信息与通信技术“知识，通常只是略高于使用软件的技能训练。因此．学生们认为计算机学科枯燥也并不意外；而他们在娱乐和通信上使用计算机技术的天然热情，也被创造这类技术缺乏学术深度的印象所减弱。这些问题被认为是导致过去10年大学计算机科学专业学生人数下降一半的核心原因。考虑到数字技术对现代社会的极度重要性，让人们重新领略计算机科学的奇妙之处已经刻不容缓。    2008年，我很荣幸地被选为第180届英国皇家学院圣诞讲座(RoyalInstimtion Christmas Lectures)的演讲人，该讲座由迈克尔·法拉第(Michael Faraday)于1826 ff-C2Cg。2008年圣诞讲座的主题首次涉及计算机科学。在准备这些讲座时，我花了很多时间来思考如何向大众解释计算机科学，却发现满足这一需求的资源很少，几乎没有关于计算机科学的畅销书。因此，我特别高兴能看到麦考密克的这本新书。    麦考密克在面向大众介绍计算机科学的复杂思想上做得非常好。这其中许多思想极其新颖，仅从这点上来看，它们就很值得关注。举个例子：电子商务的爆炸式增长之所以成为可能，是因为具备了能在互联网上秘密、安全地发送机密信息(如信用卡卡号)的能力。数十年来，建立在“开放”通道上的保密通信被认为是一个科学难题。当人们发现解决方法时，才发觉保密通信极度优雅，而麦考密克也以精确的类比进行了解释，无须读者拥有计算机科学知识。这些优点使这本书对科普读物做出了不可估量的贡献，我极力推荐本书。

名人推荐

《星际迷航》（Star Trek）中的计算机并不特别让人兴奋。他们向计算机问问题，计算机还要想一会儿。我觉得我们能做得更好。——拉里•佩奇（谷歌联合创始人）

媒体关注与评论

《星际迷航》（Star Trek）中的计算机并不特别让人兴奋。他们向计算机问问题，计算机还要想一会儿。我觉得我们能做得更好。    ——拉里·佩奇（谷歌联合创始人）

内容概要

约翰·麦考密克，JohnMacCormick，计算机科学的领头人和导师。

获得牛津大学博士学位，曾经在惠普和微软从事研究工作。现在在迪金森学院担任计算机学科的教授。并且是多项专利的所有者。

书籍目录

第一章 前言：计算机日常运用的卓越思想有哪些？

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

第三章 Page Rank——让谷歌腾飞的技术

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

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

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

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

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

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

第十章 什么可以计算？

第十一章 结论：更多在你指尖的精灵？

致谢

编辑推荐

《改变未来的九大算法》编辑推荐：在读完《改变未来的九大算法》后，你不会成为一名更加熟练的计算机用户。但你会更加珍视自己每天在所有计算设备上不停使用的思想的美。我们每天都会进行多次搜索查询，但是你想过这个令人惊叹的工具是如何奏效的吗？谷歌的精英管理层因为谷歌“以超乎寻常的技巧返回相关度极高的结果”而获奖，他们是怎么做到的？《改变未来的九大算法》将带你一探究竟。领略奠定虚拟世界的精巧算法，珍视你指尖上的精灵。

作者简介

Google得出的搜索结果是如何产生的？

百度为何会陷入“搜索门”，又是什么机制使然？

身处在大数据时代的我们，究竟该如何应对变化莫测的世界？

……

没有满篇的专业术语，第一次让我们通过简单明了的语言、生动的例证了解支撑计算机王国的灵魂支柱——9大算法，包括人工智能、数据压缩，以及Google著名的PageRank等。

本书精彩地介绍了搜索引擎、PageRank、公开密钥加密、纠错码、模式识别、数据压缩、数据库、数字签名等内容。

在解释这些算法的同时，作者也向我们展示了充满科学原创精神的计算机世界：因为每一种算法的提出不但延伸了虚拟世界的领域，同时也是人类智慧的彰显，可以被广泛运用于众多领域。

在读完本书后，你不会成为一名更加熟练的计算机用户，但你会更珍视自己每天在所有计算设备上不停使用的思想的美。

我们每天都会进行多次搜索查询，但是你想过这个令人惊叹的工具是如何奏效的吗？

谷歌的精英管理层因为谷歌“以超乎寻常的技巧返回相关度极高的结果”而获奖，他们是怎么做到的？

本书将带你一探究竟。

---

 改变未来的九大算法下载 精选章节试读 更多精彩书评

---