半部论语治天下: 《算法设计指南》(本科教学版)
算法设计指南(本科教学版)
0. 为何是半部
算法世界中的故事由作者娓娓道来, 各种设计技术非常自然地穿插其中, 读者更像是在阅读一本小说, 你没看错, 这就是Steven Skiena教授的名作The Algorithm Design Manual. 要是在美国亚马逊网站上输入“Algorithms”, 可以发现这本书长期排名居于前五, 而且还一度是计算机算法类的最畅销书籍(Best Seller). 你可随手翻开一页往下读去, 肯定觉得妙趣横生不忍释卷, 仿佛就像走进了Skiena教授的课堂一样, 这也许是它广受欢迎的主要原因吧. 此外, Skiena教授的主页上还提供了在线课程视频, 若是身临其境更能深入体会其妙.
考虑到国内算法课程教学情况, 我们认为本书的卷I(讨论“实用算法设计”)单独成书比较适合讲授, 而且携带这本“算法小说”也更为方便. 为此我们征求了作者本人的同意, 特将这本书的精简版(仅包含卷I)译出以飨读者. 不过, 阅读是一个可能随时中断的过程, 而原书中许多段落只能在课堂讲授的语境中才能理解, 为此我们补充了一些起承转合的词句. 此外, 作者对很多掌故信手拈来, 而且经常还有弦外之音, 妙则妙哉, 可是对于不能一窥堂奥的读者实为遗憾, 中译本尽量对它们给出注释.
1. 资源下载
我在GitHub上给出了如下材料：
- 中文版序
- 译者的话
- 前言
- 目录
- 第10章：如何设计算法
后续我们将补充算法问题便览部分, 也就是《算法设计指南》后半部分的精髓. 可在原书配套网站的"By Problem"处查阅, 包含如下类型的问题:
- 数据结构
- 数值问题
- 组合问题
- 图问题: 多项式时间问题
- 图问题: 难解问题
- 计算几何
- 集合与字符串问题
2. 一本书主义之"吸星大法"：《算法设计指南》
注: 原文载于我的微信公众号"算法时空".
吸星大法
对于程序员来说, 算法可以说就是内功. 大家都知道, 要想功力高超, 必得勤学苦练.
可是, 如果功力不够又很想去行走江湖, 怎么办呢?
少年, 看你骨骼清奇, 是万中无一的算法奇才, 这里有本秘籍《算法设计指南》(本科教学版), 号称算法中的“吸星大法”, 马上就要上市了!
哇, 丁春秋的吸星大法! 居然还有这样的神作? 嗯, 它早已名噪江湖了:
《算法设计指南》由算法领域的知名专家Steven Skiena教授编写, 其主要内容包括基本算法设计、算法分析、数据结构、排序与查找、图算法、动态规划以及难解问题与近似算法. Skiena教授荣获了IEEE计算机科学与工程教学奖, 这本书则是其教学理念的最好展现. 该书长期居于算法畅销教材前列, 是一本不可多得的“算法设计指南”, 它不仅能作为计算机相关专业算法课程的教材, 对于相关领域从业人员亦是极具价值的参考书.
看完这个评价, 是不是很有兴趣? 且听我慢慢道来, 顺便告诉你《算法设计指南》(本科教学版)这本秘籍背后的故事.
关注算法思想
曾经看到个笑话: C++程序员面试时要对一个长为10000的数组a排序, 应聘者写下了一句:
std::sort(a, a + 10000);
考官莞尔一笑, 转向了下一题.
注: 当然上面的这句也可以写成:
std::sort(std::begin(a), std::end(a));
《算法设计指南》这本书的思想基本就是这样, 能用现成的库函数就不要自己写, 优先把程序组织起来. 以排序来说, 作者认为先把数据排序再进行处理是非常重要的一招, 有了排序之后的数据, 我们就可以:
- 运行二分查找.
- 找到差异最小的一组元素.
- 统计元素的频率分布.
- 构造出点集的凸包.
由此可以看出, 我们主要应该去关注算法思想, 再借助绝顶高手的深厚内力(不妨挑战一下std::sort函数的性能), 便可迸发出很强的武功招数. 事实上, 那些自己写排序的中级选手, 还真打不过你这个只会吸星大法的毛头小伙子呢.
更妙的是, 目前各种库函数层出不穷, 随随便便就可以吸取众多大牛的内力, 构建程序时只需心无旁骛地从实际出发建立合适的模型便可马到功成.
化为己有
《算法设计指南》不单授你吸取功力的方法, 还注重将内力逐渐化为自己的技能. 例如动态规划这种内力向来难以融合到体内, 而《算法设计指南》独创一派, 让你自己在意念中构造动态规划, 便能左右逢源. 秘籍里说得好:
一旦你理解了动态规划这种方式就会发现很好用, 它也许应该是最简单易用的算法设计技术了. 事实上, 我发现完全依靠自己思考来设计动态规划算法更为简单, 而在书里去查现成的算法还得找半天. 也就是说, 你要是还没有真正理解动态规划, 那它看起来就如同魔法一般. 你得弄明白其中的窍门才能去用它.
说到这里, 你肯定非常想看看如何完全依靠自己思考设计动态规划了.
算法世界搭车客指南
要避免所吸取的内功让你走火入魔, 那么最好按照作者推荐的内功心法来. 《算法设计指南》推荐了很多优秀的算法库和资源, 而这些精髓都在(http://www3.cs.stonybrook.edu/~algorith/), 作为新时代的算法设计者, 肯定更愿意在网络上阅读这些内容吧. 作者在前言里提到:
有位颇具洞察力的评论家因为这份便览非常强大的缘故, 将我的这本书称作“算法世界搭车客手册”(The Hitchhiker’s Guide to Algorithms).
能被评为“算法世界搭车客指南”, 和闪耀着宇宙终极答案(大家都知道是42)的那本《银河系搭车客指南》相提并论, 确实是一份极高的评价.
译者注释
这本书里面有很多典故, 还有很多笑话. 有些地方要是不认真看, 可能还理解不了作者的深意. 虽然吸星大法功力强大, 也需要指点一番才能理解.
多年以前很是佩服钱钟书老先生的《管锥编》, 可惜至今放在书架上未能看懂, 但先生的风范我是非常佩服的. 一条注释虽然短小, 但也是经过深思熟虑之后写出的结论, 而且有时候看注释比看原文更有趣.
所以, 我在翻译《算法设计指南》的时候践行了钱先生的理念, 为这本书编写了270条翻译注释(也就是说随手翻开就能看到“译者注”). 当然, 有的读者不喜欢注释, 他们喜欢那种读下顺畅的感觉而觉得注释很啰嗦, 只能对这部分读者报以歉意了.
War Story
“设计”是本书的核心, 作者不但以生动有趣的语言讲授了算法设计中的常用技术与思想, 还着重教导我们应从已有经典设计和实现中汲取力量来完成问题求解, 而这正是一个优秀算法工作者所必备的素养. 为了更全面真实地展现作者的算法设计观, 《算法设计指南》每章都给出了若干取自现实案例的精彩War Story, 读者可以从中深刻体验到优秀算法设计的曲折历程. 为了减轻阅读的难度, 作者淡化了繁难的算法分析而仅仅给出性能结论与对比, 这在同类算法书中是相当少见的.
实际上, War Story就是实战案例, 学习了内功心法再配合这个, 实在是无敌了. 关键在于, Skiena教授的文笔风趣幽默, 谈笑间灰飞烟灭收拾了许多算法难题, 这滋味着实酸爽哪!
一睹为快
当然, 作为微博/微信公众号“算法时空”的读者, 你将提前看到如下新鲜发布的材料——也就是《算法设计指南》(本科教学版)的目录和样章. 我们专门选择了第10章这份“吸星大法”的要诀赠送给你!
选购
《算法设计指南》(本科教学版)由清华大学出版社出版(2017年7月), ISBN号为978-7-302-45734-3, 定价为69元, 欢迎大家持续关注, 喜欢这本吸星大法秘籍的就转发到朋友圈吧!
