Pratt, Vaughn Ronald

vaughn ronald pratt
inglés  vaughan ronald pratt
Fecha de nacimiento 12 de abril de 1944( 04/12/1944 ) (78 años)
Lugar de nacimiento
País
Esfera científica informática [1]
Lugar de trabajo
alma mater
consejero científico Donald Ervin Knuth [2]
Conocido como Uno de los autores del algoritmo Knuth-Morris-Pratt , autor del Pratt Simplicity Certificate y del Pratt Parser
Premios y premios Fello ACM
Sitio web profiles.stanford.edu/… (  inglés)
 Archivos multimedia en Wikimedia Commons

Vaughan Ronald Pratt ( nacido el  12 de abril de 1944 en Melbourne , Australia ) es un profesor emérito de la Universidad de Stanford , uno de los pioneros de la informática teórica . Desde 1969, Pratt ha realizado importantes contribuciones a áreas fundamentales como los algoritmos de búsqueda , la clasificación y las pruebas de . Su investigación más reciente se centra en el modelado formal de sistemas competitivos y espacios Chu El trabajo de Pratt se distingue por la aplicación a la informática de modelos de diversas áreas de las matemáticas: geometría , álgebra lineal y general , lógica matemática .

Carrera

En 1970, Pratt completó su tesis de maestría en la Universidad de Sydney en lo que ahora se conoce como procesamiento del lenguaje natural . Después de eso, se mudó a los Estados Unidos , donde defendió su tesis doctoral 20 meses después bajo la supervisión de Donald Knuth . El tema de su trabajo fue el análisis de Shellsort y redes de clasificación .

Pratt se desempeñó como profesor asistente en el MIT de 1972 a 1976 y luego como profesor extraordinario de 1976 a 1982. En 1974, con Knuth y Morris , Pratt completó y formalizó el trabajo que había comenzado en 1970 durante mis días de estudiante en Berkeley . Fruto de esta coautoría, apareció el Algoritmo Knuth-Morris-Pratt . En 1976, Pratt desarrolló un sistema de lógica dinámica  , una lógica modal de comportamiento estructurado.

En 1980-1981, Pratt se ausentó de la investigación en el MIT y se trasladó a la Universidad de Stanford , donde recibió una cátedra en 1981.

En 2000, Pratt se convirtió en profesor emérito de Stanford.

Logros clave

Varios algoritmos bien conocidos llevan el nombre de Pratt. El certificado de primalidad propuesto por Pratt mostró que la primalidad de los números se puede verificar en tiempo polinomial. De este hecho se sigue que el problema de verificar la simplicidad de los números radica en la clase NP y, por lo tanto, presumiblemente, no es co-NP completa [3] . Posteriormente, se desarrolló un algoritmo polinomial para verificar la simplicidad de un número. El algoritmo Knuth-Morris-Pratt , que Pratt desarrolló a principios de los años 70 con su colega de Stanford, Donald Knuth , independientemente de Morris , es el algoritmo de búsqueda de subcadenas general más eficiente que se conoce en la actualidad [4] . Junto con Bloom , Floyd , Rivest y Tarjan , Pratt describió la mediana de las medianas ( el algoritmo BFRPT por las iniciales de los autores), el primer algoritmo óptimo para elegir una estadística de orden [5] .

Notas

  1. ↑ 1 2 https://profiles.stanford.edu/vaughan-pratt
  2. ↑ Genealogía matemática  (inglés) - 1997.
  3. ↑ Vaughan Pratt. Cada primo tiene un certificado sucinto. Revista SIAM de Computación , vol.4, pp.214-220. 1975. Citas Archivado el 6 de junio de 2008 en Wayback Machine , texto completo Archivado el 26 de septiembre de 2007 en Wayback Machine (requiere inicio de sesión pagado)
  4. ↑ Donald Knuth, James H. Morris, Jr. y Vaughan Pratt. Coincidencia rápida de patrones en cadenas. SIAM Journal on Computing , 6(2):323-350. 1977. Citas Archivado el 4 de enero de 2010 en Wayback Machine .
  5. ↑ Blum, M .; Floyd, OR ; Pratt, VR ; Rivest, R.L .; Tarjan, RE Límites de tiempo para la selección  //  Journal of Computer and System Sciences : diario. - 1973. - Agosto ( vol. 7 , no. 4 ). - Pág. 448-461 . - doi : 10.1016/S0022-0000(73)80033-9 .

Enlaces

  Ir al elemento de Wikidata  sitios temáticos