Leonid Levin
Leonid Anatolievič Levin (rusky Леонид Анатольевич Левин; * 2. listopad 1948, Dnipro, Ukrajina, tehdy Ukrajinská SSR, SSSR) je ukrajinsko-americký informatik a matematik. Zabývá se především teoretickou informatikou – především výpočetní složitostí, pravděpodobnostními algoritmy a teorií informace.
| Leonid Anatolievič Levin | |
|---|---|
 | |
| Narození | 2. listopadu 1948 (76 let) Dnipro, Ukrajina, tehdy Ukrajinská SSR, SSSR |
| Alma mater | Massachusettský technologický institut (do 1979) Fakulta mechaniky a matematiky Lomonosovovy univerzity Lomonosovova univerzita |
| Pracoviště | Bostonská univerzita (od 1980) |
| Obory | informatika a teorie pravděpodobnosti |
| Ocenění | Guggenheimovo stipendium (1993) cena Alexandra von Humboldta (2010) Knuthova cena (2012) |
Některá data mohou pocházet z datové položky. | |
Levin v roce 1970 vystudoval Moskovskou státní univerzitu M. V. Lomonosova, kde v roce 1972 získal i titul kandidáta věd. Jeho školitelům byl Andrej Nikolajevič Kolmogorov. Později emigroval do Spojených států, kde v roce 1978 získal titul PhD. na MIT. V současnosti působí jako profesor na Bostonské univerzitě.
Leonid Levin je znám především díky své práci v oblasti výpočetní složitosti. Nezávisle na Stephenu Cookovi V roce 1971 objevil, že problém splnitelnosti booleovské formulí (SAT) je NP-úplný, čímž dokázal existenci NP-úplných problémů. Tento výsledek je v současnosti znám jako Cookova-Levinova věta.
Reference
editovatV tomto článku byly použity překlady textů z článků Leonid Anatolievič Levin na slovenské Wikipedii, Leonid Levin na anglické Wikipedii a Левин, Леонид Анатольевич na ruské Wikipedii.
Externí odkazy
editovat
Obrázky, zvuky či videa k tématu Leonid Levin na Wikimedia Commons
