David S. Johnson 獲頒 Knuth Prize. 恭喜!!! 不過好像相對來說沒有受到什麼注目. 上次頒給 Volker Strassen 時似乎還比較多人談到這件事. 或許是因為太理所當然了吧 :) 畢竟他一直是 TCS 界的大老, 他不僅是幾個學術組織領導人和期刊的編輯, 更建立了 SODA 這個研討會. 或許多寫什麼才是怪事 XD
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.
他最有名的著作應該是 Computers and Intractability: A Guide to the Theory of NP-Completeness , 雖然現在來說已經過時了. (三十年前的作品你要怎樣) 但仍然是經典之作, 後來有很多書基本上都參考了他的編排方式, 像是 A compendium of NP optimization problems.
老實說, 我碩士班的時候還參考了不少這本書的內容. 即使在今天, 如果想要證一個問題是 NP-Hard, 這本書依然是最佳的參考書. 實際上, 這本書還是 CS 被引用最多次的書.
這本書影響到底有多深遠, 我想就不用我多說了, 這麼多年來, 只要提到這方面的研究, 都會想到 D. S. Johnson. 知名期刊 Journal of Algorithm (不過已經倒了) 從 1982 年起就邀請 D. S. Johnson 寫了好幾年的 NP-Completeness Columns. 到 2007 年, ACM Trans. Algorithms 還邀請他寫 The NP-Completeness Column.
他的另一個深遠的貢獻是, 發起了 experimental algorithm 這個領域, 從 The DIMACS Implementation Challenges 到推動 ACM Journal on Experimental Algorithmics. 雖然我不是很清楚證明了什麼定理或者發明了什麼雋永的演算法, 但是我想他的影響的確是深遠的.
Ref.: A Theoretician's Guide to the Experimental Analysis of Algorithms
沒有留言:
張貼留言