前言

计算机是如何解决问题的呢？小小的GPS是如何只在几秒内就从无数条可能路径中找出到达目的地的最快捷路径的呢？在网上购物时，又如何防止他人窃取你的信用卡账号呢？解决这些问题，以及大量其他问题的答案均是算法。我写本书的目的就是为你打开算法之门，解开算法之谜。

我是《算法导论》的合著者之一。《算法导论》是一本特别好的书（当然，这是我个人的主观评价），但是它确实相当专业。

本书并不是《算法导论》，甚至不能被称为一本教材。它既没有对计算机算法领域进行广度或深度的研究，也没有遵照惯例来讲述设计计算机算法的方法，甚至连一道需要读者自己求解的难题或者练习题也没有。

那么，这是一本什么样的书呢？如果你符合如下条件，那么就可以开始阅读之旅了：

· 你对计算机如何解决问题感兴趣；

· 你想知道如何评估这些解决方案的质量；

· 你想了解计算方面的问题和这些问题的解决方案是如何与非计算机世界关联起来的；

· 你能处理一点数学运算；

· 你没有编写过计算机程序（当然，编写过程序更好）。

一些计算机算法方面的书籍是讲述理论概念的，并涉及非常少的技术细节；一些书籍关注的全是技术细节；而另外一些书籍是介于这两者之间的。每类图书都有自己的定位，我将本书定位于介于两者之间。诚然，本书涉及了一些数学知识，并且部分地方阐述得非常仔细，但是我已经竭力避免深入阐述细节（或许除了本书的末尾部分，我无法克制住自己，阐述了一些细节知识）。

我认为本书有点像开胃菜。设想你去了一家意大利餐厅，点了一份开胃菜，直到吃完开胃菜，你才会决定是否点其余食物。开胃菜到了，你就开始用餐了。或许你不喜欢吃开胃菜，并且决定不点其他菜了。可能你喜欢吃开胃菜，但是吃完它，你就感觉饱了，因此不需要点其他菜了。或者也有可能你喜欢吃开胃菜，但你并没有吃饱，此时你便开始期待其他菜了。将本书看作开胃菜，我希望能够产生后两种结果之一：读完了本书，你就很满足，感觉没有必要再深入探究算法世界了；你非常喜欢从本书中所学到的知识，以至于你想要学习更多算法方面的内容。每一章最后一节的标题为“拓展阅读”，其中会介绍更多关于该章主题的更为深入的书籍和文章。

你将从本书中学到什么

我无法断定你将从本书中学到什么。如下是我希望你能从本书中学到的：

· 什么是计算机算法，能够采用一种方式来描述计算机算法，以及如何评估算法。

· 在计算机中查找信息的简单方式。

· 在计算机中重排信息以使其以一种预定顺序排列的方法。（我们称这一任务为“排序”。）

· 如何解决那些能在计算机中以一种称为“图”的数学结构建模的基本难题。在许多应用中，利用图建模的领域包括：道路网（哪些十字路口到哪些十字路口有直接相连的道路，这些道路有多长），任务间的依赖关系（哪个任务必须在其他任务之前完成），金融关系（世界各国货币间的汇率是多少），或者人与人之间的联系（谁认识谁，谁讨厌谁，哪个演员和哪个演员出现在同一个电影中，等等）。

· 如何解决关于文本字符串的问题。其中一些问题在某些领域有所应用，例如生物学领域，其中字符表示基本的分子，字符串表示DNA结构。

· 密码学背后的基本原理。即使你自己从来没有加密过一条信息，你的计算机很可能已经对它执行加密操作了（例如当你在网上购物时）。

· 数据压缩的基本概念，这远远超过了“f u cn rd ths u cn gt a gd jb n gd pay”背后的压缩原理。

· 计算机在任意合理的时间内都难以解决的一些问题，或者至少还没有人想出如何解决的问题。

为了理解本书中的内容，你需要事先了解什么

正如我之前所说的，本书中涉及部分数学知识。如果你害怕数学，那么你可以尝试着跳过它，或者你也可以尝试着阅读涉及更少专业技术知识的书籍。但是我已经尽力做到让数学部分变得容易理解了。

我假定你从来没有写过，甚至从来没有读过一个计算机程序。如果你能看懂提纲的内容，就应该能够理解我是如何表达每一步算法，以及如何将这些步骤合并在一起组合成一个完整的算法的。如果你听到过如下笑话，那么你已经是在通往算法世界了：

