纸上得来终觉浅,绝知此事要躬行。
在小异的印象中,刷算法题似乎是每个有追求的程序员都乐此不疲的一件事,因为算法是编程最重要的基础。刷题的前提是要会算法,正所谓“基础不牢,地动山摇”,对算法的掌握在一定程度上可以看出一个人的编程水平。
如何学算法一直是摆在新手程序员面前老大难的问题。小异今天带来的这本哈佛大学、华盛顿大学、康奈尔大学等名校都在用的书——《算法设计》,就是为了解决这个老大难问题的。
▲ 风靡国内外的经典算法教材
01
取康奈尔大学多年算法课之精华
20世纪90年代,计算机技术如烈日般照耀着世界,这个领域对所有人有着非凡而强烈的吸引力,公众对于信息技术的迷恋超乎寻常。康奈尔大学的计算机相关课程也吸引了无数优秀的学生前来参加,同时有无数优秀的教师参与授课。
学校的一系列算法课程也跟着计算机领域的发展而得到发展,许多优秀的教师为这些课程提出了自己独特的思想与方法,包括Juris Hartmanis、Monika Henzinger、John Hopcroft、Dexter Kozen、Ronitt Rubinfeld和Sam Toueg等人。
基于这一系列的算法课程,本书作者乔恩·克莱因伯格(Jon Kleinberg)和伊娃·塔多斯(Eva Tardos)着手写一本用于本科和研究生的算法入门教材。经过精心的编写,这本书的初稿首先出现在康奈尔大学算法课的老师们面前,他们对本书中的材料以及有关该领域本质的更广泛问题进行了无数次讨论,对初稿的修改提出了诸多有益的建议与意见。
然后,作者把初稿作为实验教材,发放给自己的本科和研究生学生去使用,得到了最真实有效的反馈和意见。同时,在早期阶段,华盛顿大学的Anna Karlin老师大胆地使用初稿作为她在学校的课程教材,并获得学生的普遍好评,学生们认为本书内容设置合理有趣,非常适合作为算法初学教材。之后,越来越多的人将它用作课程教材或教学资源,有了这些大量的一线教师的投入与反馈,作者对初稿做了许多修订,使其更加适合老师教学和学生学习使用。
在最后,经过塔夫茨大学、马里兰大学、密歇根大学、宾夕法尼亚大学、布朗大学等大量名校名师和无数学生的实践使用,作者得到了许多详细而深入的评阅意见,这些意见为最终稿的改进提供了非常大的帮助。
当本书出版,立马形成了一股抢购浪潮,因为本书是专门为算法课入门而写的,无数名校师生争相购买使用。更多的计算机从业人员和爱好者也很快将这本书拿到了自己手上,毕竟大家都知道,一本好的算法书对提升自己的算法能力有多么重要。
本书两位作者都是康奈尔大学的教授,他们不仅在算法教学上有着极其丰富的经验,对各自领域也都做出了极大的贡献。
02
聚专注解决问题算法专家之积累
乔恩·克莱因伯格本科就毕业于康奈尔大学,在麻省理工学院获得博士学位之后进入IBM研究院工作。从IBM出来之后,他回到母校康奈尔大学,开始了他的教学与研究生涯。
▲ 年轻时的乔恩·克莱因伯格
如今,乔恩·克莱因伯格在康奈尔大学更多的是把精力放到算法与网络,还有信息组合结构的数学分析与建模的研究工作上,最近的教学课程Choices and Consequences in Computing ,The Structure of Information Networks和Networks,分别是在2022年春季、2021年秋季和2017年秋季开设的。
在算法与网络领域研究这么多年,他获得过NSF职业奖、ONR青年研究奖、马克阿瑟基金会奖学金、帕卡德基金会奖学金、西蒙斯研究员奖、斯隆基金会奖学金等数不清的奖项,得到了业内外的一致认可。
同时,他还是美国国家科学院院士、美国国家工程院院士和美国艺术与科学学院成员。2006年还获得了国际数学联盟颁发的内万林纳奖。
他以解决重要而且实际的问题,并能够从中发现深刻的数学思想而著称。他发明了著名的“小世界论”和万维网搜索算法,设计的HITS算法启发了谷歌的PageRank算法。他的这些思想在本书中体现得淋漓尽致——本书提出并解决了200多个详细而实际的算法问题。
他200多篇的技术论文凝聚了多年来的研究成果,有173篇是在康奈尔大学期间发表的。这些论文帮助了无数人开展自己的研究和学习,在谷歌学术上其论文引用超过100000次,单篇最多引用超过14000次。
▲ 乔恩·克莱因伯格的谷歌学术页面
伊娃·塔多斯是一位来自匈牙利的优秀女性数学家,毕业于匈牙利布达佩斯的Eötvös Loránd 大学,1989年加入康奈尔大学执教。2006年至2010年间,她担任康奈尔大学计算机科学系主任,目前是计算机与信息科学学院副院长。
▲ 正在给学生上课的伊娃·塔多斯
她是算法、算法博弈论和理论计算机科学的基础贡献者,是ACM研究员、美国数学学会研究员,获得过帕卡德、斯隆基金会和古根海姆奖学金。2013年,她被授予IEEE冯·诺依曼奖章。
▲ 2013年伊娃·塔多斯获冯·诺依曼奖章
在康奈尔大学,她与乔恩·克莱因伯格在教学和学术研究上有着大量合作,两人开设的算法与网络课程在学校极受欢迎。
正是因为有着两位经验丰富的教授主笔,加上其他优秀的算法教师和工作人员提供的帮助,本书中的内容生动有趣、适合算法入门,成为美国诸多大学的本科和研究生算法课程教材。
03
成极具启发性的算法经典之教材
算法思想无处不在,在计算机科学和其他领域中的体现都很明显。
这本书真正地在教算法
作为许多学校使用多年的经典教材,本书有着得天独厚的优势与特点——这是一本问题集。
本书包含200多个问题,这些都是作者在康奈尔大学教学课程的一部分,几乎所有的问题都在课外作业中被开发,或者在考试中进行了测验。这些问题是本书的重要组成部分,其结构与整本书相互融合,保持一致。
这些来自计算机科学和其他领域的问题,每个都有着详细而通俗易懂的文字描述,这正是本书所强调的一点——理解和描述问题。对于这些问题的解答,本书是这样引导的:建立必要的符号和形式化,设计算法,然后分析这个算法并证明它的正确性。这是一个完整的过程,带有完整解释的算法、运行时间的分析和正确的证明。
同时,本书有大量篇幅用于算法问题的形式描述,以及针对该问题的算法设计和分析。这种结构可以让读者很好地了解如何讨论计算机应用中出现的问题,并对这些问题的解决方法做出详细的分析。
这相较于其他大部头算法图书有着更好的阅读体验,像近800页的《算法导论》很多情况下都沦为了书架上吃灰大军的一员,正是因为它有着大部头被人诟病的通病:内容几乎都是一大段伪代码加上一大段颇为啰嗦的解释,读起来很是费劲。这种形式有时候会让人的注意力莫名其妙地集中不起来,使书本传达的信息难以有效地被读者接收。
算法本身的抽象度就很高,再加上伪代码和大量的文字解释,读者理解起来就需要花费更多的精力,甚至难以理解。
而且,本书将重点放在算法背后的数学结构之上,并不拘泥于代码实现。通过分析问题、提出算法、证明算法的过程,读者能够发现和体会算法的美与巧妙。
学习算法是为了解决实际问题,而不是简单地掌握一些代码。了解算法的本质,认识它背后的数学结构,才是最重要的——这也是前面说的本书的目标。
其他一些算法图书就在这方面做得有点不好,比如《算法(第4版)》使用的就是Java语言,有大量的Java代码。让算法与特定语言绑定太深,花费了大量篇幅去描写Java 的API,很多读者在阅读的时候产生了一系列疑问:算法是什么?是Java的算法吗?
那些书脱离了算法的本质——数学结构,过于重视某种特定语言,读者在阅读的时候要么需要有语言基础,要么需要消耗大量时间去查阅相关语法、API,学习成本过高,得不偿失。
好的算法教材不能拘泥于某种特定的编程语言,不管读者掌握的是C、Java、Python还是什么语言,他们都能看懂、学会算法,这本书才能算是一本好的算法教材。如果因为使用语言不同,就无法使用一本专门的算法教材,就违背了算法基础功能——解决问题。
如果问题是一条河,这本书并不是扔给我们一座桥让我们直接过去,而是教会我们思考为何并且如何去建造一座桥,以跨过这条河。这样,我们在以后再遇到其他更宽的河时,不会因为能够获取的桥长度不够而过不去。
本书内容概要
基于这些目标,本书经过精心编排,共划分了13章。
其中,第1章介绍了一些有代表性的算法问题,这些问题不仅仅是一个展示,更是对后续内容的一个预告。问题之间相互关联,作为里程碑,随着本书的推进而再次出现。
第2章和第3章介绍了一些基础知识,比如用于分析算法的关键数学定义和符号、图算法的基本定义和算法原语。同时,这两章还介绍了许多基本数据结构,相信大家都知道,这是算法中非常重要的内容。
第4章至第7章则讲了4种主要的算法设计技术:贪心算法、分治法、动态规划和网络流。
第8章和第9章介绍计算难解性,大部分内容都围绕NP完全性。
第10章至第12章承接前面章节的内容,介绍3种处理计算难解性的技术,即识别结构上的特殊情况、近似算法和局部搜索启发式算法。
最后一章是关于随机化在算法设计中的应用。
这些内容最终形成了一本503页的教材,其内容翔实而不繁杂,每一处都针对特定问题提出对应的解决方案,并展开讲述,启发读者进行更深入地思考。
如何使用本书的材料资源
因为本书的最初目的是作为本科和研究生阶段的教材,所以其内容经过认真的安排,每章的前几节都适合本科生,后面的“高级章节”更适合研究生。比如在康奈尔大学的本科阶段使用时,作者和其他算法老师们大约一节课只讲一节书本内容,如果讲不完,会将这些额外的材料作为学生可以在课外阅读的补充。
而且,他们会跳过那些加星号的章节,虽然里面包含了重要的内容和主题,但是对本科算法课程来说它们并不是那么重要,有时候难度还有点大。
对那些研究生,和已经投身于各领域工作的有经验的程序员们来说,后面的内容应该成为他们的重点学习对象。当然,把本书用来复习或补充背景知识也是非常有效的。
同时,本书提供了由普林斯顿大学的Kevin Wayne开发的一套包含教学PPT在内的配套资料,老师可以用来辅助算法教学,普通读者也可以下载用作自学辅助。
无论是作为算法入门图书还是进阶图书,这本书都能够提供合适的内容,教会读者学会使用真正的算法思想解决问题,走向计算机领域更深、更远之处。
04
获行业大咖、无数读者之力荐
在本书还是初稿的时候,它就引起了大量学校教授和业内人士的注意,他们对本书给予了高度的认可并给出了专业的意见。
所以出版之后,很多领域内的大佬们也不吝美言,对本书赞誉有加。
“这本书是我看过的非常优秀的本科生教材,我认为它将为算法教材的新时代奠定基础... (它采用)新颖的教学方式,更强调算法的设计并且配有丰富的练习 。”
——Dieter van Melkebeek,威斯康星大学麦迪逊分校
“这本书完美融合了直观性和严谨性,包含了计算机科学所有领域的各种奇妙的应用,并且提供了独特的问题分析和算法设计方法”
——Anna R. Karlin,华盛顿大学
“两位作者将算法思想与真实问题联系起来的工作极其了不起,并且完成得非常精彩。
——Michael Mitzenmacher,哈佛大学
同时,使用了本书的读者们也认识到这本书的独特,为自己选择本书而感到庆幸。
这本书侧重于如何设计算法,而不是众所周知的标准算法。因此,如果你想培养一种解决算法问题的思考过程, 这本书是最佳选择。
——Abhishek Pratap Singh, 读者
我在这本书和相关课程上度过了非常愉快的时光,这本书提供了学习算法的一个非常好的方法。如果我没记错的话,它甚至对“快速傅立叶变换”有了很好的概述。
——Travis Johnson,读者
这是一本关于算法的非常好的书,尤其是写得非常深入,所有的内容都易于理解和阅读,适合算法和高级算法课程,习题也很不错。
——Kory,读者
这本书是我们学校上算法设计课的教材,此书的作者能够通过一些实际的例子来阐明算法枯燥的理论,足以证明作者在算法方面的造诣之深。此书最精彩的部分是把算法的理论跟实际问题结合起来,让读者感觉不到枯燥,非常适合第一次接触算法设计的计算机专业学生,课后的习题也有答案可以参考。总之,我个人认为这是一本很不错的书。
——决漫,读者
作为一名教科书hater,我居然对这本书恨不起来,哈哈!优秀的CS教科书,示例出色,并且练习题很好!
——动物凶猛,读者
最后,小异把作者在本书中的话送给大家:
我们希望无论你们的计算追求把你们带到什么地方,你们都会发现本书是令人愉悦的、有用的指南。
好的算法教材不多,希望这本于你正合适,可以在你的算法技能提升路上提供帮助。
文章编辑:沙鱼 审校:桐希 刘雅思
参考来源:
[1] Jon Kleinberg's Homepage..
[2] Éva Tardos - Wikipedia..
[3] Eva Tardos | IEEE Computer Society..
[4]乔恩·克莱因伯格,和伊娃·塔多斯.算法设计.[M]北京:人民邮电出版社,2021.
—END—
,