Aller au contenu

Richard Karp

Un article de Wikipédia, l'encyclopédie libre.
Richard Karp
Richard Karp en 2009.
Biographie
Naissance
Voir et modifier les données sur Wikidata (89 ans)
BostonVoir et modifier les données sur Wikidata
Nom dans la langue maternelle
Richard Manning KarpVoir et modifier les données sur Wikidata
Nationalité
Formation
Université Harvard
Harvard School of Engineering and Applied Sciences (en)
Université de Californie à BerkeleyVoir et modifier les données sur Wikidata
Activités
Autres informations
A travaillé pour
Membre de
Directeur de thèse
Site web
Distinctions
Œuvres principales
A simple algorithm for finding frequent elements in streams and bags (d)Voir et modifier les données sur Wikidata

Richard Manning Karp (né le à Boston dans le Massachusetts) est un chercheur américain connu notamment pour ses recherches en optimisation combinatoire et théorie de la complexité. Il a reçu le prix Turing en 1985 pour ses travaux.

Richard Karp est le fils d'Abraham et Rose Karp[1].

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[2],[3].

Il a ensuite travaillé pour IBM au centre de recherche Thomas J. Watson[2].

En 1968, il devient professeur d'informatique et de mathématiques à l'université de Californie à Berkeley[2], où il reste ensuite, à l'exception d'une période de quatre ans comme professeur à l'université de Washington.

Il a été le directeur de thèse de Narendra Karmarkar, Noam Nisan et Rajeev Motwani entre autres[3].

Richard Karp a surtout travaillé en algorithmique et en théorie de la complexité. Parmi ses contributions importantes, on compte notamment les points suivants.

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

  • M. Gondran et M. Minoux, Graphes et algorithmes, Eyrolles, coll. « Dir. Ét. & Rech. EDF », (réimpr. 1984, 1995, 2009 chez Lavoisier: 4e éd.), 546 p.

Notes et références

[modifier | modifier le code]
  1. https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf
  2. a b c et d « citation du prix Turing », sur Association for Computing Machinery
  3. a et b (en) « Richard Karp », sur le site du Mathematics Genealogy Project
  4. Jack Edmonds et Richard M. Karp, « Theoretical improvements in algorithmic efficiency for network flow problems », Journal of the ACM, Association for Computing Machinery (ACM), vol. 19, no 2,‎ , p. 248–264 (DOI 10.1145/321694.321699)
  5. (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.
  6. John Hopcroft et Richard Karp, « An n5/2 algorithm for maximum matchings in bipartite graphs », SIAM Journal on Computing, vol. 2, no 4,‎ , p. 225-231 (DOI 10.1137/0202019)
  7. Richard M. Karp et Richard J. Lipton, « Some connections between nonuniform and uniform complexity classes », dans Symposium on Theory of Computing, (DOI 10.1145/800141.804678), p. 302-309.
  8. Richard M. nom2=Rabin Karp, « Efficient randomized pattern-matching algorithms », IBM Journal of Research and Development, vol. 31, no 2,‎ , p. 249–260 (DOI 10.1147/rd.312.0249, lire en ligne).
  9. « Prix de Richard Karp », sur Institute for Operations Research and the Management Sciences

Liens externes

[modifier | modifier le code]