算法基础：打开算法之门

托马斯 H. 科尔曼（Thomas H. Cormen），达特茅斯学院计算机科学系教授，2009年7月到2015年7月期间担任达特茅斯学院计算机科学系主任。他是《算法导论（第3版）》（麻省理工学院出版社，2009)的合著者(与查尔斯 E. 雷瑟尔森，罗纳德 L. 李维斯特以及克利福德·斯坦合著)之一。目前的研究兴趣包括：算法工程、并行计算、具有高延迟的加速计算。他分别于1993年、1986年获得麻省理工学院电子工程和计算机科学博士、硕士学位，师从查尔斯 E. 雷瑟尔森教授。由于在计算机教育领域的突出贡献，科尔曼教授荣获2009年ACM杰出教员奖。

王宏志，哈尔滨工业大学计算机科学与技术学院副教授、博士生导师。研究方向包括大数据管理、数据质量、图数据管理。发表学术论文140余篇，出版学术专著两本，参与翻译《算法导论（第3版）》。在爱课程网、学堂在线、好大学在线上首次开设“大数据算法”在线课程，出版《大数据算法》教材。

“算法是计算机科学的核心。这是一本力图针对大众读者的算法书籍。它使一个抽象的主题变得简洁易懂，而没有过多拘泥于细节。本书具有深远的影响，还没有人能够比托马斯 H. 科尔曼更能胜任缩小算法专家和公众的差距这一工作。”
—— Frank Dehne，卡尔顿大学计算机科学系教授

“托马斯 H. 科尔曼写了一部关于基本算法的引人入胜的、简洁易读的调查报告。有一定计算机编程基础并富有进取精神的读者将会洞察到隐含在高效计算之下的关键的算法技术。”
—— Phil Klein，布朗大学计算机科学系教授

“托马斯 H. 科尔曼帮助读者广泛理解计算机科学中的关键算法。对于计算机科学专业的学生和从业者，本书对每个计算机科学家必须理解的关键算法都进行了很好的回顾。对于非专业人士，它确实打开了每天所使用的工具的核心——算法世界的大门。”
—— G. Ayorkor Korsah，阿什西大学计算机科学系助理教授

Algorithms Unlocked
出版者的话
译者序
前言
第1章什么是算法以及为什么应该关注算法1
1.1正确性2
1.2资源利用3
1.3针对非计算机专业人士的计算机算法5
1.4针对计算机专业人士的计算机算法6
1.5拓展阅读7
第2章如何描述和评估计算机算法9
2.1如何描述计算机算法9
2.2如何描述运行时间16
2.3循环不变式19
2.4递归21
2.5拓展阅读23
第3章排序算法和查找算法24
3.1二分查找26
3.2选择排序31
3.3插入排序34
3.4归并排序38
3.5快速排序47
3.6小结55
3.7拓展阅读57
第4章排序算法的下界和如何超越下界58
4.1基于排序的规则58
4.2基于比较排序的下界59
4.3使用计数排序超越下界60
4.4基数排序66
4.5拓展阅读68
第5章有向无环图69
5.1有向无环图72
5.2拓扑排序72
5.3如何表示有向图76
5.4拓扑排序的运行时间77
5.5PERT图表中的关键路径78
5.6有向无环图中的最短路径82
5.7拓展阅读86
第6章最短路径87
6.1Dijkstra算法89
6.2BellmanFord算法98
6.3FloydWarshall算法103
6.4拓展阅读112
第7章字符串算法114
7.1最长公共子序列114
7.2字符串转换120
7.3字符串匹配128
7.4拓展阅读135
第8章密码学基础136
8.1简单替代密码137
8.2对称密钥加密138
8.3公钥加密142
8.4RSA加密系统144
8.5混合加密系统153
8.6计算随机数153
8.7拓展阅读154
第9章数据压缩156
9.1哈夫曼编码158
9.2传真机165
9.3LZW压缩166
9.4拓展阅读176
第10章难？问题177
10.1棕卡车问题177
10.2P、NP和NP完全类181
10.3可判定问题和归约183
10.4主问题186
10.5NP完全问题例析188
10.6总体策略203
10.7前景206
10.8不可判定问题208
10.9小结210
10.10拓展阅读211
参考文献212
索引214

