[转]算法的上帝——Donald E.Knuth

5 月 23rd, 2010 | Posted by | Filed under 随笔日记

本文内容遵从CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
网址: http://www.penglixun.com/life/diary/donald_ervin_knuth.html

Knuth

开始介绍前先膜拜之~

密尔沃基市,是美国威斯康辛州最大的城市。1938年1月10日,圣诞刚过不久,密尔沃基市民像往常一样平静地生活着。咖啡店里,有人在议论着罗斯 福总统的救市新政策,有人在议论着到底该不该限制公民持枪。而更多的人呢,则一边品尝着密尔沃基闻名全国的啤酒,一边听着广播里面的实时战况:侵华日军登 陆青岛了。谁也没有想到,这个平静的日子将载入这座城市的史册。这天,密尔沃基路德教会高中的一名印刷管理员,高兴地迎来了一个健康的儿子。他为儿子取了 一个响亮的名字,这个名字在不久的将来,成为了计算机编程艺术的旗帜:Donald Ervin Knuth。

为了方便讲述,请各位读者允许我先剧透一件39年后的事儿。在1977年Knuth造访中国前夕,姚期智的夫人为他取了一个中文名字:高德纳。在下面的故事里,我们就使用这个名字来称呼他。

高德纳天资聪颖,他的超凡智力在8岁时就显示出来了。当时,一家糖果商在孩子们当中举办了一项有趣的比赛,要求用“Ziegler’s Giant Bar”里面的字母,写出尽可能多的单词。裁判事先准备了一份2500个单词的列表,可他却远远低估了小选手的能力,高德纳令人惊讶写出了4500多个单 词,毫无疑问地获得了冠军。他为学校赢得了一台电视机,还为每个同学赢得了一只棒棒糖,他的赛后感言是,我还能写出更多。

高德纳的高中就读于他父亲所在的路德教会高中,在这期间,他发表了此生第一篇学术文章。尽管如此,但这个充满了才华和个性的年轻小伙,并没有把心思 放在科学上,他的主业是音乐和作曲。他的老师,甚至包括他自己,十分怀疑他将来进入大学后,是否能够顺利学习数学。这种想法给高德纳造成了不小的自卑,尽 管他的平均分是学校历史上最高的。不过有句话说,真正的天才是1%的灵感加上99%的汗水,这话用在高德纳身上毫不夸张,18岁的他,在进入大学之后,丝 毫没有向数学屈服,而是花费无数的课余时间,大量练习数学难题,这种努力的劲头再加上他的天份,使他很快就在数学方面超过了其他同学。其实我们与其关注一 些科学家们不可模仿的机会和天赋,莫不如更关注他们如何面对困难和挫折。高德纳告诉我们,没有什么过不去的坎儿,方法就是抓紧时间干活。

高德纳就读的大学是凯斯理工学院,在这里他接触了IBM650计算机,这导致高德纳的音乐家梦想一去不复返,科学天赋终于重新占领了他的心扉。 1956年,在他第一次使用IBM650之后,他就躇踌满志地相信,说明书上介绍的程序,一定比不上他自己编写的。于是高德纳开始学习编程,他的第一个程 序是因数分解,不久之后,高德纳就对编程有了许多体会。当时高德纳还兼职管理学校的篮球队,于是他编写了一个程序,能够自动评估每名球员的价值,令球队的教练非常欣赏。这件事还吸引了CBS电视台的报道,后来高德纳、球队教练和IBM650的一张合影,还被印到了IBM650的宣传册上。1960年,高德 纳以公认出色的成就,打破了学校的惯例,同时获得了学士和硕士两个学位,大家来做个减法吧,算算高德纳此时年岁几何。

