《计算机应用基础》课程教学资源（推荐书籍）改变未来的九大算法[美]约翰·麦考密克（John MacCormick）

NEALG○PTH/ THAT CHANO©ED FUTURE 改变未来的九大算法 上的 ① 中信出版社CHINACITICPRESS

序 第一章 前言 001计算机日常运用的卓越思想有哪些 第二章 搜索引擎索引 013在世界上最大的草垛中寻针 第三音 PageRank 目录 031 让谷歌腾飞的技术 第四意 公钥加密 049 用明信片传输秘密 第五章 纠错码 075 自纠正的错误

改李未来的九大第法 第六章 图形识别 099从经验中学习 第七章 数据压缩 127有益无害 第八音 数据库 147追求一致性的征程 第九章 第十章 205什么可以计算 有些程序不可能存在 第十一章 话论 235更多在你指尖的精灵 243致谢 245注释 PDF电子书基地http:/dayol982.400gb.com

PDF电子书基地 http://dayo1982.400gb.com

第一章 前言 一计算机日常运用的卓越思想有哪些 ALSORITHMS 此乃小技.为诗之诀在于有气。有势、有情 有韵.有起、有承、有转、有合。① 一威廉姆·莎士比亚 《爱的徒劳》（亿ove3 Labour Lost) ①选自朱生豪译本。—译者注

PDF电子书基地http:/dayol982.400gb.com

PDF电子书基地 http://dayo1982.400gb.com

计算机科学中的伟大思想是如何诞生的？以下遴选部分思想进行介绍： ·20世纪30年代，在第一台数字计算机发明以前，一位英国天才开创了计 算机科学领域。之后，这位天才继续证明，不管未来建造的计算机运行多快、功 能多强大、设计得多好，仍旧有一些问题是计算机不能解决的。 ·1948年，一位供职于电话公司的科学家发表了一篇论文，开创了信息理论 领域。这位科学家的工作让计算机能以完美的精确度传输信息，即便大部分数据 都因为被干扰而破坏。 ·1956年，一群学者在达特茅斯举行会议。这次会议的目标很清晰，也很 大胆，那就是开创人工智能领域。在取得了许多重大成功以及经历了无数失望之 后，我们仍期待出现一个真正的智能计算机程序。 ·1969年，BM公司的一名研究人员发明了一种将信息组织进数据库中的先 进方法。目前.绝大多数在线交易都使用该技术存储及检索信息

李泰来的九大算法 ·1974年.英国政府秘密通信实验室的研究人员发明了一种让计算机安全通 信的方法，即另一台计算机可以查看在计算机之间交换的所有信息。这些研究人 员为政府保密所限—不过幸运的是，三名美国专家独立开发并拓展了这项重大 发明，为互联网上所有的安全通信打下了基础。 ·1996年，两名斯坦福大学博士生决定联手搭建一个互联网搜索引擎。几年 后.他们创办了谷歌公司一互联网时代的第一个数字巨头。 在我们享受21世纪技术惊人增长的同时，使用计算机设备一不管 是现有最强大的一组机器还是最新、最时尚的手持设备一一都不可避免地 要依赖计算机科学的基础思想，而这些思想都诞生于20世纪。想一想： 你今天做过什么令人印象深刻的事情吗？好吧，这个问题的答案取决于你 怎么看。也许你搜索了包含数十亿份文档的资料库，从中选出两到三份与 你的需求最相关的文档？即便有能够影响所有电子设备的电磁干扰，存储 或传输了数百万条信息，也没犯一点错误？你是否成功地完成了一次在线 交易，即便同时有成千上万名消费者在访问同一个服务器？你是否在能够 被其他数十台计算机嗅探到的线路中传输了一些机密信息（比如信用卡卡 号)？你是否运用过压缩的魔力，将数兆的照片压缩成更易于管理的大小， 以便在电子邮件中发送？你是否在手持设备上触发了人工智能，自动纠正 你在手持设备的小巧键盘上输人的内容？ 这些令人印象深刻的壮举都依赖于之前提到的伟大发现。然而，绝大 多数计算机用户每天都会多次运用这些独创想法，却从没有意识到！本书 旨在面向大众解释这些概念—我们每天使用的计算机科学的伟大思想。 在解释每个概念时，我都假设读者不了解任何计算机科学的任何知识。 PDF电子书基地http:/dayol982.400gb.com

PDF电子书基地 http://dayo1982.400gb.com