计算机是如何解决问题的呢？小小的GPS是如何只在几秒钟内就从无数条可能路径中找出到达目的地的最快捷路径的呢？在网上购物时，又如何防止他人窃取你的信用卡账号呢？解决这些问题，以及大量其他问题的答案均是算法。我写本书的目的就是为你打开算法之门，解开算法之谜。
我是《算法导论》的合著者之一。《算法导论》是一本特别好的书（当然，这是我个人的主观评价），但是它确实相当专业。
本书并不是《算法导论》，甚至不能被称为一本教材。它既没有对计算机算法领域进行广度或深度的研究，也没有遵照惯例来讲述设计计算机算法的方法，甚至连一道需要读者自己求解的难题或者练习题也没有。
那么，这是一本什么样的书呢？如果你符合如下条件，那么就可以开始阅读之旅了：
●你对计算机如何解决问题感兴趣；
●你想知道如何评估这些解决方案的质量；
●你想了解计算方面的问题和这些问题的解决方案是如何与非计算机世界关联起来的；
●你能处理一点数学运算；
●你不需要编写过计算机程序（当然，编写过程序更好）。
一些计算机算法方面的书籍是讲述理论概念的，并涉及非常少的技术细节；一些书籍关注的全是技术细节；而另外一些书籍是介于这两者之间的。每类图书都有自己的定位，我将本书定位于介于两者之间。诚然，本书涉及了一些数学知识，并且部分地方阐述得非常仔细，但是我已经竭力避免深入阐述细节（或许除了本书的末尾部分，我无法克制住自己，阐述了一些细节知识）。
我认为本书有点像开胃菜。设想你去了一家意大利餐厅，点了一份开胃菜，直到吃完开胃菜，你才会决定是否点其余食物。开胃菜到了，你就开始用餐了。或许你不喜欢吃开胃菜，并且决定不点其他菜了。可能你喜欢吃开胃菜，但是吃完它，你就感觉饱了，因此不需要点其他菜了。或者也有可能你喜欢吃开胃菜，但你并没有吃饱，此时你便开始期待其他菜了。将本书看作开胃菜，我希望能够产生后两种结果之一：或者读完了本书，你就很满足，感觉没有必要再深入探究算法世界了；或者你非常喜欢从本书中所学到的知识，以至于你想要学习更多算法方面的内容。每一章最后一节的标题为“拓展阅读”，其中会介绍更多关于该章主题的更为深入的书籍和文章。
你将从本书中学到什么
我无法断定你将从本书中学到什么。如下是我希望你能从本书中学到的：
●什么是计算机算法，能够采用一种方式来描述计算机算法，以及如何评估算法。
●在计算机中查找信息的简单方式。
●在计算机中重排信息以使其以一种预定顺序排列的方法。（我们称这一任务为“排序”。）
●如何解决那些能在计算机中以一种称为“图”的数学结构建模的基本难题。在许多应用中，利用图建模的领域包括：道路网（哪些十字路口到哪些十字路口有直接相连的道路，这些道路有多长），任务间的依赖关系（哪个任务必须在其他任务之前完成），金融关系（世界各国货币间的汇率是多少），或者是人与人之间的联系（谁认识谁？谁讨厌谁？哪个演员和哪个演员出现在同一个电影中等）。
●如何解决关于文本字符串的问题。其中一些问题在某些领域有所应用，例如生物学领域，其中字符表示基本的分子，字符串表示DNA结构。
●密码学背后的基本原理。即使你自己从来没有加密过一条信息，你的计算机很可能已经对它执行加密操作了（例如当你在网上购物时）。
●数据压缩的基本概念，这远远超过了“f u cn rd ths u cn gt a gd jb n gd pay”背后的压缩原理。
●计算机在任意合理的时间内都难以解决的一些问题，或者至少还没有人想出如何解决的问题。
为了理解本书中的内容，你需要事先了解什么
正如我之前所说的，本书中涉及部分数学知识。如果你害怕数学，那么你可以尝试着跳过它，或者你也可以尝试着阅读涉及更少专业技术知识的书籍。但是我已经尽力做到令数学部分变得容易理解了。
我假定你从来没有写过，甚至从来没有读过一个计算机程序。如果你能看懂提纲的内容，就应该能够理解我是如何表达每一步算法，以及如何将这些步骤合并在一起组合成一个完整的算法的。如果你听到过如下笑话，那么你已经是在通往算法世界了：
你听说过被困在淋浴中的计算机专家吗？当时他在按照洗发瓶上的指示洗头发。指示说明是“打洗发露。冲洗。重复。”
本书使用了一种自由的写作风格，希望这种比较个性的方法能使本书的内容看起来更容易理解。有些章节依赖于前面章节的内容，但是这种依赖程度很轻。有些章节开始时不涉及专业技术知识，但是会逐步讲述专业技术知识。即使你感觉某一章太难了，这也不会影响下一章内容的学习。你也很可能会从下一章的开始部分受益。
报告错误
如果你在本书中发现了错误，请通过发送邮件来告知我。
致谢
本书中的许多内容都参考了《算法导论》的内容，因此多亏了《算法导论》的合著者——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。
Tom Cormen
于新罕布什尔州汉诺威