Vaughan Pratt

Vaughan Pratt
Conhecido(a) por	Algoritmo de Knuth-Morris-Pratt
Nascimento	1944 (81 anos)
Nacionalidade	australiano
Orientador(es)(as)	Donald Knuth[1]
Instituições	Universidade Stanford
Campo(s)	Ciência da computação

Vaughan Ronald Pratt (1944) é um cientista da computação australiano. É professor emérito da Universidade Stanford e um pioneiro no campo da ciência da computação.

Maiores contribuições

Um número de algoritmos bem conhecidos carregam o nome de Pratt. Certificados de Pratt, pequenas provas da primalidade de um número, demonstraram de um modo prático, que a primalidade pode ser eficientemente verificada, colocando o problema do teste de primalidade na classe de complexidade NP e fornecendo a primeira evidência forte de que o problema não é co-NP-complete.[2] O algoritmo de Knuth-Morris-Pratt, o qual Pratt projetou no início dos anos 70 junto com professores de Stanford Donald Knuth e independentemente Morris, ainda é o algoritmo de busca de string mais geral e eficiente conhecido hoje.[3] Junto com Blum, Floyd, Rivest, e Tarjan, ele descreveu o primeiro pior-caso do algoritmo de seleção ótimo.[4]

Ferramenta de construção útil

Pratt construiu algumas ferramentas úteis. Em 1976, ele escreveu um artigo de trabalho no MIT AI Lab sobre CGOL, uma sintaxe alternativa para MACLISP que ele havia projetado e implementado com base em seu paradigma de top down a precedência do operador de análise.[5] O seu analisador é algumas vezes chamado de "Pratt parser"[6] e tem sido usado em sistemas posteriores, como o MACSYMA. Douglas Crockford também usou isso como o analisador subjacente para o JSLint.[7] Pratt também implementou um TECO - editor de texto baseado no chamado "DOC", que mais tarde foi renomeado para "ZED".[8]

Em 1999, Pratt construiu o menor servidor de internet do mundo (na época) — tinha o tamanho de uma caixa de fósforo.[9][10]

Outras contribuições

Pratt foi honrado em um artigo da revista Byte magazine (1995) por propor que o Pentium FDIV bug poderia ter consequências piores do que a Intel ou a IBM estavam prevendo na época.[11][12]

Hoje Pratt tem uma grande influência. Além do ser professor de Stanford, ele mantém adesão em pelos menos sete organizações profissionais. Pratt é fellow da Association for Computing Machinery e está no Editorial Board das três maiores revistas matemáticas. Ele é também o presidente e CTO da TIQIT Computers, Inc..

Referências

1. Vaughan Pratt (em inglês) no Mathematics Genealogy Project
2. Vaughan Pratt. Todo primo tem um certificado sucinto. SIAM Journal on Computing, vol.4, pp.214–220. 1975. Citations, Full-text Arquivado em 26 de setembro de 2007, no Wayback Machine. (requires paid login)
3. Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350. 1977. Citations
4. M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, "Time bounds for selection," J. Comput. System Sci. 7 (1973), pp.448–461
5. Pratt, V.R., Top Down Operator Precedence. Proceedings of the ACM Symposium on Principles of Programming Languages. 1973. pp41-51.
6. George J. Carrette A simple Pratt-Parser for SIOD. 1990.
7. https://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js jslint source code line 2224
8. Eric Fischer. Emacs and Other Editors. alt.folklore.computers. November 15, 2000.
9. BBC News.Surfing on a matchbox. 1999.
10. CNN News. Smallest Web server fits in shirt pocket. 1999.
11. "How to Bruise an Integer" Arquivado em 7 de outubro de 2008, no Wayback Machine., Byte, March 1995.
12. "Chain Reaction in Pentiums", Vaughan Pratt, 1994. In wdv-notes334, 22 Jan, 1995. Article is formatted from a newsgroup posting: Vaughan Pratt (30 de dezembro de 1994). «"TECHNICAL: Chain reaction in Pentiums (Was: The Flaw: Pentium-Contaminated Data Persists)"». Grupo de notícias: comp.sys.intel. 3e097i$[e-mail]. Consultado em 3 de junho de 2006 

Ligações externas

• Faculty home page at Stanford University
• Abstract page, com downloads de texto completo de muitas das publicações de Pratt.
• Douglas Crockford walks through creating a Pratt parser in JavaScript.