Vaughan Pratt
| Vaughan Pratt | |
|---|---|
 | |
| Conhecido(a) por | Algoritmo de Knuth-Morris-Pratt |
| Nascimento | 1944 (80 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
- ↑ Vaughan Pratt (em inglês) no Mathematics Genealogy Project
- ↑ 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)
- ↑ Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350. 1977. Citations
- ↑ 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
- ↑ Pratt, V.R., Top Down Operator Precedence. Proceedings of the ACM Symposium on Principles of Programming Languages. 1973. pp41-51.
- ↑ George J. Carrette A simple Pratt-Parser for SIOD. 1990.
- ↑ https://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js jslint source code line 2224
- ↑ Eric Fischer. Emacs and Other Editors. alt.folklore.computers. November 15, 2000.
- ↑ BBC News.Surfing on a matchbox. 1999.
- ↑ CNN News. Smallest Web server fits in shirt pocket. 1999.
- ↑ "How to Bruise an Integer" Arquivado em 7 de outubro de 2008, no Wayback Machine., Byte, March 1995.
- ↑ "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]
- 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.
