编辑推荐
《算法导论》作者托马斯 H. 科尔曼面向大众读者的算法著作
理解计算机科学中关键算法的简明读本,帮助您开启算法之门
你想知道你的GPS是如何在几秒钟内从看起来无数多条可能路径中找到到达目的地的快捷路径的吗?当你在网上购物时,你的信用卡账号是如何被保护的呢?答案均是算法。本书是关于计算机算法基础的指南。在本书中,作者展示了计算机如何通过算法解决问题。
读者将学习到什么是计算机算法,如何描述计算机算法,以及如何评估计算机算法。读者还将学习到在计算机中查找信息的简单方法;在计算机中将信息按照某个预定的顺序重排(“排序”);如何解决那些在计算机中能使用一种被称为“图”的数学结构来建模的基本问题(可用于对道路网建模,针对任务间的依赖建模,以及金融套利交易建模);如何解决关于字符串(例如DNA结构)的问题;密码学的基本原理;数据压缩的基本原理;甚至那些至今还没有人得出如何借助计算机在一段合理的时间内求解的问题。
内容简介
读者将理解什么是计算机算法,如何描述它们,以及如何来评估它们。这些计算机算法将提供:利用计算机搜索信息的简单方式;解决各种排序问题的方法;利用有向无环图和短路径法来解决基本问题的方法(可用于建模公路网络,任务间的依赖以及金融关系;解决字符串(例如DNA结构)问题的方法;密码学背后的基本原理;数据压缩的基础知识;以及甚至一些没有人能够理解如何在计算机上用相当长的时间来解决的问题。
作者简介
托马斯 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�睩ord算法98
6.3Floyd�瞁arshall算法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�盤�盇��,是《算法导论》第2版和第3版的文字编辑,本书还是由她担任文字编辑,对此我感到非常兴奋。她是最好的、最专业的文字编辑。她让我放下所有顾虑。为了证明她的优秀,请看Julie关于我的第5章初稿所回复的一份电子邮件:
亲爱的Cormen先生,
当局逮捕了一个逃走的章节,这个章节被发现隐藏在你的书中。我们无法确定它是从哪本书中逃离的,但是我们无法想象这几个月中在你都不知晓的情况下,它是如何一直寄宿在你的书中的,因此我们别无选择,只能询问你。我们希望你能承担起修改这一章的任务,给它一个机会,让它成为书中的一个有用的公民。来自一个负责逮捕的军官的报告,Julie Sussman,附上。
你可能很好奇“P�盤�盇�薄贝�表什么,事实上前两个字母代表“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
于新罕布什尔州汉诺威
探索思维的边界:一本关于逻辑、模式与创造力的实践指南 在信息爆炸的时代,我们每天都被海量的数据和层出不穷的问题所包围。如何有效地处理这些信息,找到解决问题的最优路径,甚至发现隐藏在混沌中的规律,已经成为一项至关重要的能力。这本书并非直接教授具体的算法“公式”或“代码”,而是致力于打磨一种通用的思维模式,一种看待世界、分析问题、构建解决方案的哲学。它引导读者深入理解“解决问题”这个行为本身,探究其背后共通的逻辑脉络,并提供一套系统性的思考框架,帮助我们在面对任何复杂挑战时,都能以一种更加清晰、高效、富有创造力的方式迎刃而解。 第一部分:拨开迷雾,看见问题的本质 在信息洪流中,我们常常被表象所迷惑,被细节淹没。这本书首先着眼于如何“看见”问题的本质。我们将从识别问题的关键要素入手,学习如何剥离无关紧要的信息,聚焦核心矛盾。这不仅仅是简单的“提取”和“筛选”,而是一种深度的洞察力训练。我们会探讨不同类型问题的共性,例如,是求最优解?是分类问题?还是模式识别?理解问题的本质,如同在星空中找到北极星,为接下来的探索指明方向。 洞察分析: 我们将深入剖析“为什么”一个问题值得解决,它的根本驱动力是什么?它与哪些更宏观的目标相关联?通过对问题根源的探寻,我们能够避免陷入“头痛医头,脚痛医脚”的陷阱,从源头上找到真正有效的解决方案。 分解与重构: 复杂的问题常常令人望而生畏。这本书将教会我们如何将一个庞大的挑战分解成一系列更小、更易于管理的部分。这种“分而治之”的策略,不仅能降低解决问题的难度,更能让我们在每一步都取得切实进展,保持前进的动力。我们会学习如何识别这些子问题的内在联系,并思考如何将它们重新组合,形成一个整体的解决方案。 抽象化思维: 现实世界的问题千变万化,但很多问题在本质上具有相似的结构。本书将引导读者掌握抽象化的能力,即从具体的事例中提炼出普适的规律和模型。这种抽象能力是通向更高级思维的关键,它允许我们将已有的知识和经验迁移到全新的领域,解决前所未见的问题。我们会通过一系列思考练习,逐渐培养这种“举一反三”的智慧。 第二部分:构建桥梁,连接已知与未知 一旦我们清晰地理解了问题的本质,下一步就是寻找解决它的路径。这条路径往往横跨已知和未知之间。这本书将侧重于如何有效地利用我们已有的知识和资源,并思考如何探索和获取未知的信息,从而搭建起通往解决方案的桥梁。 模式识别的艺术: 自然界和社会中充满了各种各样的模式,从数列的规律到事件的周期性,再到人际互动的倾向。识别这些模式,是理解事物运行机制和预测未来走向的关键。我们将探讨如何通过观察、归纳和演绎,来发现隐藏在数据和现象背后的模式。这不仅仅是数学上的技巧,更是一种敏锐的观察力和逻辑推理能力的结合。 类比与启发: 很多时候,我们能够找到解决新问题的灵感,是因为我们曾见过或听说过类似的场景。本书将强调类比思维的力量,即通过寻找不同领域事物之间的相似性,来启发新的解决方案。我们会学习如何有意识地运用类比,将已经解决的问题的思路应用到当前的问题上,或者从成功的案例中汲取经验。 信息搜集与验证的策略: 在解决问题的过程中,我们常常需要搜集更多的信息来支撑我们的判断和决策。这本书将指导读者如何更有效地搜集信息,如何辨别信息的可靠性,以及如何通过多种渠道交叉验证,确保我们获得的信息是准确和全面的。这包括对信息源的评估,对数据背后逻辑的审视,以及如何避免被片面或错误的信息所误导。 构建假设与验证: 解决问题往往是一个不断尝试和修正的过程。我们会学习如何基于已有的信息和洞察,提出合理的假设,并设计简单有效的方法来验证这些假设。这个过程如同科学研究,通过提出问题、形成假说、进行实验(思考实验或实际操作),然后根据结果调整方向。 第三部分:精益求精,优化解决方案 找到一个可行的解决方案是第一步,但真正的智慧在于如何不断优化它,使其达到最佳状态。本书将引导读者思考如何让解决方案更有效、更稳健、更具扩展性。 效率的考量: 在资源有限的情况下,效率往往是衡量一个解决方案优劣的重要标准。我们会探讨不同策略在执行效率上的差异,以及如何通过对过程的细致分析,找到提升效率的切入点。这并非仅仅是“快”,而是“在满足需求的前提下,以最少的时间、最少的资源完成”。 稳健性与鲁棒性: 现实世界充满了不确定性,一个好的解决方案应该能够经受住各种意外情况的考验。我们将探讨如何设计出更具稳健性的方案,使其在面对输入数据波动、外部环境变化等情况下,依然能够稳定运行,甚至能够优雅地处理错误。 权衡取舍的艺术: 在实际的解决方案设计中,我们常常需要在多个目标之间做出权衡。例如,可能需要在速度和精确度之间进行选择,或者在成本和功能之间进行平衡。本书将帮助读者理解权衡取舍的必要性,并提供一套思考框架,帮助我们在复杂的决策中做出最优的选择。 可扩展性与适应性: 随着时间的推移,问题本身可能会发生变化,或者对解决方案的需求会增加。本书将引导读者思考如何设计具有良好可扩展性和适应性的解决方案,使其能够随着需求的增长而平滑地扩展,或者能够轻松地适应新的环境和要求。 第四部分:灵活运用,应对未知挑战 这本书的最终目标是培养读者一种“举一反三”的能力,一种面对未知挑战时,能够自信地运用所学思维模式去分析和解决问题的能力。 跨领域的迁移: 通过大量不同场景的案例分析和思考练习,我们将看到,那些在数学、物理、计算机科学等领域被称之为“算法”的底层逻辑,在很多看似不相关的领域,如项目管理、商业策略、甚至日常生活中的问题,都拥有惊人的相似性。这本书将帮助读者打破学科壁垒,将通用思维模式迁移到更广泛的领域。 创造力的催化剂: 很多时候,解决问题的创新突破,并非来自于全新的知识,而是来自于对已知事物的不同组合和重新审视。本书所强调的逻辑分析、模式识别和分解重构等思维方式,将为读者的创造力提供坚实的基础和有效的工具。我们会鼓励读者跳出固有的思维定势,用一种更开放、更灵活的视角去探索解决方案的可能性。 持续学习与进化: 解决问题的能力并非一成不变,它需要我们不断地学习、实践和反思。本书将提供一个持续学习的起点,鼓励读者在日常的学习和工作中,有意识地运用这些思维模式,并在实践中不断完善和发展自己的问题解决能力,成为一个终身学习者和高效的问题解决者。 这本书不是关于“学到”多少现成的解决方案,而是关于“学会”如何去发现、创造和优化解决方案。它将是一段充满智慧启迪的旅程,带领读者穿越思维的迷雾,抵达逻辑清晰、模式可见、解决方案触手可及的彼岸。它旨在赋能读者,让他们在面对任何复杂性和不确定性时,都能拥有一套属于自己的、强大的思维利器。