Леонід Анатолійович Левін (нар. 2 листопада 1948, Дніпропетровськ) — радянський і американський математик, фахівець в області теорії обчислювальної складності. Професор інформатики в Бостонському університеті.
Леонід Анатолійович Левін | |
---|---|
Народився | 2 листопада 1948 (75 років) Дніпропетровськ, Українська РСР, СРСР |
Місце проживання | США |
Країна | США СРСР |
Діяльність | математик, інформатик |
Alma mater | d Массачусетський технологічний інститут (1979) МДУ[1] |
Галузь | математика |
Заклад | Бостонський університет |
Науковий ступінь | доктор філософії[1] (1979) |
Науковий керівник | Колмогоров Андрій Миколайович і d[1] |
Аспіранти, докторанти | d[1] d[1] d[1] |
Членство | Американська академія мистецтв і наук[2] Національна академія наук США[3] |
Нагороди | |
Левін Леонід Анатолійович у Вікісховищі |
Життєпис
Народився 2 листопада 1948 року в Дніпропетровську.
1970 — закінчив Московський державний університет, після чого працював там же на посаді наукового співробітника під науковим керівництвом Андрія Колмогорова.
1971 — представив кандидатську дисертацію, виконавши всі формальні вимоги щодо її попереднього опробування, дисертація була схвалена Колмогоровим, усіма опонентами і головною організацією, однак вчений ступінь Левіну присуджена не була. Формальною причиною для цього послужила «невизначеність політичного обличчя» здобувача, що, в сукупності з наступними утисками в наукових колах, стали однією з причин еміграції.
В 1972—1973 роках працював в , а з 1973 по 1977 роки — у Всесоюзному науково-дослідному інституті комплексної автоматизації нафтової і газової промисловості (ВНИИКАНефтегаз) на посаді старшого наукового співробітника.
У 1978 році емігрував в США. У 1979 році отримав диплом доктора філософії з математики в Массачусетському технологічному інституті.
1980 — працює і викладає в Бостонському університеті.
2014 — обраний членом Американської академії мистецтв і наук.
Основні результати в області теорії ймовірностей в застосуванні до інформатики, теорії складності обчислень.
Незалежно від Стівена Кука довів у 1971 році теорему Кука — Левіна, завдяки якій була сформульована проблема рівності класів P і NP, яка стала однією з задач тисячоліття. Робота була опублікована лише в 1973 році, але була повідомлена на конференціях, що пізніше дозволило встановити пріоритет Левіна.
Нагороди
- 2004 — (Лондонський університет)
- 2010 — Премія Гумбольдта
- 2012 — Премія Кнута
Примітки
- Математичний генеалогічний проєкт — 1997.
- https://www.amacad.org/person/leonid-levin
- http://www.nasonline.org/member-directory/members/2542359.html
- (PDF). Архів оригіналу (PDF) за 29 березня 2017. Процитовано 11 січня 2017.
- (PDF). Архів оригіналу (PDF) за 4 березня 2016. Процитовано 11 січня 2017.
- . Архів оригіналу за 19 червня 2017. Процитовано 11 січня 2017.
- . Архів оригіналу за 14 жовтня 2017. Процитовано 11 січня 2017.
- Кутателадзе С. Премия по информатике для выходца из СССР [ 25 жовтня 2016 у Wayback Machine.] // . № 23 (117) от 20 ноября 2012. С. 14.
- (PDF). Архів оригіналу (PDF) за 19 квітня 2016. Процитовано 11 січня 2017.
- Л. А. Левин Универсальные задачи перебора [ 10 жовтня 2017 у Wayback Machine.] (рус.) // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116.
- Boris A. Trakhtenbrot A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms (англ.) // Annals of the History of Computing. — 1984. — Vol. 6, no. 4. — P. 384—400.
- Second Annual Kolmogorov Lecture [ 5 березня 2016 у Wayback Machine.] (англ.)
- Leonid Levin Wins Humboldt Research Award [ 30 травня 2010 у Wayback Machine.] (англ.)
- . Архів оригіналу за березень 3, 2016. Процитовано січень 11, 2017.
- . Архів оригіналу за 16 січня 2017. Процитовано 11 січня 2017.
Література
- Dennis Elliott Shasha, Cathy A. Lazere. Stephen Cook and Leonid Levin: A good solution is hard to find // Out of their minds: the lives and discoveries of 15 great computer scientists. — Springer, 1998. — С. 139—156. — 291 с. — (Copernicus Series). — .
Посилання
- Персональная страница на сайте Бостонского университета [Архівовано 8 травня 2012 у WebCite] (англ.).
- Curriculum vitae [Архівовано 8 травня 2012 у WebCite] (англ.).
- Список публикаций [ 29 травня 2016 у Wayback Machine.] (англ.).
- Диссертация А. Л. Левина [ 29 березня 2017 у Wayback Machine.]
- Отзывы о диссертации Л. А. Левина [ 4 березня 2016 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshih lyudej iz prizvishem Levin Leonid Anatolijovich Levin nar 2 listopada 1948 Dnipropetrovsk radyanskij i amerikanskij matematik fahivec v oblasti teoriyi obchislyuvalnoyi skladnosti Profesor informatiki v Bostonskomu universiteti Leonid Anatolijovich LevinNarodivsya2 listopada 1948 1948 11 02 75 rokiv Dnipropetrovsk Ukrayinska RSR SRSRMisce prozhivannyaSShAKrayina SShA SRSRDiyalnistmatematik informatikAlma materd Massachusetskij tehnologichnij institut 1979 MDU 1 GaluzmatematikaZakladBostonskij universitetNaukovij stupindoktor filosofiyi 1 1979 Naukovij kerivnikKolmogorov Andrij Mikolajovich i d 1 Aspiranti doktorantid 1 d 1 d 1 ChlenstvoAmerikanska akademiya mistectv i nauk 2 Nacionalna akademiya nauk SShA 3 Nagorodipremiya Knuta 2012 premiya Gumboldta 2010 Grant Guggengajma 1993 Levin Leonid Anatolijovich u VikishovishiZhittyepisNarodivsya 2 listopada 1948 roku v Dnipropetrovsku 1970 zakinchiv Moskovskij derzhavnij universitet pislya chogo pracyuvav tam zhe na posadi naukovogo spivrobitnika pid naukovim kerivnictvom Andriya Kolmogorova 1971 predstaviv kandidatsku disertaciyu vikonavshi vsi formalni vimogi shodo yiyi poperednogo oprobuvannya disertaciya bula shvalena Kolmogorovim usima oponentami i golovnoyu organizaciyeyu odnak vchenij stupin Levinu prisudzhena ne bula Formalnoyu prichinoyu dlya cogo posluzhila neviznachenist politichnogo oblichchya zdobuvacha sho v sukupnosti z nastupnimi utiskami v naukovih kolah stali odniyeyu z prichin emigraciyi V 1972 1973 rokah pracyuvav v a z 1973 po 1977 roki u Vsesoyuznomu naukovo doslidnomu instituti kompleksnoyi avtomatizaciyi naftovoyi i gazovoyi promislovosti VNIIKANeftegaz na posadi starshogo naukovogo spivrobitnika U 1978 roci emigruvav v SShA U 1979 roci otrimav diplom doktora filosofiyi z matematiki v Massachusetskomu tehnologichnomu instituti 1980 pracyuye i vikladaye v Bostonskomu universiteti 2014 obranij chlenom Amerikanskoyi akademiyi mistectv i nauk Osnovni rezultati v oblasti teoriyi jmovirnostej v zastosuvanni do informatiki teoriyi skladnosti obchislen Nezalezhno vid Stivena Kuka doviv u 1971 roci teoremu Kuka Levina zavdyaki yakij bula sformulovana problema rivnosti klasiv P i NP yaka stala odniyeyu z zadach tisyacholittya Robota bula opublikovana lishe v 1973 roci ale bula povidomlena na konferenciyah sho piznishe dozvolilo vstanoviti prioritet Levina Nagorodi2004 Londonskij universitet 2010 Premiya Gumboldta 2012 Premiya KnutaPrimitkiMatematichnij genealogichnij proyekt 1997 d Track Q829984 https www amacad org person leonid levin http www nasonline org member directory members 2542359 html PDF Arhiv originalu PDF za 29 bereznya 2017 Procitovano 11 sichnya 2017 PDF Arhiv originalu PDF za 4 bereznya 2016 Procitovano 11 sichnya 2017 Arhiv originalu za 19 chervnya 2017 Procitovano 11 sichnya 2017 Arhiv originalu za 14 zhovtnya 2017 Procitovano 11 sichnya 2017 Kutateladze S Premiya po informatike dlya vyhodca iz SSSR 25 zhovtnya 2016 u Wayback Machine 23 117 ot 20 noyabrya 2012 S 14 PDF Arhiv originalu PDF za 19 kvitnya 2016 Procitovano 11 sichnya 2017 L A Levin Universalnye zadachi perebora 10 zhovtnya 2017 u Wayback Machine rus Problemy peredachi informacii 1973 T 9 3 S 115 116 Boris A Trakhtenbrot A Survey of Russian Approaches to Perebor Brute Force Searches Algorithms angl Annals of the History of Computing 1984 Vol 6 no 4 P 384 400 Second Annual Kolmogorov Lecture 5 bereznya 2016 u Wayback Machine angl Leonid Levin Wins Humboldt Research Award 30 travnya 2010 u Wayback Machine angl Arhiv originalu za berezen 3 2016 Procitovano sichen 11 2017 Arhiv originalu za 16 sichnya 2017 Procitovano 11 sichnya 2017 LiteraturaDennis Elliott Shasha Cathy A Lazere Stephen Cook and Leonid Levin A good solution is hard to find Out of their minds the lives and discoveries of 15 great computer scientists Springer 1998 S 139 156 291 s Copernicus Series ISBN 0387982698 PosilannyaPersonalnaya stranica na sajte Bostonskogo universiteta Arhivovano 8 travnya 2012 u WebCite angl Curriculum vitae Arhivovano 8 travnya 2012 u WebCite angl Spisok publikacij 29 travnya 2016 u Wayback Machine angl Dissertaciya A L Levina 29 bereznya 2017 u Wayback Machine Otzyvy o dissertacii L A Levina 4 bereznya 2016 u Wayback Machine