Леонид Левин - Википедия - Leonid Levin

Леонид Анатольевич Левин
ЛеонидЛевин2010.jpg
Леонид Левин в 2010 году
Родившийся (1948-11-02) 2 ноября 1948 г. (возраст 72)
Днепропетровск, Украинская ССР, Советский союз
Альма-матерМосковский университет
Массачусетский Институт Технологий
Известенисследование сложности, случайности, информации
НаградыПриз Кнута (2012)
Научная карьера
ПоляИнформатика
УчрежденияБостонский университет
ДокторантАндрей Колмогоров, Альберт Р. Мейер

Леонид Анатольевич Левин (/лeɪ.oʊˈпяdˈлɛvɪп/ Lay-oh-НЕОБХОДИМОСТЬ LEV-в; русский: Леони́д Анато́льевич Ле́вин; украинец: Леоні́д Анато́лійович Ле́він; родился 2 ноября 1948 г.), американец советского происхождения. специалист в области информатики.

Он известен своей работой в случайность в вычисление, алгоритмическая сложность и несговорчивость, средняя сложность,[1] основы математика и Информатика, алгоритмическая вероятность, теория вычислений, и теория информации. Он получил степень магистра в Московский университет в 1970 году, где он учился Андрей Колмогоров и завершил Кандидатская степень академические требования в 1972 г.[2]

Он и Стивен Кук независимо обнаруженный Существование NP-полные задачи. Эта теорема NP-полноты, часто называемая Теорема Кука – Левина, послужила основой для одного из семи Задачи Премии тысячелетия объявленный Институт математики Клэя с предложенным призом в размере 1 000 000 долларов. Теорема Кука – Левина стала прорывом в Информатика и важный шаг в развитии теории вычислительная сложность.

Левин был награжден Приз Кнута в 2012[3] за открытие NP-полноты и развитие средняя сложность. Его жизнь описана в главе книги Не в их уме: жизни и открытия 15 великих ученых-компьютерщиков.[4]

биография

Он получил степень магистра в Московский университет в 1970 году, где он учился Андрей Колмогоров и завершил Кандидатская степень академические требования в 1972 г.[2][5] После исследований в области алгоритмических проблем теории информации в Московском институте передачи информации им. Национальная Академия Наук в 1972–1973 гг., а в 1973–1977 гг. - старший научный сотрудник Московского национального научно-исследовательского института комплексной автоматизации нефтегазовой промышленности, эмигрировал в НАС. в 1978 году и получил степень доктора философии. на Массачусетский Институт Технологий (Массачусетский технологический институт) в 1979 году.[2] Его советником в MIT был Альберт Р. Мейер.

Он хорошо известен своей работой в случайность в вычисление, алгоритмическая сложность и несговорчивость, средняя сложность,[1] основы математика и Информатика, алгоритмическая вероятность, теория вычислений, и теория информации.

Его жизнь описана в главе книги Не в их уме: жизни и открытия 15 великих ученых-компьютерщиков.[4]

Левин и Стивен Кук независимо обнаруженный Существование NP-полные задачи. Эта теорема NP-полноты, часто называемая Теорема Кука – Левина, был основой для одного из семи Задачи Премии тысячелетия объявленный Институт математики Клэя с предложенным призом в размере 1 000 000 долларов. Теорема Кука – Левина стала прорывом в Информатика и важный шаг в развитии теории вычислительная сложность. Журнальная статья Левина по этой теореме была опубликована в 1973 г .;[6] он читал лекции по содержащимся в ней идеям за несколько лет до того времени (см. Трахтенброт опрос),[7] хотя полное официальное написание результатов имело место после публикации Кука.

Левин был награжден Приз Кнута в 2012[3] за открытие NP-полноты и развитие средняя сложность.

В настоящее время он является профессором информатики в Бостонский университет, где начал преподавать в 1980 году.

Примечания

  1. ^ а б Левин, Леонид (1986). «Полные средние задачи». SIAM J. Comput. 15 (1): 285–6. Дои:10.1137/0215020.
  2. ^ а б c Биографические данные Левина
  3. ^ а б Пресс-релиз ACM, 22 августа 2012 г. В архиве 3 марта 2016 г. Wayback Machine
  4. ^ а б Шаша, Деннис; Кэти Лазер (сентябрь 1995 г.). Не в их уме: жизни и открытия 15 великих ученых-компьютерщиков. Springer. ISBN  0-387-97992-1.
  5. ^ 1971 г. (на русском); английский перевод в arXiv
  6. ^ Левин, Леонид (1973). «Универсальные задачи перебора, Универсальные переборные задачи». Проблемы передачи информации (Русский: Проблемы передачи информации, Проблемы передачи информации). 9 (3): 115–116. (pdf)
  7. ^ Борис Александрович Трахтенброт (1984). "Обзор российских подходов к алгоритмам перебора (перебора)". Анналы истории вычислительной техники. IEEE. 6 (4): 384–400. Дои:10.1109 / MAHC.1984.10036. S2CID  950581.

Рекомендации

внешняя ссылка