高德纳谈计算机程序设计艺术（下）

作者：Justin Richards 

译者：Elliot，何逸勤

高德纳（D. E. Knuth）教授是备受尊崇的系列巨著《计算机程序设计艺术》（The Art of Computer Programming）和数十篇受到高度赞誉的计算机科学论文的作者。2011年6月，结束了在英国的书籍研讨和系列演讲的高德纳教授，跟BCS编辑Justin Richards畅谈了自己的人生和工作。

您曾经说过，您的工作从根本上是“关于如何辨别能够（在计算机科学领域）产生持续影响而非很快改变的东西”。这里的具体含义是什么呢？

我每天大约都会收到一份期刊，没有ITNOW啦（笑），但会有The Computer Journal。我的邮筒每周大约收到8份这样的期刊，那里面就是数量庞大的资料，其中就有些好内容。那么，我怎样决定哪些要写进去《计算机程序设计艺术》的呢？

我会尽力避开那些很快就会过时的内容，专注在将会有大范围应用的内容上。我要找出那些不是很难上手、能够成为多数人的常用工具的那些实际内容。什么是下一代的每个程序员都需要牢记的？我不会假装自己在每一件事情上都是正确的，但会努力辨别出那些能够吸引我的注意力的、令人无法忽视的、我们的下一代必须记住的知识。

那么我想您的作品中所选用的材料都是构建计算机科学的基石，而不是那些具时效性的枝节？

不错，但也有一些枝节的东西是可以在两三个段落中描述清楚并且容易理解的。那些需要花十页纸来才说得清的问题是很难被我选入书里的。我更倾向于选取那些通常只需要三页就可以阐释清楚、本质上有很高的实用性、并能很好地和书里面的其他内容熔炼在一起的算法。

就以我们从小学习的加法为例，假如你认真去想一想，你就会发现其应用之广泛是如此的不可思议。我们会在各种各样的场合中使用加法，而且日复一日从不间断。然而我们掌握的是加法的本质概念。我的书里面有许许多多类似的小概念，而对于这种我所需要的题材，我相信还有很多有待人们去研究发现。

即使是加法和算术，现在还有所谓的“无进位加法”或者叫“尼姆数加法”——那是大概一百年前在英国被发明的。一开始那只是计算机所擅长的一个游戏，而且它能和普通的加法结合使用；后来我们发现这种加法其实非常实用，因此我的新书中会解释为什么我们也许应该让小孩子们从五年级就开始学习它。当然这并不是说我们真正需要学习的都已经在幼儿园就学会了。事实远非如此简单，学习需要经过漫长的累积，才能像滴水穿石那样，在某天达到飞跃。

1999年，MIT邀请您就“信仰与科学的关系”这一普遍性主题做了六场公开演讲。十多年过去了，您对科学与精神性的关系的看法是否有什么改变呢？

我很高兴看到人们认为生命中存在某些超出人类理解能力的东西。做那些演讲的时候，我只是从壁橱中跳出来说：“计算机科学很美妙，但那不是一切。请不要期待我能够真正回答你的疑问。我要解释的是：我为什么会觉得仍旧存在神秘的事物是件好事。”

伴随着科学上不断推进的成就而来的是一种倾向，我们倾向认为自己可以认知所有的事物。然而，我感觉到，当我们愈加深入地思考，就越会认为自己不过刚刚开始。我们正以令人难以置信的速度在改变着许多事物，但我仍认为未来100年还将有更多需要探索的东西。

因此，人类还有很大的学习空间，而我们所已经学到的浩瀚知识，仍值得我们自豪。

收到MIT的邀请时，我想：如果我的一生中是需要至少一次机会去深究这个问题的，那恰恰就是此时此地了。我不会假装成这方面的专家，仅仅是觉得大家并没有真正花时间去思考这个问题。能在这么多人身上产生反响，我深感庆幸。

那个系列讲座有很好的上座率吗？

的确很好，几乎连站的位置都没有了！而且那还是一个相当大的讲堂。那个系列一共是六个讲座，第一个之后就放在了Dr. Dobbs的远程网络上面发布，而在接下来的五六年间被下载的次数也是令人吃惊之多。

所以说这个系列讲座必定是满足了某种需求。我其实并没有提供答案，而只是提出了一些问题。我认为那些都是我们生活中不可或缺的部分，为何不在公众场合中共同探讨呢？事实上我为前来参与的人数感到相当惊喜。

