Richard karp

Richard karp Imagen en Infobox. Richard Karp en 2009. Biografía
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
Otras informaciones
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)
Obras primarias
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.

Biografía

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.

Obras

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 .

Premios y reconocimientos

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. "

Fuente

Notas y referencias

  1. https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf
  2. "  Turing Premio de cita  " , en la Association for Computing Machinery
  3. (en) “  Richard Karp  ” , en la página web del Proyecto Matemáticas Genealogía
  4. Jack Edmonds y Richard M. Karp , "  Mejoras teóricas en la eficiencia algorítmica para problemas de flujo de red  ", Revista de la ACM , Asociación de Maquinaria de Computación (ACM), vol.  19, n o  21972, p.  248–264 ( DOI  10.1145 / 321694.321699 )
  5. (en) Richard M. Karp reducibilidad entre problemas combinatorios . En Complejidad de los cálculos informáticos , Proc. Lindo. IBM Thomas J. Watson Res. Center, Yorktown Heights, Nueva York. Nueva York: Plenum, p. 85-103. 1972.
  6. John Hopcroft y Richard Karp, "  Un algoritmo n 5/2 para coincidencias máximas en gráficos bipartitos  ", SIAM Journal on Computing , vol.  2, n o  4, 1973, p.  225-231 ( DOI  10.1137 / 0202019 )
  7. Richard M. Karp y Richard J. Lipton, "Algunas conexiones entre clases de complejidad uniformes y no uniformes" , en Simposio sobre Teoría de la Computación , 1980( DOI  10.1145 / 800141.804678 ) , pág.  302-309.
  8. Richard M. nom2 = Rabin Karp , "  Algoritmos de coincidencia de patrones aleatorios eficientes  ", IBM Journal of Research and Development , vol.  31, n o  2Marzo de 1987, p.  249–260 ( DOI  10.1147 / rd.312.0249 , leer en línea ).
  9. "  Premio Richard Karp  " , sobre el Instituto de Investigación de Operaciones y Ciencias de la Gestión

enlaces externos