Richard Karp

Richard Manning Karp (né le 3 janvier 1935 à 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

Richard Karp en 2009.

Biographie
Naissance	3 janvier 1935 Boston
Nom dans la langue maternelle	Richard Manning Karp
Nationalité	Américaine
Formation	Université Harvard Harvard School of Engineering and Applied Sciences (en) Université de Californie à Berkeley
Activités	Mathématicien, informaticien, professeur d'université

Autres informations
A travaillé pour	Université de Californie à Berkeley, université de Washington
Membre de	Association américaine pour l'avancement des sciences Association for Computing Machinery Académie américaine des arts et des sciences Société américaine de philosophie Académie américaine des sciences (1980) Académie nationale d'ingénierie des États-Unis (1992) Académie des sciences (2002) Society for Industrial and Applied Mathematics (2009)
Dir. de thèse	Anthony Oettinger
Distinctions	Prix Turing (1985) Liste détaillée Docteur honoris causa de l'École polytechnique fédérale de Zurich Docteur honoris causa du Technion Médaille du centenaire de l’université Harvard Docteur honoris causa de l'Institut Weizmann Prix de Kyoto Prix Frederick W. Lanchester (1977) Prix Fulkerson (1979) Prix Turing (1985) Prix de théorie John-von-Neumann (1990) ACM Fellow (1994) National Medal of Science (1996) Prix Harvey (1998) Prix EATCS (2000) Benjamin Franklin Medal (2004) Médaille Benjamin-Franklin (2004) Prix de Kyoto en technologies avancée (2008) Fellow of the Society for Industrial and Applied Mathematics (2009) Prix Dickson de science (2009)

Œuvres principales
A simple algorithm for finding frequent elements in streams and bags (d)

Biographie

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

Travaux

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

En 1971 il a développé, avec Jack Edmonds, l'algorithme d'Edmonds-Karp pour résoudre le problème de flot maximum dans les réseaux[4].
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[5].
En 1973, il publie avec John Hopcroft, l'algorithme de Hopcroft-Karp pour un problème de couplage[6].
En 1980, il prouve avec Richard J. Lipton, le théorème de Karp-Lipton, en théorie de la complexité[7].
En 1987, il a codéveloppé l'algorithme de Rabin-Karp[8].

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

Prix et distinctions

1985 prix Turing[2]
1987 Conférence von Neumann
1990 prix de théorie John-von-Neumann[9]
1996 National Medal of Science
2004 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. »

Source

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

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Richard Karp » (voir la liste des auteurs).

https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf
« citation du prix Turing », sur Association for Computing Machinery
(en) « Richard Karp », sur le site du Mathematics Genealogy Project
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, n^o 2,‎ 1972, p. 248–264 (DOI 10.1145/321694.321699)
(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.
John Hopcroft et Richard Karp, « An n^5/2 algorithm for maximum matchings in bipartite graphs », SIAM Journal on Computing, vol. 2, n^o 4,‎ 1973, p. 225-231 (DOI 10.1137/0202019)
Richard M. Karp et Richard J. Lipton, « Some connections between nonuniform and uniform complexity classes », dans Symposium on Theory of Computing, 1980 (DOI 10.1145/800141.804678), p. 302-309.
Richard M. nom2=Rabin Karp, « Efficient randomized pattern-matching algorithms », IBM Journal of Research and Development, vol. 31, n^o 2,‎ mars 1987, p. 249–260 (DOI 10.1147/rd.312.0249, lire en ligne).
« Prix de Richard Karp », sur Institute for Operations Research and the Management Sciences

Liens externes

Notices d'autorité :
Notice dans un dictionnaire ou une encyclopédie généraliste :
- Encyclopædia Britannica
Ressources relatives à la recherche :
- (en) Digital Bibliography & Library Project
- (en) Mathematics Genealogy Project
- (mul) Scopus
(en) ACM Crossroads magazine : interview de Richard Karp
(en) Page personnelle

Portail de l’informatique
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] ttps://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf

[turing-2] « citation du prix Turing », sur Association for Computing Machinery

[mathgenealogy-3] (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, n^o 2,‎ 1972, 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 n^5/2 algorithm for maximum matchings in bipartite graphs », SIAM Journal on Computing, vol. 2, n^o 4,‎ 1973, 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, 1980 (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, n^o 2,‎ mars 1987, 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