在世最偉大的計算機科學家高德納度過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 ，你就獲勝了。證明你必然會獲勝。該問題亦叫做保加利亞紙牌。
TAG:煎蛋 |