随后,高德纳从五大湖区,来到了美国西南岸,进入伯克利攻读数学博士学位。在此期间,他的编程生涯也正式开始了,他对外提供软件服务,为各种不同机 器设计各种稀奇古怪的编译器,曾经一个程序卖到5000美元。最值得一提的,就是他对ALGOL60编译器提出的测试方法。不知道大家是否还记得 ALGOL,这盏批量生产图灵奖的阿拉丁神灯。当时我们介绍过,ALGOL60的设计目标要求支持递归,而在设计编译器时,对递归的处理是很复杂的,所以 经常会因为编译器不成熟而出故障。高德纳编写了一段非常简单的测试程序,江湖人称“Man or boy test”,俗名“是男人就得-67”。高德纳说,只要用ALGOL60编译器来编译我的这段程序,如果运行结果等于-67,就说明这个编译器是纯爷们 儿,否则就只能算小男孩。

1963年,25岁的高德纳顺利拿到了博士学位,并留在伯克利任教。在毕业前一年,虽然还是研究生,但高德纳已经因为设计编译器而响誉计算机行业。 于是著名的Addison-Wesley出版社与他约稿,请他写一本关于编译器和程序设计方面的书。这本来是很平常的一件事,但您看看高德纳是何许人也, 不久之后,他简直把这件事做成了一件计算机科学史上的奇观。1962年约的稿,高德纳一直写到1966年还没交,在此期间他又是毕业,又是教书,终于人家 出版社急了。编辑找到高德纳,说这都四年了你写了多少啊,高德纳说,才写3000页手稿。编辑大囧,忙问都3000页了你怎么还不交,高德纳答曰,急啥, 我还没写到正题呢。编辑彻底雷住了,说那你出个多卷本吧……

《计算机程序设计艺术》,就这么诞生了。

把一件平常的事做到人间极致,这就是高德纳。他不是故弄玄虚,他的心里攒着一股劲儿,要写出一部与牛顿的《自然哲学的数学原理》相媲美的传世巨著。 他一开始计划了六卷,后来觉得这个数字不怎么好,又改成了七卷。1968年,《计算机程序设计艺术》(The Art Of Computer Programming,江湖人称TAOCP)的第一卷正式出版了。这一卷的标题叫《基本算法》,但难度却并不低。比尔盖茨曾经花了几个月的时间读完这一 卷,并且做了大量的练习,然后他说,如果你想成为一个优秀的程序员,那就去读这个《基本算法》吧,确保自己能够解决里面的每一个问题。然而,高德纳本人的 说法却比盖茨犀利多了:要是看不懂,就别当程序员。

就在这同一年,高德纳跳槽到斯坦福大学,并当上了教授,一边带博士,一边继续写书。一年后,TAOCP第二卷《半数值算法》正式出版,又过了三年, 也就是1973年,第三卷《排序与查找》也相继付梓。这三卷书立即被计算机界惊为神作,在那几年之内就卖出去了100多万套,至今仍然是编程书籍中的最高 经典。有一些对我们来说巧妙得不能再巧妙的算法,在这三卷书中顺手掂来,比比皆是,这个我们等会再说,现在有件要紧的事儿。按照高德纳的计划,这套书一共 是七卷,但是现在刚刚写完三卷,就已是震古烁今。震到什么程度呢,连图灵奖颁奖委员都坐不住了,他们做了一件前所未有的事。按照惯例,图灵奖的获奖者都是 成就等身,要经过时代的检验,然而高德纳却是例外,在他的七卷本刚刚写完三卷时,ACM便决定立即为其颁发图灵奖:

授予高德纳图灵奖,以表彰其在算法分析、程序设计语言的设计和程序设计领域的杰出贡献,特别是其著名的 《The Art of Computer Programming》系列丛书。

这是1974年的ACM图灵奖颁奖词,高德纳捧走了历史上第9个图灵碗。这对高德纳来说,无疑是个殊荣,因为这一年他只有36岁,直到现在,他仍然保持着 获奖年龄最小的纪录。

这是1974年的ACM图灵奖颁奖词,高德纳捧走了历史上第9个图灵碗。这对高德纳来说,无疑是个殊荣,因为这一年他只有36岁,直到现在,他仍然保持着 获奖年龄最小的纪录。

