Richard Karp

Biographie
Naissance	3 janvier 1935 (89 ans) ; Boston
Nom dans la langue maternelle	Richard Manning Karp
Nationalite	americaine
Formation	Universite Harvard ; Harvard School of Engineering and Applied Sciences ( en ) ; Universite de Californie a Berkeley
Activites	Mathematicien , informaticien , professeur d'universite
A travaille pour	Universite de Californie a Berkeley ; Universite de Washington
Membre de	Academie americaine des sciences ( 1980 ) ; Academie nationale d'ingenierie des Etats-Unis ( 1992 ) ; Academie des sciences ( 2002 ) ; Society for Industrial and Applied Mathematics ( 2009 ) ; Academie americaine des arts et des sciences ; Association for Computing Machinery ; Societe americaine de philosophie ; Association americaine pour l'avancement des sciences
Directeur de these	Anthony Oettinger
Site web	www.eecs.berkeley.edu/Faculty/Homepages/karp.html
Distinctions	Prix Turing ( 1985 ) ; Liste detaillee Prix Frederick W. Lanchester ( 1977 ) ; Prix Fulkerson ( 1979 ) ; Prix Turing ( 1985 ) ; Prix de theorie John-von-Neumann ( 1990 ) ; ACM Fellow ( 1994 ) ; National Medal of Science ( 1996 ) ; Prix Harvey ( 1998 ) ; Prix EATCS ( 2000 ) ; Benjamin Franklin Medal ( 2004 ) ; Medaille Benjamin-Franklin ( 2004 ) ; Prix de Kyoto en technologies avancee ( 2008 ) ; Membre honoraire de la Society for Industrial and Applied Mathematics ( 2009 ) ; Prix Dickson de science ( 2009 ) ; Docteur honoris causa du Technion ; Medaille du centenaire de l’universite Harvard ; Docteur honoris causa de l'Institut Weizmann ; Docteur honoris causa de l'Ecole polytechnique federale de Zurich
	A simple algorithm for finding frequent elements in streams and bags ( d )

Richard Manning Karp (ne le 3 janvier 1935 a Boston dans le Massachusetts ) est un chercheur americain connu notamment pour ses recherches en optimisation combinatoire et theorie de la complexite . Il a recu le prix Turing en 1985 pour ses travaux.

Biographie [ modifier | modifier le code ]

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

Il est entre a l' universite Harvard , ou il recut son Bachelor's degree en 1955 , son Master's degree en 1956 , et son Ph.D. de mathematiques appliquees en 1959 ^[
2
]^,^[
3
].

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

En 1968 , il devient professeur d'informatique et de mathematiques a l' universite de Californie a Berkeley ^[
2
], ou il reste ensuite, a l'exception d'une periode de quatre ans comme professeur a l' universite de Washington .

Il a ete le directeur de these de Narendra Karmarkar , Noam Nisan et Rajeev Motwani entre autres ^[
3
].

Travaux [ modifier | modifier le code ]

Richard Karp a surtout travaille en algorithmique et en theorie de la complexite . Parmi ses contributions importantes, on compte notamment les points suivants.

En 1971 il a developpe, avec Jack Edmonds , l' algorithme d'Edmonds-Karp pour resoudre le probleme de flot maximum dans les reseaux ^[
4
].
En 1972 il a publie un article fondateur en theorie de la complexite, dans lequel il prouve la NP-completude de 21 problemes ^[
5
].
En 1973, il publie avec John Hopcroft , l' algorithme de Hopcroft-Karp pour un probleme de couplage ^[
6
].
En 1980, il prouve avec Richard J. Lipton , le theoreme de Karp-Lipton , en theorie de la complexite ^[
7
].
En 1987 , il a codeveloppe l' algorithme de Rabin-Karp ^[
8
].

Il s'interesse actuellement a la bio-informatique .

Prix et distinctions [ modifier | modifier le code ]

1985 prix Turing ^[
2
]
1987 Conference von Neumann
1990 prix de theorie John-von-Neumann ^[
9
]
1996 National Medal of Science
2004 Medaille Benjamin Franklin en informatique pour ses travaux sur la complexite algorithmique

Il fut cite de la facon suivante lors de la remise du prix Turing : ≪ Pour ses contributions continues a la theorie des algorithmes, notamment le developpement d'algorithmes efficaces pour les reseaux et d'autres problemes d'optimisation combinatoires, l'identification de calculabilite en temps polynomial avec la notion intuitive d'algorithme efficace, et surtout, ses contributions a la theorie de la NP-completude . Karp a introduit la methodologie desormais classique pour prouver qu'un probleme est NP-complet, ce qui a permis d'identifier de nombreux problemes pratiques et theoriques comme etant difficiles a calculer. ≫

Source [ modifier | modifier le code ]

M. Gondran et M. Minoux, Graphes et algorithmes , Eyrolles , coll. ≪ Dir. Et. & Rech. EDF ≫, 1979 ( reimpr. 1984, 1995, 2009 chez Lavoisier: 4 ^e ed.), 546 p.

Notes et references [ modifier | modifier le code ]

(en) Cet article est partiellement ou en totalite issu de l’article de Wikipedia en anglais intitule ≪ Richard Karp ≫ ( voir la liste des auteurs ) .

↑ https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf
↑ ^{a
b
c
et
d} ≪ citation du prix Turing ≫, sur Association for Computing Machinery
↑ ^{a
et
b} (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 [ modifier | modifier le code ]

Notices d'autorite :
- VIAF
- ISNI
- BnF ( donnees )
- IdRef
- LCCN
- GND
- Pays-Bas
- Israel
- NUKAT
- Norvege
- WorldCat
Notice dans un dictionnaire ou une encyclopedie generaliste :
- Britannica
Ressources relatives a la recherche :
(en) ACM Crossroads magazine : interview de Richard Karp
(en) Page personnelle

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

[turing-2] {a
b
c
et
d} ≪ citation du prix Turing ≫, sur Association for Computing Machinery

[mathgenealogy-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, 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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]