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 los algoritmos de búsqueda , los algoritmos de ordenación y las pruebas de primalidad . Más recientemente, su investigación se ha centrado en el modelado formal de sistemas concurrentes y espacios de Chu .
Criado en Australia y educado en la 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 ahora se conoce como procesamiento del lenguaje natural . Luego fue a los Estados Unidos, donde completó una tesis de doctorado en la Universidad de Stanford en solo 20 meses bajo la supervisión del asesor Donald Knuth . Su tesis se centró en el análisis del algoritmo de ordenamiento Shellsort y las redes de ordenamiento . [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 fue 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 el funcionamiento inicial de Sun Microsystems , actuando como consultor durante su primer año, luego, tomando una licencia de Stanford durante 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 puede verificarse 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 de búsqueda de cadenas general más eficiente conocido 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 creó 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 de 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 utilizó como analizador subyacente para JSLint . [8] Pratt también implementó un editor de texto basado en TECO llamado "DOC", que luego se renombró como "ZED". [9]
En 1999, Pratt construyó el servidor web más pequeño del mundo (en ese momento): tenía el tamaño de una caja de cerillas. [10] [11]
En un artículo de la revista Byte de 1995, Pratt fue reconocido por proponer que el error FDIV de Pentium podría tener consecuencias peores que las que Intel o IBM estaban prediciendo en ese momento. [12] [13]
En la actualidad, 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 fundador, presidente y director de tecnología de TIQIT Computers, Inc. durante los diez años anteriores a su cierre en 2010.
