跳至內容

沃恩·普拉特

維基百科,自由的百科全書
沃恩·普拉特
Vaughan Pratt
出生Vaughan Ronald Pratt
(1944-04-12) 1944年4月12日80歲)
 澳洲墨爾本
母校雪梨大學
史丹福大學
知名於KMP演算法
普拉特證明英語Primality certificate
普拉特解析器英語Operator-precedence parser
網站boole.stanford.edu/pratt.html
科學生涯
研究領域計算機科學
機構史丹福大學
麻省理工學院
學術指導者高德納

沃恩·普拉特(英語:Vaughan Pratt,1944年4月12日)是一名澳大利亞計算機科學家史丹福大學名譽教授。自1969年以來,普拉特在搜尋演算法排序演算法質數測試等基礎領域做出多項貢獻。近期他的研究重點是並行系統楚空間英語Chu space的形式建模。

職業生涯

普拉特在澳大利亞長大,曾就讀於諾克斯文法學校英語Knox Grammar School。1970年,普拉特進入雪梨大學學習,並在那裏完成碩士論文,該論文與現在的自然語言處理有關。隨後他前往美國,在指導教授高德納的指導下,僅用20個月就完成史丹福大學的博士論文。他的論文重點分析希爾排序演算法和排序網絡英語Sorting network[1]

普拉特曾任麻省理工學院助理教授(1972年—1976年)和副教授(1976年—1982年)。1974年,普拉特與高德納和詹姆斯·H·莫里斯合作,完成他1970年在加利福尼亞大學柏克萊分校攻讀研究生時開始的工作,並使之正規化;合作成果是KMP演算法。1976年,他發展了動態邏輯英語Dynamic logic (modal logic)系統,這是一種結構化行為的模態邏輯

他從麻省理工學院到史丹福大學休假(1980年—1981年),並於1981年被任命為史丹福大學全職教授。

1980年至1982年,普拉特在史丹福大學指導太陽工作站英語SUN workstation計劃。他以各種方式為太陽電腦公司的成立和早期運營做出貢獻,在公司成立的第一年擔任顧問,隨後兩年離開史丹福大學,擔任研究主管,最後於1985年重新擔任太陽電腦公司顧問並返回史丹福大學。

他還設計了太陽電腦公司的徽標[2],徽標上有四個交錯的「sun」字樣;這是一個雙向圖

2000年,普拉特成為史丹福大學榮譽教授。

主要貢獻

許多著名的演算法都以普拉特的名字命名。普拉特證明英語Primality certificate是對一個數是否為質數的簡短證明,它以一種實用的方式證明質數是可以有效驗證的,將質數檢定問題歸入複雜度類NP,並首次有力地證明該問題並非共NP-完備英語co-NP-complete[3]。1970年代初,普拉特與史丹福大學教授高德納共同設計了KMP演算法,該演算法是詹姆斯·H·莫里斯獨立設計的,至今仍是已知最高效的通用字串搜尋演算法。[4]。他與曼紐爾·布盧姆羅伯特·弗洛伊德羅納德·李維斯特羅伯特·塔揚一起描述中位數的中位數英語Median of medians,這是第一個最壞情況下的最佳選擇演算法[5]

打造實用工具

普拉特開發了一些有用的工具。1976年,他撰寫一篇關於CGOL英語CGOL麻省理工學院人工智能實驗室工作論文,CGOL是他根據自上而下的運算子優先級解析範式設計並實現的MACLISP的替代語法。[6]。他的解析器有時被稱為「普拉特解析器英語Operator-precedence parser[7],並被用於後來的系統中,如MACSYMA英語Macsyma道格拉斯·克羅克福特也將其用作JSLint的底層解析器[8]。普拉特也實作了一個基於TECO英語TECO (text editor)的文字編輯器,名為「DOC」,後來更名為「ZED」[9]

1999年,普拉特建立了當時世界上最小的網頁伺服器——只有火柴盒大小[10][11]

其他貢獻

普拉特在1995年《位元組英語Byte (magazine)》雜誌的一篇文章中指出,奔騰浮點除錯誤造成的後果可能比英特爾IBM當時預測的還要嚴重[12][13]

如今的普拉特影響廣泛。除了史丹福大學的教授職位外,他還是至少七個專業組織的成員。他是美國計算機協會會士,也是三大數學期刊的編委。他也是TIQIT電腦公司頁面存檔備份,存於互聯網檔案館)的創始人、董事長兼執行長,該公司於2010年關閉。

參考資料

  1. ^ Vaughan Ronald Pratt: Shellsort and Sorting Networks. Garland Publishing, Inc., New York & London, 1979, ISBN 0-8240-4406-1
  2. ^ Designers: Vaughan Pratt. Logobook. [2021-08-07]. (原始內容存檔於2020-08-09) (英語). 
  3. ^ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214–220. 1975. Citations頁面存檔備份,存於互聯網檔案館), Full-text頁面存檔備份,存於互聯網檔案館) (requires paid login)
  4. ^ Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350. 1977. Citations頁面存檔備份,存於互聯網檔案館
  5. ^ Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. Time bounds for selection (PDF). Journal of Computer and System Sciences. August 1973, 7 (4): 448–461 [2024-02-10]. doi:10.1016/S0022-0000(73)80033-9可免費查閱. (原始內容存檔 (PDF)於2019-03-31). 
  6. ^ Pratt, V.R., Top Down Operator Precedence. Proceedings of the ACM Symposium on Principles of Programming Languages. 1973. pp41-51.
  7. ^ George J. Carrette A simple Pratt-Parser頁面存檔備份,存於互聯網檔案館) for SIOD. 1990.
  8. ^ https://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js jslint source code line 2224
  9. ^ Eric Fischer. Emacs and Other Editors頁面存檔備份,存於互聯網檔案館). alt.folklore.computers. November 15, 2000.
  10. ^ BBC News.Surfing on a matchbox頁面存檔備份,存於互聯網檔案館). 1999.
  11. ^ CNN News. Smallest Web server fits in shirt pocket頁面存檔備份,存於互聯網檔案館). 1999.
  12. ^ "How to Bruise an Integer" 互聯網檔案館存檔,存檔日期2008-10-07., Byte, March 1995.
  13. ^ "Chain Reaction in Pentiums"頁面存檔備份,存於互聯網檔案館), Vaughan Pratt, 1994. In wdv-notes334, 22 Jan, 1995. Article is formatted from a newsgroup posting: Vaughan Pratt. "TECHNICAL: Chain reaction in Pentiums (Was: The Flaw: Pentium-Contaminated Data Persists)". Newsgroupcomp.sys.intel. 1994-12-30 [2006-06-03]. Usenet: [email protected]. (原始內容存檔於2012-11-04). 

外部連結