我们故事才讲到一半,可天才的高德纳却已经得到了图灵奖。各位读者可能要问,那下面还讲啥,他无非就是接着写书,接着带博士,就别废话啦。您要是这 么想,那就大错特错了,他要是那么做,他就不是高德纳。提前剧透一下,这个看上去顺理成章的计划,很快就被打破了,计划中的七卷本,直到今天都没有完成。 欲知发生了什么,且听下回分解。

上一篇我们讲到,高德纳计划要写一套七卷本的《计算机程序设计艺术》,没想到刚刚写完第三卷,就被 ACM授予了图灵奖。这在图灵奖历史上是从没有过的事。 我们还记得巴黎会议上的诺尔吧,他的图灵碗比他的获奖成果迟来了整整45年,他等这个碗时间,比高德纳获奖时的岁数还要长。但是,高德纳在获此殊荣之后, 再一次令世界大跌眼镜:他宣布从此歇笔了,因为排版工具太差,破坏了这套书的美。

高德纳的这一动作让外界十分震惊,可以想见,他遭到了排山倒海的怀疑。有人说,高德纳肯定是江郎才尽,拿了图灵碗,见好就收;有人说,图灵奖对前三卷的评 价过高了,高德纳无力面对这么大的压力,只好找个理由撤退;还有人说,获奖之后停止写作,充分体现了他写书的目的就是为了功利。他们纷纷质疑,这个图灵碗 是彻底发错了人。

然而,如果我们真正翻开TAOCP读一读,就不难理解这是为什么。我觉得,对于算法的研究,可以分成三层境界。第一层是分析算法的复杂度,这是计算机专业 的大学生普遍掌握的技能,达到这个境界,可以说是入了算法的门;第二层境界是改进算法的复杂度,在分析之后继续思考,想办法去降低它,这就可以算是懂算法 了;第三层境界,就是寻找算法的最优复杂度,不但要改进它,而且要改到什么程度呢?就是要证明出来,我改完的算法就是最优的,你无论如何都不可能再改进 了,再改进就违反宇宙规律。

高德纳,就是典型的第三种人。诸位不妨看看,TAOCP里面给出了多少最优算法,高德纳是铁了心,要当算法世界中的上帝。高德纳就是这么一个极致地追求极 致的人,他强迫自己把每件事都做得不可逾越。那么他怎么能够容忍,这套被他视为毕生事业的书,被糟糕的排版技术束缚?于是,无论别人怎样质疑,他最终还是 把写作晾到了一边,开始全力以赴地研究字体和排版。高德纳让我们领略了什么才是真正的个性,个性绝不是打18个耳洞,或在牛仔裤上抠36个窟窿。个性,就 是在所有岔路口都追随自己的心,让所有影响你追求梦想的障碍统统跪倒。

高德纳这一歇笔,就是十年。在这不务正业的十年当中,对极致的追求像只看不见的手,推动他创造了三个响亮的成果,其中影响最大的,就是排版系统TEX。如 果大家用MS Office Word写过论文,就会体会到那份求死不得的心:不断地调整字号、行距、缩进、分栏,如果这还不算什么,你再写几个数学式子看看?但是在TEX中,这些麻 烦几乎完全不存在,你唯一需要做的,就是把你想写的内容告诉它。如果说时间就是生命,那就可以认为,TEX每天都在拯求科学家们的生命,说它推动了科学的 发展也不为过。TEX是一场出版界的革命,直到现在仍是全球学术排版的不二规范,它所排出的文字之美,特别是数学式子的美,让人们由衷感叹:啊,一毫米都 不能再挪动了。

除了功能上的美之外,TEX作为一个软件产品,也令人叹为观止。它的版本号不是自然数列,也不是年份,而是从3开始,不断地逼近圆周率 (3.14,3.141…目前最新版本是3.1415926)。高德纳再一次用行动宣告,我这个东西,不可能再有什么大的改进了,最多只能小修小补,使其 趋近完美。他还专门设立了奖金:谁发现TEX的一个错误,就付他2.56美元,第二个错误5.12美元,第三个10.24美元…以此类推。我们都知道,传 说某个国王就因为这种指数游戏失去了江山,高德纳作为算法大师,更清楚指数增长的可怕性。然而他却敢立此重赏,结果直到今天,他也没有为此付出多少钱,可 见TEX经过了怎样的千锤百炼。这个耗费十年打造的玩具,让当初质疑图灵奖发错了的人们全部闭嘴了,他们甚至改口说:哦,为了这个TEX,不妨再给高德纳 一个图灵碗吧。

