2013年9月23日 星期一

高德納的生平及其貢獻

貢獻:高德納最為人知的事蹟是,他是《電腦程式設計藝術》(The Art of Computer Programming)的作者。此書是計算機科學界最受高度敬重的參考書籍之一。他創造了演算法分析的領域,在數個理論計算機科學的分支做出基石一般的貢獻,此外還是排版軟體TeX和字型設計系統Metafont的發明人。


1966年,當高德納的著作已經長達3000多頁時,他與出版商商定,編纂一部系統地介紹電腦程式設計的巨著《電腦程式設計藝術》。對電腦領域產生了深遠的影響。
《美國科學家》(American Scientist)雜誌曾將該書與愛因斯坦的《相對論》、狄拉克的《量子力學》、理查·費曼的《量子電動力學》等書並列為20世紀最重要的12本物理科學類專論書之一。
                                                                                                                                                                                                         

1968年高德納拒絕了美國國家安全域的工作邀請,受聘成為史丹福大學電腦系教授,和他的一個學生開發了 Knuth-Morris-Pratt演算法,該法則使計算機在文章中搜尋一串字元的過程更加連貫。除此之外高德納還在電腦領域作出了多項貢獻,例如LR parsing theory, Knuth-Moris-Patt pattern等。


生平:加州理工學院研究所二年級時,為私人公司寫編譯器,賺得5000元美金。1963年高德納獲得加州理工學院數學博士學位,之後留校任教,並在數學領域取得多項成就。與此同時高德納也開始研究電腦程式設計,1962年1月Addison-Wesley公司的顧問Richard Varga請他出版一本有關編譯器的書籍。


KMP演算法:是在一個「主文字字串」 S 內尋找一個「詞」 W 的出現,透過觀察發現,在不匹配發生的時候這個詞自身包含足夠的訊息來確定下一個匹配將在哪裡開始,以此避免對以前匹配過的字元重新檢查。


引述自Yahoo奇摩知識

心得:我覺得他很厲害,可以發明這麼好用的東西。