几年前我在Google给了一个关于相同主题的演讲，那是又一次座无虚席。而那次演讲更接近于我在图灵系列讲座中的“提问-回答”。与其什么都事先规划好，我更喜欢这种即席回应人们提问的形式。

我正想请教您怎样应对类似的挑战呢。对很多人来说，不知道自己即将需要回答哪些问题，是非常可怕的……

哈哈，没那么艰巨啊。即便我说错了什么，那也没啥大不了。压力也不是那么大啦，尤其是要跟首相回答记者问题相比较的话。我觉得奥巴马总统会觉得这种事情有压力，但小布什总统大概不会这样想。

我想小布什也会有他所擅长的……

我想大概是吧，不过我真不愿意卷入政治讨论，我还没有研究出一套关于政治的算法呢！

1975年，您出版过一本《婚姻的稳定性》（Marriages Stables）的手册，那是对算法分析的入门介绍？

那只是个小噱头，但那本书其实又是我在蒙特利尔做的一系列六个演讲的内容。那系列演讲的主题就不是“信仰和科学”了，而是集中在算法分析。我是以“稳定的婚姻”这一数学问题来展开讨论的。这个问题也可以看作男孩和女孩之间的游戏：他们各自去展现本身的状态，每个男孩都会对女孩做排名，反之亦然。我们会问自己：“我们要怎样运用一系列准则来将他们配对，使他们之间的关系是有稳定性的？”当有些人更多地欣赏对方而非自己的现有配偶时，关系就是不稳定的。我们总能找到方法以稳定的方式来配对这些男孩和女孩。

我们可以从数学上证明这是可行的。不过，这样的方法不止一种，因此我就可以引入算法分析来解释为什么某个方法比其他的更好。回到前面的观点，我最希望听众记住的是如何去领会这些算法的工作方式。因此，通过具体数学解决问题的方法，我们可以解决类似男孩女孩配对这样的趣味性问题。

如此说来，这个类比是帮助人们在脑海里对您的理论形象化？

是的。因此我可以得出一个普通的男孩将要进行一定次数的求爱，而不需要多久我们就能统计出每个结果的概率。你可以通过设计许多问题来让女孩们或男孩们得到最好的选择。在试图解决这个问题的过程中我们就能体会数学的各种美好。

我在那里通过六个讲座来讨论了这样一个问题，并与听众们进行了互动。尽管我当时使用的是英语而且我不通法语，但他们仍决定把整个讲座都翻译成法语，并最终以法语出版了那次讲座的书。而这本书二十年之后才又以英语再版。因而我也有了用我并不懂的语言出书的经历了。

看来您确实很喜欢挑战，六场演讲的系列讲座，一次还不过瘾，非要两次……

那是啊，每20年，我都会面临一次这样的挑战！那种感觉跟在家里埋头创作《计算机程序设计艺术》是很不一样的。我一直为这系列书籍搜集资料，已经几乎有50年啦。

今年您被邀请来做图灵系列讲座，请问对此您有什么特别感想吗？

我现在正在人生的一个转折点，庆祝我的两个经时数年的大项目进入收尾阶段。因此也是给这个系列讲座的最佳时间。事实上两年前我就曾经告诉他们，从那时算起两年之后会是一个合适的时间——到那时候我会放松下来，然后重新调整一下去迎接新的挑战。

我完成了我引以为豪的《计算机程序设计艺术》卷4A的写作，并在不到两周前刚刚收到第一本样书。此外我也完成了我累积的论文专著的第八卷。我把多年来我所写的所有的学术论文都出版成书。例如有一卷是关于印刷术的，因为我曾经研究过能使书籍变得更美观的软件。有一卷则收集了我所有关于算法分析的论文。还有一卷收集的是我针对非专业计算机读者写的较为通俗的论文。

最后这第八卷是关于趣味游戏的，我把它们当作甜品一样留到最后。因为这些论文纯粹是因为我喜欢而写的，写作过程也是最快乐的。我就是非常热爱这本关于趣味游戏的书，虽然我也不是很确定原因是什么。

我在同一天完成了这本书和《计算机程序设计艺术》卷4A的写作，并把它们分别寄给了各自的出版商。而也在同一个星期内收到了这两本书的样书，这确实让我心花怒放。我非常庆幸在完成它们的过程中我没有生病，也没有发生世界大战。我也很高兴它们终于圆满完成了，我再也不用为它们操心了。

