读者将理解什么是计算机算法，如何描述它们，以及如何来评估它们。这些计算机算法将提供：利用计算机搜索信息的简单方式；解决各种排序问题的方法；利用有向无环图和最短路径法来解决基本问题的方法（可用于建模公路网络，任务间的依赖以及金融关系；解决字符串（例如DNA结构）问题的方法；密码学背后的基本原理；数据压缩的基础知识；以及甚至一些没有人能够理解如何在计算机上用相当长的时间来解决的问题。

《算法导论》第一作者托马斯 H. 科尔曼面向大众读者的算法著作
理解计算机科学中关键算法的简明读本，帮助您开启算法之门

“算法是计算机科学的核心。这是唯一一本力图针对大众读者的算法书籍。它使一个抽象的主题变得简洁易懂，而没有过多拘泥于细节。本书具有深远的影响，还没有人能够比托马斯 H. 科尔曼更能胜任缩小算法专家和公众的差距这一工作。”
—— Frank Dehne，卡尔顿大学计算机科学系教授
“托马斯 H. 科尔曼写了一部关于基本算法的引人入胜的、简洁易读的调查报告。有一定计算机编程基础并富有进取精神的读者将会洞察到隐含在高效计算之下的关键的算法技术。”
—— Phil Klein，布朗大学计算机科学系教授
“托马斯 H. 科尔曼帮助读者广泛理解计算机科学中的关键算法。对于计算机科学专业的学生和从业者，本书对每个计算机科学家必须理解的关键算法都进行了很好的回顾。对于非专业人士，它确实打开了每天所使用的工具的核心——算法世界的大门。”
—— G. Ayorkor Korsah，阿什西大学计算机科学系助理教授


你想知道你的GPS是如何在几秒钟内从看起来无数多条可能路径中找到到达目的地的最快捷路径的吗？当你在网上购物时，你的信用卡账号是如何被保护的呢？答案均是算法。本书是关于计算机算法基础的权威指南。在本书中，作者展示了计算机如何通过算法解决问题。

读者将学习到什么是计算机算法，如何描述计算机算法，以及如何评估计算机算法。读者还将学习到在计算机中查找信息的简单方法；在计算机中将信息按照某个预定的顺序重排（“排序”）；如何解决那些在计算机中能使用一种被称为“图”的数学结构来建模的基本问题（可用于对道路网建模，针对任务间的依赖建模，以及金融套利交易建模）；如何解决关于字符串（例如DNA结构）的问题；密码学的基本原理；数据压缩的基本原理；甚至那些至今还没有人得出如何借助计算机在一段合理的时间内求解的问题。

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

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

后
算法导论（原书第3版）
作者：Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
译者：殷建平 徐云 王刚 刘晓光 苏明 邹恒明 王宏志
ISBN：978-7-111-40701-0　定价：128.00元

全球超过50万人阅读的算法圣经！算法标准教材，国内外1000余所高校采用。
专家推荐：
“本书是算法领域的一部经典著作，书中系统、全面地介绍了现代算法：从最快算法和数据结构到用于看似难以解决问题的多项式时间算法；从图论中的经典算法到用于字符匹配、计算集合和数论的特殊算法。本书第3版尤其增加了两章专门讨论van Emde Boas树（最有用的数据结构之一）和多线程算法（日益重要的一个主题）。”
—— Daniel Spielman，耶鲁大学计算机科学和应用数学Henry Ford II教授
“作为一个在算法领域有着近30年教育和研究经验的教育者和研究人员，我可以清楚明白地说这本书是我所见到的该领域最好的教材。它对算法给出了清晰透彻、百科全书式的阐述。我们将继续使用这本书的新版作为研究生和本科生的教材和可以信赖的研究参考书。”
—— Gabriel Robins，弗吉尼亚大学工程和
应用科学学院计算机科学系教授
读者评语：
“计算机圣经之一！算法才是程序员的核心竞争力！”
“这本书，一定要好好细读，理解体会其中的道理，算法是计算机的精髓！这本书作为讲解算法的一本经典书籍，它本来可以是无聊沉闷的、学术的，但是它不是那样子的！它的内容是有趣的、易于理解的，让你在学习深奥的算法过程中享受乐趣！”

计算机是如何解决问题的呢？小小的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。

Tom Cormen
于新罕布什尔州汉诺威

计算机\算法

