Vaughan Pratt (nacido el 12 de abril de 1944) es un profesor emérito de la Universidad de Stanford , que fue uno de los pioneros en el campo de la informática . Desde 1969, Pratt ha hecho varias contribuciones a á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 .
Vaughan Pratt | |
---|---|
Nació | Vaughan Ronald Pratt 12 de abril de 1944 |
Educación | Universidad de Stanford (1972) Universidad de Sydney (1970) |
Conocido por | Algoritmo de Knuth-Morris- Pratt Certificado de Pratt Analizador de Pratt |
Carrera científica | |
Campos | Ciencias de la Computación |
Instituciones | MIT de la Universidad de Stanford |
Asesores académicos | Donald Knuth |
Sitio web | boole |
Carrera profesional
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 ahora se conoce como procesamiento del lenguaje natural . Luego se fue a los Estados Unidos, donde completó un doctorado. tesis 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 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 Morris , Pratt completó y formalizó el trabajo que había comenzado en 1970 como estudiante de posgrado en Berkeley ; el resultado de la coautoría fue el algoritmo de coincidencia de patrones de Knuth-Morris-Pratt . En 1976, desarrolló el sistema de lógica dinámica , una lógica modal de comportamiento estructurado.
Pasó 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 varias formas a la fundación y operación inicial de Sun Microsystems , actuando como consultor durante su primer año, luego tomando una licencia de Stanford para el En los dos años siguientes, se convirtió en director de investigación y finalmente retomó su papel como consultor de Sun y regresó a Stanford en 1985.
También diseñó el logotipo de Sun Microsystems , que presenta cuatro copias intercaladas de la palabra "sol" ; es un ambigrama .
Pratt se convirtió en profesor emérito en Stanford en 2000.
Contribuciones importantes
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 primordialidad 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. . [2] El algoritmo Knuth-Morris-Pratt , que Pratt diseñó a principios de la década de 1970 junto con el 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. [3] Junto con Blum , Floyd , Rivest y Tarjan , describió la mediana de las medianas , el primer algoritmo de selección óptimo en el peor de los casos . [4]
Construcción de herramientas útiles
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 en base a su paradigma para el análisis de precedencia de operadores de arriba hacia abajo. [5] Su analizador a veces se denomina " analizador de Pratt " [6] y se ha utilizado en sistemas posteriores, como MACSYMA . Douglas Crockford también lo usó como analizador subyacente para JSLint . [7] Pratt también implementó un editor de texto basado en TECO llamado "DOC", que luego pasó a llamarse "ZED". [8]
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. [9] [10]
Otras contribuciones
En un artículo de la revista Byte de 1995, se reconoció a Pratt por proponer que el error Pentium FDIV podría tener peores consecuencias de lo que Intel o IBM estaban prediciendo en ese momento. [11] [12]
Hoy Pratt tiene una gran 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 está en el 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 cuando cerró sus puertas en 2010.
Referencias
- ^ Vaughan Ronald Pratt: Shellsort y redes de clasificación . Garland Publishing, Inc., Nueva York y Londres, 1979, ISBN 0-8240-4406-1
- ^ Vaughan Pratt. Cada prime tiene un certificado sucinto. SIAM Journal on Computing , vol.4, pp.214-220. 1975. Citas , texto completo (requiere inicio de sesión pagado)
- ^ Donald Knuth, James H. Morris, Jr. y Vaughan Pratt. Emparejamiento rápido de patrones en cadenas. SIAM Journal on Computing , 6 (2): 323–350. 1977. Citas
- ^ Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (agosto de 1973). "Plazos de selección" (PDF) . Revista de Ciencias de la Computación y Sistemas . 7 (4): 448–461. doi : 10.1016 / S0022-0000 (73) 80033-9 .
- ^ Pratt, VR, precedencia del operador de arriba hacia abajo. Actas del Simposio ACM sobre principios de lenguajes de programación . 1973. pp41-51.
- ^ George J. Carrette Un simple Pratt-Parser para SIOD . 1990.
- ^ https://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js jslint línea de código fuente 2224
- ^ Eric Fischer. Emacs y otros editores . alt.folklore.computers. 15 de noviembre de 2000.
- ^ BBC News. Navegando en una caja de cerillas . 1999.
- ^ Noticias de CNN. El servidor web más pequeño cabe en el bolsillo de la camisa . 1999.
- ^ "Cómo magullar un entero" Archivado el 7 deoctubre de 2008en la Wayback Machine , Byte, marzo de 1995.
- ^ "Reacción en cadena en Pentiums" , Vaughan Pratt, 1994. En wdv-notes334, 22 de enero de 1995. El artículo tiene el formato de una publicación de un grupo de noticias: Vaughan Pratt (30 de diciembre de 1994). " " TÉCNICO: reacción en cadena en Pentiums (era: el defecto: persisten datos contaminados con Pentium) " " . Grupo de noticias : comp.sys.intel . Usenet: [email protected] . Consultado el 3 de junio de 2006 .
enlaces externos
- Vaughan Pratt en el Proyecto de genealogía matemática
- Página de inicio de la facultad en la Universidad de Stanford
- Página de resumen , con descargas de texto completo de muchas de las publicaciones de Pratt.
- Douglas Crockford explica cómo crear un analizador de Pratt en JavaScript.