跳转到内容

沃恩·普拉特

维基百科,自由的百科全书
沃恩·普拉特
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). 

外部链接