第二个成果,就是METAFONT,这是一套用来设计字体的系统。对于它的价值,一句话就能概括:计算机界最懂字体的两个人,一个是苹果的乔布斯,另一个 就是高德纳。

第三个成果,就是文学化编程(Literate Programming),它把程序设计的艺术性展示得淋漓尽致。高德纳说,一段好的程序,不仅仅是要清晰易读,而且要能够读出美感,读出意境。天呐,意 境,一排一排的计算机代码,要像诗歌一样充满意境。高教授,你疯了?

高德纳说,你才疯了呢,看我给你们露一手。于是,他在C语言的基础上,开发了一套CWEB系统,除了用它写出了TEX程序之外,竟然还用它写了一本叫作 《Stanford Graphbase》的书。高德纳微微一笑,我都能用编程语言写书,何况有意境的程序了,我的口号是:程序员也能得普利策奖(这是全球新闻写作领域的最高 奖项)。

文学化编程还为高德纳报了一个小仇。我们第6章中讲过的迪科斯彻,当年提出了一个“结构化编程”,提倡不要在编程时使用“goto”语句,高德纳偏要唱反 调,结果被迪科斯彻称为“没结构”。这下可好,高德纳狡黠一笑,嘿嘿,如果你不跟我混,你就是“没文化”咯(literate也有“文化”之意)。

歇笔十年的高德纳,手捧这三项成果重出江湖,打消了一切质疑。这时他才对十年前的歇笔事件做了一个轻描淡写的解释:一个人要想把事情做得漂亮,就必须要跟 上帝保持和谐,现在,上帝终于让我去写四卷了。

他的笔,又拿了起来。在写作第四卷的过程中,为了帮助读者打好数学基础,以便面对TAOCP中的数学高峰,他又专门撰写了一本《Concrete Mathematics》。这本书有中文版 ,翻译为《具体数学》,我一直觉得稍有不妥。Concrete到底是什么意思呢,高德纳说,意思就是我不教那些软绵绵的数学,我要教的是扔到地上能砸个响 儿的数学。据说,他在课堂上说完这番话,有好几个同学扭头走出了教室──他们是土木工程系的学生,还以为高德纳是讲混凝土的呢(Concrete在土木领 域意为“混凝土”)。说到高德纳的教学,还有个趣闻,他批改作业的时候只抽查第314页,就能判断出这份作业的质量。为此,我们这本书的第314页用来向 高德纳致敬。

1992年,高德纳为了专心写作,宣布提前退休,并停用电子邮箱。高德纳一共带了28位博士生,他觉得28这个数字很好,于是便宣布不再收学生了。尽管如 此,他仍然为想要师从于他的人们留下了一个盼头:他开了一门叫做Computer Musing的公开课,每次会提出一个问题,如果谁能快速解出来,高德纳就会为他的博士论文签名。不知道哪位后起之秀能够获得如此殊荣呢,我们拭目以待 吧。

2008年,在TAOCP的前三卷面市30年之后,第四卷终于千呼万唤始出来,而高德纳,却已是白发苍苍的古稀老人了。一句话,一辈子,一生情,一杯酒, 他对计算机科学的热爱,使他为这套丛书耗费了一生的心血。在这一章的最后,我想用一个词,来形容这位天才的计算机科学大师,但是思前想后,我只能想到唯一 的一个词:God。

我想,尽管高德纳是一位虔诚的基督徒(他还专门写过关于圣经研究的书),但他一定会欣然接受这样的形容。正如当年Linux的作者Linus说:上帝在梦 中告诉我,我做出了最优秀的操作系统。

高德纳回答说:我可没这么说过。

标签:
目前还没有任何评论.