Vaughan Pratt (nacido el 12 de abril de 1944) es profesor emérito de la Universidad de Stanford y uno de los pioneros en el campo de la informática . Desde 1969, Pratt ha realizado varias contribuciones en áreas fundamentales como algoritmos de búsqueda , algoritmos de clasificación y pruebas de primalidad . Más recientemente, su investigación se ha centrado en el modelado formal de sistemas concurrentes y espacios Chu .
Criado en Australia y educado en Knox Grammar School , donde fue dux en 1961, Pratt asistió a la Universidad de Sydney , donde completó su tesis de maestría en 1970, relacionada con lo que hoy se conoce como procesamiento del lenguaje natural . Luego viajó a los Estados Unidos, donde realizó un doctorado. tesis en la Universidad de Stanford en sólo 20 meses bajo la supervisión del asesor Donald Knuth . Su tesis se centró en el análisis del algoritmo de clasificación Shellsort y las redes de clasificación . [1]
Pratt fue profesor asistente en el MIT (1972 a 1976) y luego profesor asociado (1976 a 1982). En 1974, trabajando en colaboración con Knuth y James H. Morris , Pratt completó y formalizó el trabajo que había comenzado en 1970 como estudiante de posgrado en Berkeley ; el resultado en coautoría fue el algoritmo de coincidencia de patrones Knuth-Morris-Pratt . En 1976 desarrolló el sistema de lógica dinámica , una lógica modal de comportamiento estructurado.
Se tomó un año sabático del MIT a Stanford (1980 a 1981) y fue nombrado profesor titular en Stanford en 1981.
Pratt dirigió el proyecto de la estación de trabajo SUN en Stanford de 1980 a 1982. Contribuyó de diversas maneras a la fundación y al funcionamiento inicial de Sun Microsystems , actuando como consultor durante su primer año y luego tomando una licencia de Stanford para el los siguientes dos años, convirtiéndose en director de investigación y finalmente retomando su papel como consultor de Sun y regresando a Stanford en 1985.
También diseñó el logotipo de Sun Microsystems , [2] que presenta cuatro copias intercaladas de la palabra "sol" ; es un ambigrama .
Pratt se convirtió en profesor emérito de Stanford en 2000.
Varios algoritmos conocidos llevan el nombre de Pratt. Los certificados Pratt , pruebas breves de la primalidad de un número, demostraron de manera práctica que la primalidad se puede verificar de manera eficiente, colocando el problema de prueba de primalidad en la clase de complejidad NP y proporcionando la primera evidencia sólida de que el problema no es co-NP-completo. . [3] El algoritmo Knuth-Morris-Pratt , que Pratt diseñó a principios de la década de 1970 junto con su colega profesor de Stanford Donald Knuth e independientemente de Morris , sigue siendo el algoritmo general de búsqueda de cadenas más eficiente que se conoce en la actualidad. [4] Junto con Blum , Floyd , Rivest y Tarjan , describió la mediana de medianas , el primer algoritmo de selección óptima en el peor de los casos . [5]
Pratt construyó algunas herramientas útiles. En 1976, escribió un documento de trabajo del MIT AI Lab sobre CGOL , una sintaxis alternativa para MACLISP que había diseñado e implementado basándose en su paradigma para el análisis de precedencia de operadores de arriba hacia abajo. [6] Su analizador a veces se denomina " analizador Pratt " [7] y se ha utilizado en sistemas posteriores, como MACSYMA . Douglas Crockford también lo usó como analizador subyacente para JSLint . [8] Pratt también implementó un editor de texto basado en TECO llamado "DOC", que luego pasó a llamarse "ZED". [9]
En 1999, Pratt construyó el servidor web más pequeño (en ese momento) del mundo: tenía el tamaño de una caja de cerillas. [10] [11]
A Pratt se le atribuyó en un artículo de la revista Byte de 1995 el mérito de proponer que el error Pentium FDIV podría tener peores consecuencias de las que Intel o IBM predijeron en ese momento. [12] [13]
Hoy Pratt tiene una amplia influencia. Además de su cátedra en Stanford, es miembro de al menos siete organizaciones profesionales. Es miembro de la Association for Computing Machinery y forma parte del consejo editorial de tres importantes revistas de matemáticas. También fue el fundador, presidente y director de tecnología de TIQIT Computers, Inc. durante los diez años anteriores a que cerrara sus puertas en 2010.