您的位置:首頁>設計>正文

在世最偉大的電腦科學家高德納度過80歲壽辰

當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 , 你就獲勝了。 證明你必然會獲勝。 該問題亦叫做保加利亞紙牌。

該問題亦叫做保加利亞紙牌。

Next Article
喜欢就按个赞吧!!!
点击关闭提示