我们BCS一直致力于提高IT行业的专业性。请问您在这方面的意见，是IT行业仅仅需要自我监管，还是需要进一步的引导呢？

我是编写程序的人，并没有合适的资格来评论这一点。英国的同业协会和共济会有着悠久的传统，在我所知道的范围内，它们能将行业引导到优良的质量标准。不过，对某些行业而言，它们做得有点过度了。行会的人能够判定成员是否值得雇用、是否能提供有价值的服务，这不太好。实际上，当今的通信手段已经大幅改善，很难再用所谓的“浮报雇佣”的做法来掩盖不够好的做法。

您觉得IT行业是否背负了充斥着极客和书呆子的坏名声？

这还真是挺有趣的，因为其实有个英国作家曾经有一个大致名为“每周极客”的博客，而我还因为曾被他评上一次而感到光荣。我想不起那个作家的名字了，这件事大概是发生在两年前的。现在还有人谈论“极客风格”——极客这个词变得更为普罗大众所接受，人们也不再羞于承认自己是个极客了。书呆子就有点不同。

我的感觉是现在人们会自诩为极客，大家也理解这个名称在当今时代已经有着不同的内涵，这跟几年前相比肯定是不同的。

即使是文字工作者，有时候也很难解释为什么有些词语会受到追捧，而有些则会日渐被遗弃，但很明显极客这个名称正处在它的上升期。我也不一定是正确的，但是在我那本关于趣味游戏的书里面有一章名为“极客艺术品”，我觉得这个题目很恰当，因为它所涵盖的恰恰就是那些我希望在自己家里收藏的艺术品。

对您而言，在过去的五六年间，计算机科学的竞技场中哪些是最重要的成就呢？

我认为那是千千万万的人们可以协同工作这一事实。如果在每年年底要问哪一项才是当年最大突破的成果，那可能真的想不到什么。不过，五年之后，整个领域却已天翻地覆。究其原因，正在于每一个分支都在不断进步。

偶尔，会出现一些其后被视作重大进步的成果，例如Web的诞生，但它们实际发生的时候，却是没有人能准确认识到其重要性的。这种情况跟中国当年建造长城很类似，每个工匠都去添砖加瓦，多如恒河沙数的人们最终成就了这一非凡的团队作品。大家都在自我挑战并相互学习，这是我理解的所谓成就。

您觉得计算机科学在现在或者不久的将来将面对的最大的问题或是挑战会是什么呢？

最大的挑战就是面对将来那么多有待攻克的未知，我们每天晚上如何安枕！作为一个美国人我非常崇拜（也有些许嫉妒）我所了解到的（我的孙子在这里出生）英国的医疗保障系统。但是我觉得仍有许多可以地方可以通过计算机的协助来改善，例如更好地保存医疗档案，更好地描述和视像化综合的症状，更好地组合运用统计和视像化的方法，等等，这些都会大大的帮助医生们迅速而清晰地理解情况。

更不用说计算机能帮助生物学家设计更好的药物。你所见到的每一个可以改善的地方都需要一个好的程序员的协助。我们从来都不会缺乏挑战性的问题，而且未来也不见得会。

我在前面说过大概50个人里面会有一个像我这样的极客，但是我担心在未来的数年极客会越发的供不应求。我也可能是错的——也可能下一代会有十分之一的极客，但是我对此表示怀疑。为了让计算机去完成那些任务，我们非常需要这些身负奇才的人来设计和运行程序。

您觉得，人工智能上的那个老掉牙的说法是否能最终解决？

我认为我们距离这一怪圈还不是很近，但人类和机器最终仍会一起面临这个问题。

必须指出，我的同事、斯坦福大学校长John Hennessy曾经说过，五年之内将出现计算机的大崩溃，就像金融海啸那样。原因是人们已经变得如此依赖计算机，简直是没有它们就活不了了。人类铁定有一天会忘记了如何做事，而原因正是对机器的过度依赖。我们不记得没有这些机器的时候是怎样做事的，这将导致大崩溃。

您曾经说过“今天所有关于计算机的一切都让我惊喜，没有一样东西我是能在三十年前就预测到的”。如果你是一个科幻小说作者，你会对未来五十年做怎么样的预测呢？

我真高兴你找到了我说的那句话。无论如何，事实就是如此！

悲观地看，我觉得我们无法解决能源困境，除非有一天出现了能很好处理废材的增殖反应堆。在十九世纪英国有人提出过一个Jevons悖论。我想他的名字应该是Stanley Jevons。

