Левін Леонід Анатолійович

(Перенаправлено з Леонід Левін)

Леонід Анатолійович Левін (нар. 2 листопада 1948Дніпропетровськ) — радянський і американський математик, фахівець в області теорії обчислювальної складності. Професор інформатики в Бостонському університеті.

Леонід Анатолійович Левін
LeonidLevin2010.jpg
Народився 2 листопада 1948(1948-11-02) (72 роки)
м. Дніпропетровськ, Україна
Місце проживання США
Країна Flag of the United States.svg США
Flag of the Soviet Union.svg СРСР
Діяльність математик, інформатик
Alma mater Московський державний університет імені М. В. Ломоносова
Галузь математика
Заклад Бостонський університет
Ступінь кандидат фізико-математичних наук
Науковий керівник Колмогоров Андрій Миколайович і Альберт Меєрd[1]
Аспіранти, докторанти Gene Itkisd[1], Ramarathnam Venkatesand[1] і Siva Raj Rajagopaland[1]
Членство Американська академія мистецтв і наук і Національна академія наук США
Нагороди

CMNS: Левін Леонід Анатолійович у Вікісховищі

ЖиттєписРедагувати

Народився 2 листопада 1948 року в Дніпропетровську

1970 — закінчив Московський державний університет, після чого працював там же на посаді наукового співробітника під науковим керівництвом Андрія Колмогорова. 

1971 — представив кандидатську дисертацію[2], виконавши всі формальні вимоги щодо її попереднього опробування, дисертація була схвалена Колмогоровим, усіма опонентами і головною організацією[3], однак вчений ступінь Левіну присуджена не була[4][5]. Формальною причиною для цього послужила «невизначеність політичного обличчя» здобувача, що, в сукупності з наступними утисками в наукових колах, стали однією з причин еміграції[6].

В 1972-1973 роках працював в Інституті проблем передачі інформації АН СРСР, а з 1973 по 1977 роки — у Всесоюзному науково-дослідному інституті комплексної автоматизації нафтової і газової промисловості (ВНИИКАНефтегаз) на посаді старшого наукового співробітника.

У 1978 році емігрував в США. У 1979 році отримав диплом доктора філософії з математики в Массачусетському технологічному інституті

1980 — працює і викладає в Бостонському університеті

2014 — обраний членом Американської академії мистецтв і наук.[7]

Основні результати в області теорії ймовірностей в застосуванні до інформатики, теорії складності обчислень.

Незалежно від Стівена Кука довів у 1971 році теорему Кука — Левіна, завдяки якій була сформульована проблема рівності класів P і NP, яка стала однією з задач тисячоліття. Робота була опублікована лише в 1973 році[8], але була повідомлена на конференціях, що пізніше дозволило встановити пріоритет Левіна[9].

НагородиРедагувати

ПриміткиРедагувати

  1. а б в г Математична генеалогія — 1997.
  2. Кандидатская диссертация Л. А. Левина
  3. Отзывы на диссертацию Л. А. Левина
  4. Б. А. Трахтенброт. Памяти Андрея Петровича Ершова
  5. Интервью с Леонидом Левиным
  6. Кутателадзе С. Премия по информатике для выходца из СССР // Троицкий вариант — Наука. № 23 (117) от 20 ноября 2012. С. 14.
  7. The New 2014 Academy Members
  8. Л. А. Левин Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116.
  9. 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.
  10. Second Annual Kolmogorov Lecture (англ.)
  11. Leonid Levin Wins Humboldt Research Award Архівовано 30 травня 2010 у Wayback Machine. (англ.)
  12. ACM press release, August 22, 2012. Архів оригіналу за березень 3, 2016. Процитовано січень 11, 2017. 
  13. Премия Кнута 2012 присуждена Леониду Левину

ЛітератураРедагувати

ПосиланняРедагувати