@ 2018.01.26 , 09:00
34

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

在世最伟大的计算机科学家高德纳度过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 ,你就获胜了。证明你必然会获胜。该问题亦叫做保加利亚纸牌。


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

4.9
赞一个 (17)

TOTAL COMMENTS: 34+1

  1. 3686973

    求老爷子安心写书!

  2. 刘某人
    @4 weeks ago
    3686978

    其实只是28岁了,因为写了3年代码看上去像80

  3. 须臾飘渺
    @4 weeks ago
    3686980

    “∧” ,“∨”, “¬”,这些表情还蛮可爱

  4. 汪非鸿
    @4 weeks ago
    3686985

    看了开头,正想吐槽名字的翻译,不过,还好我看完了全文。

  5. 无浪漫主义者
    @4 weeks ago
    3686988

    Computer science is not a real science.

  6. 絮语
    @4 weeks ago
    3687010

    好奇最后的题怎么做

  7. 3687018

    时间过得好快,第一次知道他的名字时我才20岁,现在40岁了。

  8. 里克迪
    @4 weeks ago
    3687032

    看成了全世界最长寿的程序员度过了80岁😅

  9. butters9637
    @4 weeks ago
    3687053

    现在普及和流行较广的都是便于人类掌握和理解的计算机科学。 高爷爷教的是如何像计算机一样思考, 感觉和数学分析有些类似。 但也和数学分析一样终究无法被大众所掌握。

  10. byzantinesfall
    @4 weeks ago
    3687055

    讲真,业界里能读完这几卷书的那都算大拿了。实在想象不出写出这书的是多大的拿。

  11. 3687067

    西部世界里的那个?

  12. 3687070

    http://www.codeweblog.com/%E4%BF%9D%E5%8A%A0%E5%88%A9%E4%BA%9A%E5%8D%95%E4%BA%BA%E7%BA%B8%E7%89%8C%E6%B8%B8%E6%88%8F/

  13. byzantinesfall
    @4 weeks ago
    3687082

    @Alex: 安啦。他又不可能像马丁那样书写到一半去拍肥皂剧。

  14. byzantinesfall
    @4 weeks ago
    3687096

    @无浪漫主义者: 不明白为啥这么多xx。科学研究的一般流程是发现现象,提出假设,实验验证,建立理论。从这个角度讲cs确实更接近于技术而不是科学。这只是分类,没有贬低谁拔高谁的意思。

  15. lululu
    @4 weeks ago
    3687111

    高德纳的英文名直译为唐纳德·尔文·克努斯(Knuth发音为/knuːθ/[1]),“高德纳”这个中文名字是1977年他访问中国之前所取的,命名者是储枫(姚期智的夫人,计算机科学家)
    ——Wikipedia

  16. 3687122

    在世最伟大的计算机科学家

    这个title有点夸张吧……你至少加个“之一”

    反正

  17. 脑子坏掉了
    @4 weeks ago
    3687127

    @byzantinesfall:
    形式科学吧

    就像数学不是自然科学一样

  18. 哈哈
    @4 weeks ago
    3687131

    @无浪漫主义者: but a science of engineering.

  19. 3687139

    这头发有点多啊

  20. 3687151

    @byzantinesfall: 虽然说老爷子不拍肥皂剧,但我们还是等书等得很心焦啊,而且他还动不动就跑去斯坦福开课玩儿。

  21. 3687155

    @无浪漫主义者:you misunderstand computer science and software engineering. SE is part of engineering but CS literally is computing science, which more related to computing and math than programming and language

  22. 3687189

    这篇的评论充分说明煎蛋这几年用户群变化是多么大。

  23. 月巴
    @4 weeks ago
    3687202

    希望老人家健康长寿,安心写书。也希望自己有一天能把书看完 _(:з」∠)_

  24. 只喝摩卡的狗
    @4 weeks ago
    3687290

    我的天!这大爷还活着呢?!

  25. 无浪漫主义者
    @4 weeks ago
    3687316

    @Ass
    这就是了,数学家一般不会被自己或他人认为是科学家
    一样是纠结在数学上的CS却自己也搞不清楚

  26. 3687369

    @byzantinesfall: 说数学不是科学一定会有一堆人跳起来。就像大多数人一样,其实根本说不明白什么是科学,无非是想显得高大上,拼命要往上贴

  27. 鸡蛋
    @4 weeks ago
    3687416

    @无浪漫主义者: 那你是否知道不管通过什么形式,机械的也好电子也好量子也好,通过一个简单的与非门计算出一个比特并保存一年最少需要多少能量吗?有没有一个极限?
    这问题有意义吧,计算机科学解答过这个。
    不纠结,就说这么多。

  28. 3687515

    如果高老爷子的书是智商鉴定器,那绝大多数人只能是白痴。

  29. Eriice
    @4 weeks ago
    3687566

    幻想曲启示录 https://www.cs.stanford.edu/~knuth/fant.html

  30. moonsun
    @4 weeks ago
    3687578

    所有程序猿赞美我们自在永在的主神!衷心希望主神大爷长命百岁!

  31. 二米
    @4 weeks ago
    3687654

    老爷子为了写书半截发明了tex然而到现在书都没写完

  32. 魔能野猪
    @4 weeks ago
    3687692

    正在编写“圣经”

  33. 3687719

    要么叫 唐纳德·克努特 (Donald Knuth)
    要么叫 高德纳 (Knuth Donald)
    不要混淆

  34. Pegasus
    @4 weeks ago
    3688032

    科普一下保加利亚纸牌的证明(之一)..

    为方便表述,先换个表达..
    按如下方法将牌排成表格状:
    若总共有a堆牌,则分别放在最左边的a列中;若某堆牌有b张,则放在对应列的最下边的b格.
    于是每次操作即从每列中取出一张牌组成新的一列.
    由于列的排列顺序对结论没有影响,不妨保持表格中的堆从左到右从多到少排列.
    于是每次操作其实可以分成两步:
    I.取出每列的最下一张,构成一个新的列放在第一列的左边;
    II.若有必要,交换某些列,使得所有列还是从左到右从多到少.

    将↘方向经过若干牌的线称为对角线.
    显然对操作I,每条对角线上的牌数是不变的;而对操作II,列的交换其实等价于将某些牌左移.
    于是,牌不会往右边的对角线移动,故最终所有对角线的牌数都不会改变.
    于是操作II不会再出现,即一直进行操作I,列的牌数总是有序的.

    对任意一条对角线,每次进行操作I后,其上的牌和空位相当于循环移了一位.
    若存在相邻两条对角线,左边那条有空位而右边那条有牌,由于每次操作I使两条对角线都移了一位,而两条对角线的长度互素(相差1),故若干次操作后必会使左边对角线的空位恰好在右边对角线牌的左边,此时有序性已无法满足,矛盾.

    综上,最终的牌必定会从左到右依次填满每条对角线.
    特别地,若总牌数是三角形数,则最终会恰好填满若干条对角线,状态完全不变;
    否则填满若干条对角线后剩下的牌会占据下一条对角线的部分位置,陷入循环,且周期为此对角线的长度的约数.

    在这里说数学用词没在意严谨..当然肯定有人说没图看不懂的..参见m67..
    http://www.matrix67.com/blog/archives/5865

发表评论


24H最赞