Richard Karp


Richard Karp
Karp mg 7725-b.cr2.jpg

Richard Manning Karp, né en 1935 à Boston dans le Massachusetts, est un informaticien américain, connu pour ses recherches en théorie de la complexité. Il a reçu le prix Turing en 1985 pour ces travaux.

Né de Abraham et Rose Karp à Boston, Karp a trois frères et sœurs : Robert, David et Carolyn. Il est entré à l'université Harvard, où il reçut son Bachelor's degree en 1955, son Master's degree en 1956, et son Ph.D. de mathématiques appliquées en 1959. Il a ensuite travaillé pour IBM au centre de recherche Thomas J. Watson. En 1968, il devient professeur d'informatique et de mathématiques à l'université de Californie, Berkeley, où il restera ensuite, à l'exception d'une période de 4 ans comme professeur à l'université de Washington. Richard Karp a reçu la National Medal of Science et en 2004 la médaille Benjamin Franklin en informatique pour ses travaux sur la complexité algorithmique.

Il fut cité de la façon suivante lors de la remise du prix Turing : Pour ses contributions continues à la théorie des algorithmes, notamment le développement d'algorithmes efficaces pour les réseaux et d'autres problèmes d'optimisation combinatoires, l'identification de calculabilité en temps polynomial avec la notion intuitive d'algorithme efficace, et surtout, ses contributions à la théorie de la NP-complétude. Karp a introduit la méthodologie désormais classique pour prouver qu'un problème est NP-complet, ce qui a permis d'identifier de nombreux problèmes pratiques et théoriques comme étant difficiles à calculer.

En 1971 il a co-développé avec Jack Edmonds l'algorithme d'Edmonds-Karp pour résoudre le problème du flux maximum dans les réseaux, et en 1972 il a publié un article fondateur en théorie de la complexité, dans lequel il prouve la NP-complétude de 21 problèmes[1].

En 1987, il a co-développé l'algorithme de Rabin-Karp.

Il s'intéresse actuellement à la bio-informatique.

Notes et références

  1. (en) Richard M. Karp, Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum, p.85-103. 1972.


Voir aussi

Liens externes



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Richard Karp de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Richard Karp — Saltar a navegación, búsqueda Richard Karp Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el …   Wikipedia Español

  • Richard Karp — ist der Name folgender Personen: Richard A. Karp (* 1944), amerikanischer Informatiker Richard M. Karp (* 1935), amerikanischer Informatiker Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeichne …   Deutsch Wikipedia

  • Richard Karp — Infobox Scientist name = Richard Manning Karp image width = caption = birth date = January 3, 1935 birth place = Boston, Massachusetts death date = death place = residence = citizenship = nationality = American ethnicity = field = Computer… …   Wikipedia

  • Richard M. Karp — Richard Karp Richard Karp, né en 1935 à Boston dans le Massachusetts, est un informaticien américain, connu pour ses recherches en théorie de la complexité. Il a reçu le prix Turing en 1985 pour ces travaux. Né de Abraham et Rose Karp à …   Wikipédia en Français

  • Richard M. Karp — Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie. 1985 erhielt er für seine Forschungsarbeit auf… …   Deutsch Wikipedia

  • Karp — may refer to:People*Barrie Karp (born 1945), U.S. philosopher and visual artist *Bob Karp (1911 mdash;1975), U.S. comics writer *Carol Karp (1926 mdash;1972), U.S. mathematician, professor at the University of Maryland. *David Karp (1922… …   Wikipedia

  • Richard W. Hamming — Richard Hamming Richard Hamming Nom de naissance Richard Wesley Hamming Naissance 11 février 1915 Chicago (Illinois) Décès 7 janvier 1998 (à 72 ans) Monterey (Californie) Nationalité …   Wikipédia en Français

  • Richard Wesley Hamming — Richard Hamming Richard Hamming Nom de naissance Richard Wesley Hamming Naissance 11 février 1915 Chicago (Illinois) Décès 7 janvier 1998 (à 72 ans) Monterey (Californie) Nationalité …   Wikipédia en Français

  • Richard Hamming — Naissance 11 février 1915 Chicago (Illinois) Décès 7 janvier 1998 (à 82 ans) Monterey (Californie) Nationalité …   Wikipédia en Français

  • Richard E. Stearns — Richard Stearns Pour les articles homonymes, voir Stearns. Richard Edwin Stearns (né le 5 juillet 1936) est un informaticien qui, avec Juris Hartmanis, a reçu en 1993 le prix Turing pour leurs recherches communes sur les bases de la théorie de la …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.