在世最伟大的计算机科学家高德纳度过80岁寿辰

picture：wiki

当24岁的高德纳·克努特(Donald Knuth)开始编写《计算机程序设计艺术》The Art of Computer Programming时，他肯定没有想到，在56年后他还在为此工作。

本月，计算机科学界在瑞典为高德纳庆生，这位计算机和信息科学界的泰山北斗如今已然是80高龄。

但他依然在继续编纂《计算机程序设计艺术》后续的卷本。高德纳指出，最近的几卷将以初级平装书形式出版的，其中希望读者注意到最重要的部分，在第4卷以及第6卷关于布尔函数的可满足性。

这是一个计算科学里的理论问题。用通俗的语言说。计算机里的位码变量都是布尔型变量，只取值0或1。两个布尔变量之间的运算只有“与”“或”“非”，表示为“∧”“∨”“¬”。

众所周知， 1∧0=0，1∨0=1，¬1=0。现在如果有一个包含许多变量的表达式，例如：x∨y∧¬z，问：这个表达式能等于1吗？

如果存在x,y,z的一组赋值，令表达式等于1，就说这个表达式被满足了。这就是布尔可满足性(简称SAT)问题。但是，你要允许变量个数可以任意，表达式可以任意长。这个问题是一个计算复杂性很高的问题，已经证明它基本上是一个多项式复杂性算法不可解决的问题。

二十一世纪初期出现了解决这些问题的革命性方法，并在工业界通过硬件写入的方式被大规模地应用。这些所谓的“SAT解算器”现在可以作为常规方式来为涉及数百万变量的实际问题的提供解决方案，而这直到不久前还被认为是令人绝望的工作。

在高德纳的寿诞上，还首演了他的视频音乐作品——《幻想曲启示录》，这是一部基于圣经启示录题材的管风琴演奏和视频多媒体作品。据说，他构思了50年之久。

Donald一般翻译成唐纳德，但是用在称呼Knuth的时候，会被翻译成高德纳。因为储枫教授(香港城市大学计算机科学系主任，图灵奖得主姚期智的夫人)最早的翻译，高德纳本人遂将此用作正式的中文名。

其他的学术贡献，诸如开源的TeX系统也不是无足轻重的。事实上，法国数学家、菲尔兹奖得主维拉尼曾经半开玩笑的解释，为什么高德纳不再参加每年的计算机科学学会：“他走进会场的时候，其他人都会忍不住产生跪下的冲动。是的，他就是计算机、算法以及信息科学界的教皇。”

在参加了自己的生日庆祝会，高德纳在个人网站上表达了对同行的谢意，并且提醒《计算机程序设计艺术》的读者记得完成后面的习题。如果发现错误，可以给他留言。

习题试举一例：取出 45 张牌，然后把它们随意分成若干堆。接下来，从每一堆里各取一张牌，叠在一起形成一堆新的牌。不断这样做下去，如果某个时候桌面上正好有 9 堆牌，并且各堆牌数分别为 1, 2, 3, 4, …, 9 ，你就获胜了。证明你必然会获胜。该问题亦叫做保加利亚纸牌。