Leonid Levin

Leonid Levin
Page d'aide sur l'homonymie Pour les articles homonymes, voir Levin.
Leonid Anatolievich Levin
Leonid Levin en 2010
Leonid Levin en 2010

Leonid 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

  1. Leonid Levin. Average-case complete problems. SIAM J. Comput., 15:285–286, 1986.
  2. 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.
  3. 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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Leonid Levin de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Leonid Levin — Leonid Anatólievich Levin Леонид Анатольевич Левин (nació el 2 de noviembre de 1948 en la antigua URSS). Es informático, estudió siguiendo los pasos de Andréi Kolmogórov. Leonid obtuvo su primer Doctorado en filosofía en 1972 en la universidad de …   Wikipedia Español

  • Leonid Levin — Leonid Anatolievich Levin ( he. לאוניד אנטולייביץ לוין; ru. Леонид Анатольевич Левин; born November 2, 1948 in Dnipropetrovsk Ukrainian SSR) is a computer scientist. He studied under Andrey Kolmogorov.He obtained his master degree in 1970 and… …   Wikipedia

  • Leonid Levin — (* 2. November 1948 in Dnipropetrowsk) ist ein amerikanischer Informatiker. Biografie Levin war Schüler von Andrei Kolmogorow. 1973 entwickelte er unabhängig von den damaligen Bestrebungen im Westen eine Theorie der NP Vollständigkeit …   Deutsch Wikipedia

  • Leonid Lewin — Leonid Levin (* 2. November 1948 in Dnipropetrowsk) ist ein ukrainischer Informatiker. Biografie Levin war Schüler von Andrei Kolmogorow. 1973 entwickelte er unabhängig von den damaligen Bestrebungen im Westen eine Theorie der NP Vollständigkeit …   Deutsch Wikipedia

  • Levin — bezeichnet: die Stadt Levin (Neuseeland) in Neuseeland die Gemeinde Levín in Tschechien einen Ortsteil der Stadt Dargun im Landkreis Mecklenburgische Seenplatte in Mecklenburg Vorpommern Levin ist außerdem ein männlicher Vorname, den folgende… …   Deutsch Wikipedia

  • Levin (surname) — The surname Levin comes from the Jewish biblical tribe of Levi, whose descendants the Levites had distinctive duties in the Temple period. Variations on this surname include Levy, Levine, Levitt and many others. A – J * Alan Levin, an American… …   Wikipedia

  • Levin — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour l’article homophone, voir Levain. Levin peut renvoyer à : Patronymes Carl Levin (1934 ), homme politique américain Hanoch Lev …   Wikipédia en Français

  • Leonid Kritz — 2007 beim Schachfestival im Jüdischen Museum …   Deutsch Wikipedia

  • Cook–Levin theorem — In computational complexity theory, the Cook–Levin theorem, also known as Cook s theorem, states that the Boolean satisfiability problem is NP complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing… …   Wikipedia

  • Felix Levin — Felix Levin, 2008 Land Deutschland  Deutschland …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”