- Leonid Levin
-
Pour les articles homonymes, voir Levin.Leonid Anatolievich Levin 
Leonid Levin en 2010Leonid Anatolievich Levin (russe : Леонид Анатольевич Левин, né le 2 novembre 1948 à Dnipropetrovsk, RSS d'Ukraine) est un informaticien russo-américain. Il est connu notamment pour avoir découvert la notion de NP-complétude en même temps que Stephen Cook.
Sommaire
Biographie
Il obtient son master en 1970 et l'équivalent du doctorat en 1972 à l'Université de Moscou sous la direction d'Andreï Kolmogorov. En 1978, il émigre aux États-Unis et obtient également un doctorat au Massachusetts Institute of Technology en 1979. Son directeur de thèse au MIT est Albert Meyer.
Il est connu pour son travail sur le hasard en informatique, la complexité algorithmique, la complexité en moyenne des algorithmes[1], la probabilité algorithmique, la théorie de la calculabilité et la théorie de l'information.
Sa vie est décrite dans un chapitre du livre Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists[2].
Levin a découvert indépendamment de Stephen Cook le théorème central de la NP-complétude, qu'on nomme aujourd'hui théorème de Cook-Levin. Ce théorème est lié au problème P = NP, l'un des sept problèmes du prix du millénaire pour lesquels l'institut Clay offre un prix d'un million de dollars. C'est une découverte majeure de l'informatique théorique et le fondement de la théorie de la complexité. L'article de Levin est publié en 1973, mais il en avait présenté les idées lors de ses enseignements quelques années auparavant (voir l'étude de Trakhtenbrot[3]), bien que l'écriture complète et formelle des résultats soit postérieure à la publication du résultat de Cook.
Il est actuellement professeur d'informatique à l'Université de Boston, où il enseigne depuis 1980.
Notes et références
- Leonid Levin. Average-case complete problems. SIAM J. Comput., 15:285–286, 1986.
- Shasha, Dennis; Cathy Lazere (September 1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Springer. ISBN 0-387-97992-1.
- Boris A. Trakhtenbrot (1984). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". Annals of the History of Computing (IEEE) 6 (4): 384–400.
Voir aussi
Articles connexes
- Théorème de Cook-Levin
Liens externes
Catégories :- Naissance en 1948
- Personnalité américaine en informatique
- Personnalité en informatique théorique
Wikimedia Foundation. 2010.