你听说过被困在淋浴中的计算机专家吗？当时他在按照洗发瓶上的指示洗头发。指示说明是：“打洗发露。冲洗。重复。”

本书使用了一种自由的写作风格，希望这种比较个性的方法能使本书的内容看起来更容易理解。有些章节依赖于前面章节的内容，但是这种依赖程度很轻。有些章节开始时不涉及专业技术知识，但是会逐步讲述专业技术知识。即使你感觉某一章太难了，这也不会影响下一章内容的学习。你也很可能会从下一章的开始部分受益。

报告错误

如果你在本书中发现了错误，请通过发送邮件至algorithms-unlocked@mit.edu来告知我。

致谢

本书中的许多内容都参考了《算法导论》的内容，因此多亏了《算法导论》的合著者——Charles Leiserson、Ron Rivest以及Cliff Stein的帮助。你将发现我自始至终都在频繁地提到（插入）《算法导论》的内容，我们4个作者所写的《算法导论》早已众所周知了。在写本书时，我意识到我是多么想念和Charles、Ron及Cliff的合作。同时我仍然感谢在《算法导论》的前言部分所感谢的那些人。

同时，我也参考了在达特茅斯学院教书时所讲述的课程内容，尤其是计算机科学课程1、5和25。感谢我的学生，通过他们精辟的见解，我看出了当前这种教学方法很好；通过他们无情的沉默眼神，我看出了当前这种教学方式不理想。

本书是在Ada Brunstein的建议下撰写的。Ada Brunstein是MIT出版社负责《算法导论》第3版的编辑。Ada现在已经离开MIT出版社了，Jim DeWolf接替了她的位置。刚开始时，本书被指定为MIT出版社的“基础知识”丛书的一部分，但是MIT出版社认为对于“基础知识”丛书而言，本书过于专业了。（想象一下——我写了一本对于MIT而言过于专业的书籍！）Jim巧妙、灵活地处理了这件事，允许我以自己的方式来写这本书，而不是按照MIT出版社初期的规定。同时，我还要感谢MIT出版社Ellen Faran和Gita Devi Manaktala的支持。

Julie Sussman, P.P.A.,是《算法导论》第2版和第3版的文字编辑，本书还是由她担任文字编辑，对此我感到非常兴奋。她是最好的、最专业的文字编辑。她让我放下所有顾虑。为了证明她的优秀，请看Julie关于我的第5章初稿所回复的一份电子邮件：

亲爱的Cormen先生，

当局已经抓获了一章逃逸的内容，发现它隐藏在您的书中。我们无法确定它是从哪本书中逃离的，但是我们无法想象这几个月中在您都不知晓的情况下，它是如何一直藏匿在您的书中的，因此我们只能认为您应对此负责。我们希望您能承担起修改这一章的任务，给它一个机会，让它成为书中的一个有用的公民。来自一个逮捕该章的警官的报告，Julie Sussman，附上。

你可能很好奇“P.P.A.”代表什么，事实上前两个字母代表“Professional Pain”，很可能你已经猜想到了“A”代表什么，但是我想要指出Julie的确以这个头衔自豪。因此非常非常感谢Julie！

我并不是一个密码破译者，关于密码学原理的那一章极大地归功于Ron Rivest、Sean Smith、Rachel Miller以及Huijia Rachel Lin的帮助。那一章中有一个关于棒球手势的脚注说明，这要感谢达特茅斯学院的棒球教练Bob Whalen，是他耐心地向我解释了棒球手势体系中的一些手势。Ilana Arbisser核实了计算生物学家对齐DNA序列的方式与第7章所介绍的方式一致。Jim DeWolf和我仔细思考了本书的书名，但是“Algorithms Unlocked”这一书名最终是由达特茅斯学院的一个本科生Chander Ramesh提出的。

达特茅斯学院计算机科学系是一个很好的工作去向。我的同事个个才华横溢，我们的专职人员也都是首屈一指的。如果你希望编写一个本科生或者研究生级别的计算机科学程序，或者如果你在寻找一个计算机科学专业的教授职位，建议你申请达特茅斯学院。

最后，感谢我的妻子Nicole Cormen、我的父母Renee和Perry Cormen、我的姊妹Jane Maslin以及Nicole的父母Colette和Paul Sage，感谢他们对我的爱和支持。我的父亲确信在1.1节中的图形是5，而不是S。

Thomas H.Cormen
于新罕布什尔州汉诺威