Un article de Wikipedia, l'encyclopedie libre.
Richard Manning Karp
(ne le
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.
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
]
.
Richard Karp a surtout travaille en
algorithmique
et en
theorie de la complexite
. Parmi ses contributions importantes, on compte notamment les points suivants.
Il s'interesse actuellement a la
bio-informatique
.
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. ≫
- M. Gondran
et M. Minoux,
Graphes et algorithmes
,
Eyrolles
,
coll.
≪ Dir. Et. & Rech. EDF ≫,
(
reimpr.
1984, 1995, 2009 chez Lavoisier:
4
e
ed.), 546
p.
- ↑
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,
,
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,
,
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
,
(
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,
,
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