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

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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$952@Radon.Stanford.EDU. Consultado em 3 de junho de 2006 

Ligações externas

[editar | editar código-fonte]