From Wikipedia, the free encyclopedia
Leonid Anatolievič Levin (rus. Леонид Анатольевич Левин; * 2. november 1948, Dnipro, Ukrajina, vtedy Ukrajinská SSR, ZSSR) je sovietsko-americký informatik a matematik. Zaoberá sa predovšetkým teoretickou informatikou - najmä výpočtovou zložitosťou, pravdepodobnostnými algoritmami a teóriou informácií.
Leonid Anatolievič Levin | |
ukrajinsko-rusko-americký informatik | |
Narodenie | 2. november 1948 (75 rokov) Dnipro, Ukrajina, vtedy Ukrajinská SSR, ZSSR |
---|---|
Odkazy | |
Commons | Leonid Anatolievič Levin |
Levin v roku 1970 vyštudoval Moskovskú štátnu univerzitu M. V. Lomonosova, kde v roku 1972 získal aj titul kandidáta vied. Jeho školiteľom bol Andrej Nikolajevič Kolmogorov. Neskôr emigroval do Spojených štátov, kde na Massachusettskom technologickom inštitúte získal v roku 1978 titul PhD. V súčasnosti pôsobí ako profesor na Bostonskej univerzite.
Leonid Levin je známy predovšetkým vďaka svojej práci v oblasti výpočtovej zložitosti. Nezávisle od Stephena Cooka v roku 1971 objavil, že SAT je NP-úplný problém, čím dokázal existenciu NP-úplných problémov. Tento výsledok je v súčasnosti známy ako Cookova-Levinova veta.
V novembri 2012 sa Leonid Levin stal laureátom Ceny Donalda E. Knutha (Donald E. Knuth Prize), ktorá sa udeľuje od roku 1996 za mimoriadny prínos k rozvoju informatiky. [1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.