Leonid Levin
Leonid Anatolievič Levin | |
---|---|
![]() ukrajinsko-rusko-americký informatik | |
Narození | 2. listopadu 1948 (75 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. |
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.
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
V 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
Obrázky, zvuky či videa k tématu Leonid Levin na Wikimedia Commons
![]() | Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |
Laureáti Knuthovy ceny | |
---|---|
Andrew Jao (1996) • Leslie Valiant (1997) • László Lovász (1999) • Jeffrey Ullman (2000) • Christos Papadimitriou (2002) • Miklós Ajtai (2003) • Mihalis Yannakakis (2005) • Nancy Lynch (2007) • Volker Strassen (2008) • David S. Johnson (2010) • Ravi Kannan (2011) • Leonid Levin (2012) • Gary Miller (2013) • Richard J. Lipton (2014) • László Babai (2015) • Noam Nisan (2016) • Oded Goldreich (2017) • Johan Håstad (2018) • Avi Wigderson (2019) • Cynthia Dwork (2020) • Moshe Vardi (2021) • Noga Alon (2022) |