“算法是计算机科学的核心。这是唯一一本力图针对大众读者的算法书籍。它使一个抽象的主题变得简洁易懂，而没有过多拘泥于细节。本书具有深远的影响，还没有人能够比托马斯•科尔曼更能胜任缩小算法专家和公众的差距这一工作。”
——Frank Dehne，卡尔顿大学计算机科学系教授
“托马斯•科尔曼写了一部关于基本算法的引人入胜的、简洁易读的调查报告。有一定的计算机编程基础并富进取精神的读者将会洞察到隐含在高效计算之下的关键的算法技术。”
——Phil Klein,布朗大学计算机科学系教授
“托马斯•科尔曼帮助读者广泛理解计算机科学中的关键算法。对于计算机科学专业的学生和从业者，本书对每个计算机科学家必须理解的关键算法都进行了很好的回顾。对于非专业人士，它确实打开了每天所使用的工具的核心——算法世界的大门。”
——G.Ayorkor Korsah，阿什西大学计算机科学系助理教授

你想知道你的GPS是如何在几秒钟内从看起来无数多条可能路径中找到到达目的地的最快捷路径的吗？当你在网上购物时，你的信用卡账号是如何被保护的呢？答案均是算法。本书是关于计算机算法基础的权威指南。在本书中，作者提示了计算机如何通过算法解决问题。

读者将学习到什么是计算机算法，如何描述计算机算法，以及如何评估计算机算法。读者将学习到在计算机中查找信息的简单方法；在计算机中将信息按照某个预定的顺序重排(“排序”)；如何解决那些在计算机中能使用一种被称为“图”的数学结构来建模的基本问题(可用于对道路网建模，针对任务间的依赖建模，以及金融套利交易建模)；如何解决关于字符串(例如DNA结构)的问题；密码学的基本原理；数据压缩的基本原理；甚至那些至今还没有人得出如何借助计算机在一段合理的时间内求解的问题。

王宏志 译：暂无简介

算法设计与分析是计算机科学的核心内容之一，算法设计与分析的能力也成为计算机科学从业者最重要的基本功之一，因而“算法设计与分析”是计算机专业学生的重要专业课程。尽管算法设计与分析很重要，但这门课程对许多读者来说稍显“高冷”，主要表现为其内容抽象、覆盖范围广、需要的数学基础多，因而学习算法设计与分析仿若攀登一座费时费力的高山。
针对这种情况，计算机领域的大牛Thomas Cormen出手了。他撰写了此书作为面向算法设计与分析初学者的入门书籍。本书有着如下几个鲜明的特点。
第一，本书仅仅使用了有限的数学知识。对于很多算法初学者来说，阻碍其学习的很重要的一个绊脚石就是算法设计与分析中涉及的大量数学知识，覆盖了概率论、代数、数学分析、图论等多个方面，而本书不需要读者具备这些方面的深入知识，为算法初学者提供了一条入门的捷径。
第二，本书语言通俗生动，并且把算法和现实中的问题紧密连接，避免出现大量算法分析细节。一方面，让算法真正成为生活中的一种思维方式，让读者深入了解算法思想的实际用途；另一方面，对于很多应用背后的算法知识，让读者在“知其然”的同时“知其所以然”。
第三，本书覆盖范围广，在200多页的篇幅中覆盖了图论算法、字符串算法、密码算法、数据压缩算法，甚至NP完全问题和不可判定问题，使读者可在最短的时间内掌握多种应用中不同的算法。
特别值得一提的是，本书的作者Thomas Cormen也是算法设计与分析方面的经典教材《算法导论》的作者之一，译者有幸参与了该书的翻译工作。《算法导论》是一本内容深入的算法设计与分析方面的大部头教材，而本书则可以看作是《算法导论》的一个薄薄的入门版本，通过阅读本书，读者可以用最短的时间轻松地窥见算法设计与分析的门径，奠定学习“算法设计与分析”课程的基础。
在本书英文版出版以后，译者应机械工业出版社的邀请开始了本书的翻译工作。由于水平有限且时间紧张，译文中一定存在许多不足，在此敬请各位同行、专家、学者和广大读者批评指正，欢迎大家将发现的错误或提出的意见与建议发送到邮箱wangzh@hit.edu.cn，以改进本书的译本。
最后，我要感谢哈尔滨工业大学的孔欣欣同学在翻译过程中进行的辅助翻译工作。在完成译稿之后，我的爱人黎玲利博士阅读全文并提出了很多有益的意见，在此也表示感谢。同时感谢机械工业出版社的姚蕾编辑和朱劼编辑，由于她们的信任和支持，本书的翻译工作才得以顺利进行。

王宏志

出版者的话
译者序
前言
第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