Vaughan Pratt

Vaughan Pratt

Vaughan Ronald Pratt (* 12. April 1944 in Melbourne)^[1] ist ein australischer Informatiker und Hochschullehrer.

Leben

Pratt studierte an der Universität Sydney mit dem Bachelor-Abschluss 1967 und dem Master-Abschluss 1970 (mit einem Computerprogramm für die Syllogismen in der Logik von Lewis Carroll) und wurde 1972 an der Stanford University bei Donald Knuth promoviert mit einer Dissertation über Sortieralgorithmen (Shellsort) und Sportiernetzwerke. 1972 wurde er Assistant Professor und 1976 Associate Professor am Massachusetts Institute of Technology (MIT). 1980/81 war er zu einem Sabbatjahr an der Stanford University und leitete dort von 1980 bis 1982 das SUN Workstation Projekt. Er blieb in Stanford mit einer vollen Professur ab 1981. In dieser Zeit war er auch am Aufbau von Sun Microsystems wesentlich beteiligt, zunächst als Berater, dann für zwei Jahre 1983 bis 1985 in Stanford beurlaubt als Forschungsdirektor und schließlich wieder bis 1988 als Berater. 1985 war er wieder an der Stanford University. 2000 wurde er emeritiert.

Er war Berater von Honeywell (1972), IBM (1972 bis 1974, 1978 bis 1979), des Office of Naval Research (1974), VLSI Systems (1981/82).

Forschung und Lehre

Von ihm, James Hiram Morris und Donald Knuth stammt der Knuth-Morris-Pratt-Algorithmus, ein String-Matching-Algorithmus.^[2] Pratt hatte die Idee noch als Student 1970 unabhängig von Knuth (der kurze Zeit später darauf stieß), und Pratt und Morris veröffentlichten 1970 einen Technischen Bericht dazu.^[3] Schließlich veröffentlichten alle drei 1977 einen Aufsatz dazu.

1973 entwickelte er einen Parser (Pratt Parser).^[4] Er selbst wandte ihn in einer alternativen Implementierung (CGOL)^[5] von Maclisp an, einer Lisp-Variante, und der Parser wurde auch z. B. in Macsyma verwendet. Beides waren Bestandteile des umfassenden MAC-Projekts am MIT.

Er befasste sich auch mit Primzahltests und führte 1975 das Primzahl-Zertifikat (Pratt certificate) ein, ein kurzer Beweis dass eine Zahl Primzahl ist, basierend auf dem Primzahltest von Lucas (später kamen stark verbesserte Methoden auf).^[6]

Mitte der 1990er Jahre analysierte er den Pentium-FDIV-Bug. 1999 baute er den damals kleinsten Web-Server in der Größe einer Streichholzschachtel.^[7] Er war Gründer der Firma TIQIT Computers, die sich 2010 auflösten, und 1988 gründete er Triangle Concepts.

Mit Manuel Blum, Robert Floyd, Robert Tarjan und Ron Rivest^[8] entwickelte er 1973 einen approximativen Selektionsalgorithmus (Bestimmung der k-ten kleinsten Zahl in Listen und Arrays), den median of median Algorithmus.

Außerdem befasste er sich mit der Anwendung algebraischer Methoden zur Theorie der Nebenläufigkeit (Concurrency), digitaler Typographie, rechnergestützter Geometrie, Bildverarbeitung und Computersehen.

Sonstiges

In jüngster Zeit (2010er Jahre) befasst er sich mit dem Klimawandel.

Pratt heiratete 1969 Margot F. Coster, mit der er zwei Töchter hat.

Zu seinen Doktoranden gehören David Harel und Parham Aarabi (Universität Toronto).^[9]

Schriften (Auswahl)

Außer die in den Fußnoten zitierten Arbeiten.

• Shellsort and Sorting Networks, New York/London: Garland Publishing 1979

Weblinks

Commons: Vaughan Pratt – Sammlung von Bildern, Videos und Audiodateien

• Homepage in Stanford
• Stanford Profil

Einzelnachweise

1. ↑ Geburts- und Karrieredaten Men and Women of Science, Thomson Gale 2005
2. ↑ Knuth, Morris, Pratt: Fast Pattern Matching in Strings, SIAM Journal of Computing, Band 6, 1974, S. 323–350.
3. ↑ Pratt, Morris, A linear pattern-matching algorithm (Technical Report), University of California, Berkeley, Computation Center. TR-40.
4. ↑ Pratt, Top down operator precedence, Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1973, S. 41–51
5. ↑ Pratt, CGOL: An Alternative External Representation for LISP Users, AI Working Paper 121. MIT Artificial Intelligence Laboratory 1976
6. ↑ Pratt, Every prime has a succinct certificate, SIAM Journal on Computing, Band 4, 1975, S. 214–220
7. ↑ Surfing on a match box, BBC News, 10. Februar 1999
8. ↑ M: Blum, R. W. Floyd, V. R. Pratt, R. Rivest, R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, Band 7, 1973, S. 448–461.
9. ↑ Vaughan Pratt im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet