Leonid Lewin - Leonid Levin
Leonid Anatolijewicz Lewin | |
|---|---|
 Leonid Levin w 2010 roku
| |
| Urodzić się |
2 listopada 1948 |
| Alma Mater |
Uniwersytet Moskiewski Massachusetts Institute of Technology |
| Znany z |
Twierdzenie Cooka-Levina Złożoność przeciętnego przypadku Badania złożoności, losowości, informacji |
| Nagrody | Nagroda Knutha (2012) |
| Kariera naukowa | |
| Pola |
matematyka informatyka |
| Instytucje | Uniwersytet Bostoński |
| Doradca doktorski | Andriej Kołmogorow , Albert R. Meyer |
Leonid Anatolievich Levin ( / l eɪ . Oʊ n ı d l ɛ V ɪ n / lay-OH POTRZEBA LEV -W ; Rosyjskiej : Леонид Анатольевич Левин ; ukraińskiego : Леонід Анатолійович Левін , urodzony 02 listopada 1948) jest radziecki -Amerykański matematyk i informatyk .
Znany jest z pracy nad losowością w obliczeniach , złożonością i nierozwiązywalnością algorytmiczną, złożonością przypadków przeciętnych , podstawami matematyki i informatyki , prawdopodobieństwem algorytmicznym , teorią obliczeń i teorią informacji . Uzyskał tytuł magistra na Uniwersytecie w Moskwie w 1970 roku, gdzie studiował pod Andrieja Kołmogorowa i zakończył Kandydat Nasilenie akademickich wymogów w 1972 roku.
On i Stephen Cook niezależnie odkryli istnienie problemów NP-zupełnych . To twierdzenie o NP-zupełności, często nazywane twierdzeniem Cooka-Levina , było podstawą jednego z siedmiu problemów związanych z Nagrodą Milenijną ogłoszonych przez Clay Mathematics Institute z oferowaną nagrodą w wysokości 1 000 000 USD. Twierdzenie Cooka-Levina było przełomem w informatyce i ważnym krokiem w rozwoju teorii złożoności obliczeniowej .
Levin został nagrodzony Nagrodą Knutha w 2012 roku za odkrycie NP-zupełności i rozwój średniej złożoności przypadku . Jest członkiem amerykańskiej Narodowej Akademii Nauk i członkiem Amerykańskiej Akademii Sztuki i Nauki .
Biografia
Uzyskał tytuł magistra na Uniwersytecie w Moskwie w 1970 roku, gdzie studiował pod Andrieja Kołmogorowa i zakończył Kandydat Nasilenie akademickich wymogów w roku 1972. Po zbadaniu problemów algorytmicznych teorii informacji w Moskiewskim Instytucie Informacji Przekazanie Narodowej Akademii Nauk w 1972-1973 oraz stanowisko starszego naukowca w Moskiewskim Narodowym Instytucie Badawczym Zintegrowanej Automatyki Przemysłu Naftowego/Gazowego w latach 1973-1977, wyemigrował do Stanów Zjednoczonych w 1978 roku, gdzie również uzyskał stopień doktora. w Massachusetts Institute of Technology (MIT) w 1979 roku. Jego doradcą w MIT był Albert R. Meyer .
Jest dobrze znany ze swoich prac nad losowością w obliczeniach , złożonością i nierozwiązywalnością algorytmiczną, złożonością przypadków średnich , podstawami matematyki i informatyki , prawdopodobieństwem algorytmicznym , teorią obliczeń i teorią informacji .
Jego życie zostało opisane w rozdziale książki Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists .
Levin i Stephen Cook niezależnie odkryli istnienie problemów NP-zupełnych . To twierdzenie o NP-zupełności, często nazywane twierdzeniem Cooka-Levina , było podstawą jednego z siedmiu problemów związanych z Nagrodą Milenijną ogłoszonych przez Clay Mathematics Institute z oferowaną nagrodą w wysokości 1 000 000 USD. Twierdzenie Cooka-Levina było przełomem w informatyce i ważnym krokiem w rozwoju teorii złożoności obliczeniowej . Artykuł Levina w czasopiśmie na temat tego twierdzenia został opublikowany w 1973 roku; wykładał zawarte w nim idee przez kilka lat wcześniej (patrz ankieta Trakhtenbrota ), chociaż pełne formalne spisanie wyników nastąpiło po publikacji Cooka.
Levin został nagrodzony Nagrodą Knutha w 2012 roku za odkrycie NP-zupełności i rozwój średniej złożoności przypadku .
Obecnie jest profesorem informatyki na Uniwersytecie Bostońskim , gdzie rozpoczął nauczanie w 1980 roku.
Uwagi
Bibliografia
- „Leonid A. Levin” . Matematyka Genealogia Projekt .
Zewnętrzne linki
- Strona domowa Levina na Uniwersytecie Bostońskim.
- 2012 Nagroda Knutha dla Leonida Levin