第一章前言一计算机日常运用的卓越思想有哪些 算法：指尖精灵的构件 到目前为止，我一直在谈计算机科学的伟大“思想”，但计算机科学 家们将许多重要思想形容为“算法”。那么思想和算法之间有什么区别 呢？究竞什么是算法？这一问题最简单的答案是，算法是一张精确的处 方，按顺序详细列出了解决一个问题所需要的具体步骤。我们小时候在学 校学到的一种算法就是很好的例子：将两个大数字相加的算法。如下例所 示。这个算法涉及一连串步骤，开始的步骤如下：“首先，将两个数的最 末位数相加，写下结果的最末位数，将剩下的数放到左侧的下一栏；接 着，将下一栏的数相加，再将除结果末位数之外的数字和前一栏余下的数 相加.”。依此类推。 11 4844978 4844978 4844978 +3745945 +3745945 +3745945 3 23 将两个数宇相加的算法的前两步。 请注意算法步骤近乎机械化的感觉。事实上，这是算法的关键特点之 一：每一步都必须绝对精确，没有任何人类意图或推测掺杂其中。这样， 每一个完全机械化的步骤才能被编入计算机。算法的另一个重要特点是， 不管输人什么，算法总能运行。我们在学校学到的相加算法就拥有这一特 性：不管你想把哪两个数相加，算法最终都会得出正确答案。比如，用这 一算法将两个长达】000位的数相加，你肯定能得到答案，尽管这需要相 当长的时间。 对于把算法定义为一张精确、机械化的处方的说法，你也许会略感好 奇。这张处方究竞要有多精确？要进行哪些基本操作？比如，在上面的 相加算法中，简单地说一句“把两个数相加”是不是就行了？还是说我

改未来的九大法 们要在加法表上列出所有个位数字？这些细节看起来也许有点乏味，甚至 会显得有点学究气，但其实离真相不远了：这些问题的真正答案正处于计 算机科学的核心，并且也和哲学、物理学、神经科学以及遗传学有联系。 有关算法究竟是什么的深层问题都归结于一个前提一也就是众所周知 的邱奇一图灵论题(Church-Turing Thesis)。我们将在第十章重温这些 问题，届时我们还将讨论计算的理论极限，以及邱奇一图灵论题的一些 方面。同时，将算法比作一张非常精确的处方这一非正式概念效果会非 常好 现在我们知道了算法是什么，但算法和计算机有什么联系呢？关键在 于，计算机需要用非常精确的指令编程。因此，在能让计算机为我们解决 某个特定问题之前，我们需要为那个问题开发一个算法。在数学和物理 学等其他学科中，重要的结果通常是由一个方程式获得的。（著名的例子 包括勾股定理a2+b2=c2,或爱因斯坦的质量守恒定理E=m2。)相反，计 算机科学的伟大思想通常是形容如何解决一个问题一当然，是使用一种 算法。因此，本书的主要目的是，解释让计算机成为你的个人精灵的东 西—计算机每天使用的伟大算法。 一个伟大的算法由什么构成？ 这会引出一个刁钻的问题：什么才是真正伟大的“算法”？潜在的候 选算法清单相当大，但我用几条基本标准缩减了用于本书的候选算法清单。 第一条，也是最重要的一条标准是，伟大的算法要被普通计算机用户每天 用到。第二条重要的标准是，伟大的算法应该能处理具体的现实问题，如 压缩一个特定文件或通过一个噪声链接精确地传输文件。对于已经了解部 分计算机科学的读者而言，下面的文字框解释前面两大标准的部分后果。 PDF电子书基地http:/dayol982.400gb.com

PDF电子书基地 http://dayo1982.400gb.com

第一章前言—计算机日常运用的卓越思想有哪些 第一条标准—一要被普通计算机用户每天用到—排除了主要由 计算机专业人土使用的算法，如编译器和程序验证技术。第二条标 准—针对某个特定问题的具体程序—排除了许多作为计算机科学 本科课程核心内容的伟大算法，如排序算法（快速排序）、图形算法 (迪杰斯特拉最短路径算法)、数据结构（哈希表）。这些算法的伟 大性毋庸置疑，而且很轻易地就满足了第一条标准，因为普通用户 使用的绝大多数应用程序都会反复应用这些算法。但这些算法太通 用了：它们能用于解决众多问题。在本书中，我决定要专注于解决特 定问题的算法，因为对于普通计算机用户而言，这些算法能让他们拥 有更清晰的动机。 一些和本书选取算法有关的额外细节。本书读者无须具备计算机 科学的任何知识。但如果读者具备计算机学背景知识，这个文字框 会解释为何这类读者之前偏好的许多内容没有出现在本书中。 第三个标准是，算法主要和计算机科学理论相关。这排除了主要和计 算机硬件—如CPU、监视器以及网络一有关的技术。这条标准也减 轻了对基础设施一如互联网—设计的重视。为什么我要着重于计算机 科学理论？部分原因是由于公众对计算机科学认知的不平衡：有一种广泛 的观点认为，计算机科学基本上就是编程（如“软件”)和设备设计（如 “硬件”)。事实上，最优美的计算机科学思想中有许多是十分抽象的，并 不属于以上任意一类。我希望通过着重于这些理论思想，让更多人将计算 机科学的本质作为一门知识学科来理解。 你也许已经注意到了，我列出的标准可能会遗漏一些伟大的算法，但 却从一开始就避免了定义伟大这个极其麻烦的问题。针对这一问题，我依 赖于自己的直觉。在本书中说明的每一个算法中，其核心都是一个让整件 事情奏效的精巧把戏。对我而言，当这个把戏显露出来时，那个“惊叹