Richard Karp

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Karp.
Richard Karp en 2009

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

Biographie[modifier | modifier le code]

Richard Karp 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 reste ensuite, à l'exception d'une période de 4 ans comme professeur à l'université de Washington.

Contributions fondamentales[modifier | modifier le code]

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

Prix et distinctions[modifier | modifier le code]

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

Source[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  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[modifier | modifier le code]

Liens externes[modifier | modifier le code]