前 言 许多专业的程序员其实并不太愿意去解决算法设计问题, 这真令人遗憾, 因为算法设计技术构成了计算机科学的核心实用技术之一。 本书意在作为一部关于算法设计的指南式读物, 从而让在校学生及计算机专业人员领略组合算法技术的无限风采。全书分为两卷------技术和资源: 前者是对计算机算法设计和分析技术的一般性指引; 而后者则可以让你进行查阅和参考, 它可以视作一本``目录册'', 其中每一个条目都包含了算法资源、程序实现和众多参考书目。 致读者 本书自1997年经Springer-Verlag初版之后, 各种不同版本已经售出了6万余本, 这本书如此受欢迎, 我着实倍感欣慰。此外, 该书还被翻译成中文、日文和俄文出版。本书被视为一部独一无二的指南, 能教你用算法解决实际中的许多常见问题。 从本书第2版于2008年问世至今, 这个世界有了许多改变。现在的软件公司在招聘面试中愈发重视算法问题, 导致我这本书一下子更火了, 特别是许多成功的求职者都确信本书对他们准备面试很有帮助。 算法设计应该属于计算机科学中最经典的一个领域, 尽管如此, 它还在持续发展和更新。随机化算法和数据结构如今越来越重要, 尤其是基于散列的技术。近期还有一些突破改进了不少已有最佳算法的复杂度, 例如寻找最小生成树、图同构和网络流等基本算法问题。实际上, 我们若将现代算法设计和分析的起源定在1970年左右, 那么从本书第2版诞生到如今这个时间段在整个现代算法的发展历史中占了20%之多。 所以, 是时候推出我这本书的新版了, 我们将纳入算法领域和工业界的新变化, 以及从数百名读者那里收到的反馈意见。第3版的主要目标是: 在本书的卷I(实用算法设计)中介绍或拓展诸如散列、随机化算法、分治、近似算法以及量子计算等重要主题。 对本书的卷II(算法世界搭车客指南)中更新所有问题条目的参考资料。 充分利用彩色印刷技术的优势,1 制作内容更丰富且视效更醒目的插图。 本书中有三方面尤为受人钟爱: (1) 算法世界搭车客指南(The Hitchhiker's Guide to Algorithms)2; (2) 算法征战逸事; (3) 随书电子资源部分。这些特色在第3版中得以保留并有所加强: 算法世界搭车客指南------由于收集整理某个算法问题的现有进展是一项艰巨的任务, 因此本书提供了在实际中最重要的75个问题之简要介绍并汇集成一套``算法问题目录册''。通过查阅这套目录册, 在校学生或从业人员可以很快地确定他们要处理的问题名称和该问题的研究现状, 以及如何在现有研究工作的基础上去解决所面对的实际问题。 本版基于最新研究结果和应用对每一节进行了修订完善, 我们特别关注对每个问题所能找到的软件实现这一部分内容的更新, 并对诸如GitHub等新兴平台有所体现, 而这些都是上一版未曾涉及的。 算法征战逸事------为了让读者更好地去观察了解算法问题在实际中究竟是如何出现的, 我们在书中特别准备了一系列算法征战逸事(War Story), 或者可称作``我们与真实问题交战所经历的故事''。这些故事的寓意是, 算法设计和分析不仅仅是理论, 它更是在你真有需要的时候可以派上用场的一个重要工具。 第3版保留了第2版中那些最精彩的算法征战逸事并予以修订, 此外还针对随机化算法、分治以及动态规划等主题新增了若干故事。 在线资源------我的网站www.algorist.com提供了完整的讲义和解答维基(Wiki), 而该网站已与本书同步更新。此外, 我的课程视频在YouTube上播放了超过90万次。 我们在本书中没有讲到的内容也同样重要。本书不强调以严格数学的形式进行算法分析, 所以大多数分析论证以较为直观的方式给出, 而你在这本书中一个定理也找不到。如果需要了解更多的细节, 读者应该去研读书中所提到的程序和参考文献。一言以蔽之, 这本指南的目标是让你尽可能快地走上正确的方向。 致教师 本书所涵盖的素材足以开设一门标准的``算法导论''课程。我们假设读者已学完相当于中级编程的课程(通常名叫``数据结构''或``计算机科学II'')。 你可在www.algorist.com下载用于讲授这门课程的一整套课程幻灯片(slides)。此外, 我还基于这些幻灯片录制了在线视频讲座, 可供一个完整学期的算法课程使用。通过神奇的互联网, 让我来帮你教授这门课! 我们在全书中做了很多教学法方面的改进: 新的素材------为了反映算法设计领域的新进展, 第3版增加了随机化算法、分治和近似算法等新章节, 并深入研讨了散列等主题。不过我还是认真聆听了读者的诉求, 他们拜托我把这本书控制在适度的篇幅之内。我颇为痛苦地删掉了一些不太重要的内容, 最终将相比于第2版所扩展的内容控制在10%之内。 更清晰的表述------在十年之后通读以前所写的文本, 我震惊地发现其中不少章节看起来颇为虚无缥缈, 而另一些地方却是一团乱麻。这本手稿的每一页都经过了修订甚至于重写, 力求更为清晰、准确和流畅。 更多面试资源------对于面试前的准备工作而言, 本书仍然是一本很受欢迎的材料。不过这个世界发展速度太快, 因此第3版纳入了更多且更新的面试题, 包括与诸如LeetCode和HackerRank等网站相关的编程挑战。我们还单独加入了新的一节, 为如何以最佳状态准备面试给出了建议。 停下来想想------我的每一节课程讲座都会以一个``今日问题''开篇, 我会以此阐明我在解决某个特定主题的习题时的思考过程: 从错误想法开始, 不断调整改进直至最终解决。我们的第3版为读者提供了更多的``停下来想想''章节, 可承担类似的使命。 更丰富且更精良的课后习题------与旧版相比, 本书第3版提供了更丰富且更精良的课后习题。我增加了一百多个兴味盎然的新习题, 并删去了一些不那么有意义的问题, 还对某些含混不清或者令人迷惑的问题进行了澄清。 更新代码风格------第2版的特点是用C语言实现算法, 以此替换了某些基于伪代码的描述, 这样还能增补更多实现细节。这种做法得到了广大读者的极大认可, 不过仍然有些朋友批评我的编程手法有些老旧。在第3版中所有程序代码都已修订和更新, 并系统性采用彩色字体突出显示。 彩图------我有另一本与本书所配套的书籍《数据科学指南》选用了彩图印制, 而我惊喜地发现这样会让概念传达更为明晰。现在本书中的每一幅插图均以鲜明的色彩绘制, 此外文本审稿过程也进一步提升了大部分插图中的内容质量。 致谢 每十年更新一次书籍的题献主要是关注时间流逝中的世事变幻。自这本书问世以来, Renee成为我的妻子, 又变成了我两个孩子(Bonnie和Abby)的母亲, 而这两个孩子现已长大成人。我的父亲离开了人世, 但我的母亲和兄弟(Len与Rob)仍与我相伴, 并且在我的生命中占据了非常重要的地位。我将这本书献给我的家人, 不管是新成员还是老成员, 无论尚在或是离去。 我要感谢以下人士, 他们为新版做出了很大的贡献: Michael Alvin、Omar Amin、Emily Barker和Jack Zheng在构建新网站的基础架构以及有关手稿准备的各项事宜中提供了关键性的帮助。旧版中这些工作是由Ricky Bradley、Andrew Gaun、Zhong Li、Betson Thomas和Dario Vlah承担的。坦佩雷大学的Robert Piché(可谓我这本书全世界最仔细的读者)以及石溪大学的学生Peter Duffy、Olesia Elfimova和Robert Matsibekker阅读了本版的早期文本, 在处理勘误方面省去了我乃至于诸位读者朋友的很多麻烦。此外, 还要感谢我在Springer出版社的编辑Wayne Wheeler和Simon Rees。 书中有不少习题由我的同事原创, 还有些习题是受到了其他教材的启发。在习题流传多年之后, 要弄清其最初出处确实是个挑战, 不过我的网站给出了每个问题的来源(若是我没记错出处的话)。 我对算法所了解的很多东西都是和我的研究生一起学到的。他们中的很多人(Yaw-Ling Lin、Sundaram Gopalakrishnan、Ting Chen、Francine Evans、Harald Rau、Ricky Bradley和Dimitris Margaritis)都是相关算法征战逸事中的真实英雄。Estie Arkin、Michael Bender、Jing Chen、Rezaul Chowdhury、Jie Gao、Joe Mitchell和Rob Patro一直都是我在石溪大学的朋友和算法领域的同事, 与他们共事非常令人开心。 说明 作者大度地接受对任何不足之处的批评乃是一个传统, 可我是个例外。本书中所出现的任何错误、缺陷或问题均为他人之过, 不过你若是指出来我会非常感激, 因为这样我就可以去追究相关人士的责任了。3 Steven S. Skiena 石溪大学(Stony Brook University)计算机科学系 纽约 石溪 11794-4400 2020年8月 1 译者注: 中文版采用黑白印刷, 插图已重新处理, 代码保留普通样式。前言部分的后续内容依然会提到彩色印刷问题, 以下不再说明。 2译者注: 脱胎于科幻名著《银河系搭车客指南》(The Hitchhiker's Guide to the Galaxy)。 3译者注: Jeff Erickson在他的算法教材中同样开了一个玩笑: ``All of which are entirely Steve Skiena's fault''。

• 暂无课件
• 暂无样章
• 暂无网络资源

扫描二维码
下载APP了解更多

版权图片链接