有人发现了如何让铁路系统省十倍的煤，结果是铁路系统因此消耗了一百倍更多的煤。原因是这个改进让更多的人使用铁路来运输货物。换句话说当你提高了某样事物的效率，必然导致它吸引来更多的用户。

你不会说我们需要X那么多石油来完成我们要做的事情，因为事实上我们如果有更多的石油我们就会去做更多的事情。事实上就是我们的胃口是永远无法满足的。因此我觉得我们的能源困境也会持续下去。

乐观的情形就是因此每个人都将爱上了算法分析和设计美妙的程序——那不就是一个很好的将来吗？！

高德纳作品中文版

作者：高德纳

译者：李伯民 范明 蒋爱军

《卷1：基本算法（第3版）》讲解基本算法，其中包含了其他各卷都需用到的基本内容。本卷从基本概念开始，然后讲述信息结构，并辅以大量的习题及答案。

作者：高德纳

译者：巫斌 范明

《卷2：半数值算法（第3版）》全面讲解了半数值算法，分“随机数”和“算术”两章。书中总结了主要算法范例及这些算法的基本理论，广泛剖析了计算机程序设计与数值分析间的相互联系。

作者：高德纳

译者：贾洪峰

《卷3：排序与查找（第2版）》扩展了卷1中信息结构的内容，主要讲排序和查找。书中对排序和查找算法进行了详细的介绍并对各种算法的效率做了大量的分析。          

《美国科学家》（American Scientist）杂志曾将《计算机程序设计艺术》与爱因斯坦的《相对论》、狄拉克的《量子力学》等书并列为20世纪最重要的12本科学类专著。

比尔·盖茨曾经花几个月研读《计算机程序设计艺术》，并这样对广大程序员说：如果你自以为是一个很好的程序员，请去读读高德纳的《计算机程序设计艺术》吧……要是你真把它读下来了，就毫无疑问可以给我递简历了。

根据著名Common Lisp专家Peter Seibel的访谈笔录成书的《编程人生》，记录了15 位软件先驱的编程生涯。Seibel特别有意思，在访谈每个大牛的时候基本都会问到一个问题：

你觉得《计算机程序设计艺术》这套书怎么样？我在访谈中问过一些人，他们中有些真的从头读到了尾，有些把它放在书架上，在需要时作为参考书查阅，还有些就只是摆在书架上，连碰都不去碰它。

以下大牛都认真研读过高德纳的《计算机程序设计艺术》：

• 参与创建Common Lisp和Scheme的Guy Steele

• Smalltalk之母Dan Ingalls

• 调试大师Bernie Cosell

• JavaScript宗师Douglas Crockford

• JavaScript之父Brendan Eich

• Java大神Joshua Bloch

• Haskell先驱Simon Peyton Jones

• 人工智能专家、谷歌研发总监Peter Norvig

关于TAOCP，他们说

➤ Brendan Eich

Knuth 写的《计算机程序设计艺术》，卷1到卷3，我很喜欢，特别是半数值算法那部分，还有双重散列之类的，关于黄金比例的证明则被留做练习题，很有意思。

➤ Joshua Bloch

Knuth的《计算机程序设计艺术》，事实上，我从来没有读完这一套书，没有从头到尾看过。但当我研究某个具体算法的时候，我就去看他会怎么说。往往可以得到我想要的东西，这套书太全面了。

➤ Douglas Crockford

在上大学时，有那么几个月我连房租都没交，就是为了买他的书。我读过这些书，从中得到了不少乐趣，比如在第一卷的索引有个关于拖车的笑话就很好玩。我到现在为止还没能把书上的内容全部搞懂。Knuth对某些地方的研究要比我深入得多，但我还是喜欢这些书并把它们当做参考资料。

➤ Simon Peyton Jones

Don Knuth的《计算机程序设计艺术》系列不是能够一口气读下去的，不是那种书。在某个阶段我多次推荐过这套书。

➤ Peter Norvig

有段时间我拿它当我的显示器底座，因为它是我最大部头的成套书之一，而且高度恰好合适。我感觉这样很舒服，因为它总在那儿陪着我，而且因为它就在我面前，所以我找参考书的时候就更容易去顺手翻翻它。

Seibel：但你每次想查阅它，还得先把显示器抬起来吗？

Norvig：不用，我那套书是盒装的，你只要使劲抽书就行，也可以只抽其中一本。

 

☟ 【阅读原文】京东购买TAOCP