Nacimiento |
3 de enero de 1935 Boston |
---|---|
Nombre en idioma nativo | Richard Manning Karp |
Nacionalidad | americano |
Capacitación |
Harvard Escuela de Ingeniería y Ciencias Aplicadas de Harvard ( en ) Universidad de California, Berkeley |
Ocupaciones | Matemático , informático , profesor universitario |
Trabajé para | Universidad de California en Berkeley , Universidad de Washington |
---|---|
Áreas | Teoría de la computabilidad ( in ) , bioinformática |
Miembro de |
Asociación de Maquinaria de Computación Academia Estadounidense de Artes y Ciencias Sociedad Filosófica Estadounidense Asociación Estadounidense para el Avance de la Ciencia Academia Estadounidense de Ciencias (1980) Academia Nacional de Ingeniería de los Estados Unidos (1992) Academia de Ciencias (2002) |
Director de tesis | Anthony Oettinger |
Premios |
Premio Turing (1985) |
Un algoritmo simple para encontrar elementos frecuentes en arroyos y bolsas ( d ) |
Richard Manning Karp (nacido el3 de enero de 1935en Boston en Massachusetts ) es un investigador estadounidense conocido por su investigación en optimización combinatoria y teoría de la complejidad . Recibió el Premio Turing en 1985 por su trabajo.
Richard Karp es el hijo de Abraham y Rose Karp.
Ingresó en la Universidad de Harvard , donde recibió su licenciatura en 1955 , su maestría en 1956 y su doctorado en matemáticas aplicadas en 1959 .
Luego trabajó para IBM en el Centro de Investigación Thomas J. Watson.
En 1968 , se convirtió en profesor de informática y matemáticas en la Universidad de California en Berkeley , donde permaneció a partir de entonces, excepto por un período de cuatro años como profesor en la Universidad de Washington .
Fue director de tesis de Narendra Karmarkar , Noam Nisan y Rajeev Motwani entre otros.
Richard Karp ha trabajado principalmente en algoritmos y teoría de la complejidad . Entre sus contribuciones importantes se encuentran las siguientes.
Actualmente está interesado en la bioinformática .
Fue citado de la siguiente manera en el Premio Turing: “Por sus continuas contribuciones a la teoría de algoritmos, incluido el desarrollo de algoritmos eficientes para redes y otros problemas de optimización combinatoria, la identificación de computabilidad en tiempo polinomial con la noción intuitiva de algoritmo eficiente, y más todo, sus contribuciones a la teoría de NP-completitud . Karp introdujo la metodología ahora clásica para demostrar que un problema es NP-completo, lo que ha hecho posible identificar muchos problemas prácticos y teóricos como difíciles de calcular. "