Левін Леонід Анатолійович
Леонід Анатолійович Левін (нар. 2 листопада 1948, Дніпропетровськ) — радянський і американський математик, фахівець в області теорії обчислювальної складності. Професор інформатики в Бостонському університеті.
| Леонід Анатолійович Левін | |
|---|---|
 | |
| Народився |
2 листопада 1948 (75 років) Дніпропетровськ, Українська РСР, СРСР |
| Місце проживання | США |
| Країна |
 США СРСР |
| Діяльність | математик, інформатик |
| Alma mater |
механіко-математичний факультет МДУd Массачусетський технологічний інститут (1979) МДУ[1] |
| Галузь | математика |
| Заклад | Бостонський університет |
| Науковий ступінь | доктор філософії[1] (1979) |
| Науковий керівник | Колмогоров Андрій Миколайович і Альберт Меєрd[1] |
| Аспіранти, докторанти |
Gene Itkisd[1] Ramarathnam Venkatesand[1] Siva Raj Rajagopaland[1] |
| Членство |
Американська академія мистецтв і наук[2] Національна академія наук США[3] |
| Нагороди | |
 Левін Леонід Анатолійович у Вікісховищі | |
Життєпис ред.
Народився 2 листопада 1948 року в Дніпропетровську.
1970 — закінчив Московський державний університет, після чого працював там же на посаді наукового співробітника під науковим керівництвом Андрія Колмогорова.
1971 — представив кандидатську дисертацію[4], виконавши всі формальні вимоги щодо її попереднього опробування, дисертація була схвалена Колмогоровим, усіма опонентами і головною організацією[5], однак вчений ступінь Левіну присуджена не була[6][7]. Формальною причиною для цього послужила «невизначеність політичного обличчя» здобувача, що, в сукупності з наступними утисками в наукових колах, стали однією з причин еміграції[8].
В 1972—1973 роках працював в Інституті проблем передачі інформації АН СРСР, а з 1973 по 1977 роки — у Всесоюзному науково-дослідному інституті комплексної автоматизації нафтової і газової промисловості (ВНИИКАНефтегаз) на посаді старшого наукового співробітника.
У 1978 році емігрував в США. У 1979 році отримав диплом доктора філософії з математики в Массачусетському технологічному інституті.
1980 — працює і викладає в Бостонському університеті.
2014 — обраний членом Американської академії мистецтв і наук.[9]
Основні результати в області теорії ймовірностей в застосуванні до інформатики, теорії складності обчислень.
Незалежно від Стівена Кука довів у 1971 році теорему Кука — Левіна, завдяки якій була сформульована проблема рівності класів P і NP, яка стала однією з задач тисячоліття. Робота була опублікована лише в 1973 році[10], але була повідомлена на конференціях, що пізніше дозволило встановити пріоритет Левіна[11].
Нагороди ред.
- 2004 — Медаль Колмогорова (Лондонський університет)[12]
- 2010 — Премія Гумбольдта[13]
- 2012 — Премія Кнута[14][15]
Примітки ред.
- ↑ а б в г д е Математичний генеалогічний проєкт — 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.
- ↑ The New 2014 Academy Members (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.] (англ.)
- ↑ ACM press release, August 22, 2012. Архів оригіналу за березень 3, 2016. Процитовано січень 11, 2017.
- ↑ Премия Кнута 2012 присуждена Леониду Левину. Архів оригіналу за 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). — ISBN 0387982698.
Посилання ред.
- Персональная страница на сайте Бостонского университета [Архівовано 8 травня 2012 у WebCite] (англ.).
- Curriculum vitae [Архівовано 8 травня 2012 у WebCite] (англ.).
- Список публикаций [Архівовано 29 травня 2016 у Wayback Machine.] (англ.).
- Диссертация А. Л. Левина [Архівовано 29 березня 2017 у Wayback Machine.]
- Отзывы о диссертации Л. А. Левина [Архівовано 4 березня 2016 у Wayback Machine.]