Leonid Levin

Leonid Anatolievič Levin
Leonid Anatolievič Levin
	ukrajinsko-rusko-americký informatik
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.

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

Pahýl

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.