Leonid Levin - Leonid Levin

Leonid Anatolievič Levin
LeonidLevin2010.jpg
Leonid Levin v roce 2010
narozený ( 1948-11-02 )02.11.1948 (věk 72)
Dněpropetrovsk , Ukrajinská SSR , Sovětský svaz
Alma mater Moskevská univerzita,
Massachusetts Institute of Technology
Známý jako Cookova-Levinova věta
Složitost průměrných případů
Výzkum složitosti, náhodnosti, informací
Ocenění Knuthova cena (2012)
Vědecká kariéra
Pole matematika
Informatika
Instituce Bostonská univerzita
Doktorský poradce Andrey Kolmogorov , Albert R. Meyer

Leonid Anatolievich Levin ( / l eɪ . Oʊ n jsem d l ɛ v ɪ n / lay-OH NEED LEV -v ; ruského : Леонид Анатольевич Левин ; ukrajinského : Леонід Анатолійович Левін ; narozený 02.11.1948) je sovětský -Americký matematik a počítačový vědec .

Je známý svou prací v náhodnosti ve výpočetní technice , algoritmické složitosti a neřešitelnosti, složitosti průměrných případů , základech matematiky a počítačové vědy , algoritmické pravděpodobnosti , teorii výpočtu a teorii informací . Magisterský titul získal na Moskevské univerzitě v roce 1970, kde studoval u Andreje Kolmogorova a v roce 1972 dokončil akademické požadavky na kandidátský titul .

On a Stephen Cook nezávisle objevili existenci NP-úplných problémů . Tato věta o úplnosti NP, často nazývaná Cookova-Levinova věta , byla základem pro jeden ze sedmi problémů s cenou tisíciletí vyhlášených Clay Mathematics Institute s nabídnutou cenou 1 000 000 $. Cookova - Levinova věta byla průlomem v počítačové vědě a důležitým krokem ve vývoji teorie výpočetní složitosti .

Levin získal v roce 2012 Knuthovu cenu za objev NP-úplnosti a rozvoj komplexnosti průměrných případů . Je členem Národní akademie věd USA a členem Americké akademie umění a věd .

Životopis

Magisterský titul získal na Moskevské univerzitě v roce 1970, kde studoval u Andrey Kolmogorova a v roce 1972. Absolvoval akademické požadavky kandidátského titulu. Po výzkumu algoritmických problémů teorie informací na Moskevském institutu pro přenos informací Národní akademie věd v letech 1972–1973 , a pozice vedoucího vědeckého pracovníka Moskevského národního výzkumného ústavu integrované automatizace pro ropný/plynový průmysl v letech 1973–1977, v roce 1978 emigroval do USA a získal také titul Ph.D. na Massachusetts Institute of Technology (MIT) v roce 1979. Jeho poradcem na MIT byl Albert R. Meyer .

On je dobře známý pro jeho práci v náhodnosti ve výpočetní technice , algoritmické složitosti a neřešitelnosti, složitosti průměrných případů , základech matematiky a počítačové vědy , algoritmické pravděpodobnosti , teorii výpočtu a informační teorii .

Jeho život je popsán v kapitole knihy Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists .

Levin a Stephen Cook nezávisle objevili existenci NP-úplných problémů . Tato věta o úplnosti NP, často nazývaná Cookova-Levinova věta , byla základem pro jeden ze sedmi problémů s cenou tisíciletí vyhlášených Clay Mathematics Institute s nabídnutou cenou 1 000 000 $. Cookova - Levinova věta byla průlomem v počítačové vědě a důležitým krokem ve vývoji teorie výpočetní složitosti . Levinův článek v časopise o této větě byl publikován v roce 1973; přednášel o myšlenkách v něm několik let před touto dobou (viz Trakhtenbrotův průzkum), ačkoli úplné formální sepsání výsledků proběhlo po Cookově publikaci.

Levin získal v roce 2012 Knuthovu cenu za objev NP-úplnosti a rozvoj komplexnosti průměrných případů .

V současné době je profesorem informatiky na Bostonské univerzitě , kde v roce 1980 začal učit.

Poznámky

Reference

externí odkazy