| Леонид Анатольевич Левин | |
|---|---|
 Леонид Левин в 2010 году | |
| Родившийся | 2 ноября 1948 г. |
| Альма-матер | Московский университет Массачусетский технологический институт |
| Известен | Теорема Кука – Левина. Средняя сложность. Исследование сложности, случайности, информации. |
| Награды | Приз Кнута (2012) |
| Научная карьера | |
| Поля | математика информатика |
| Учреждения | Бостонский университет |
| Докторант | Андрей Колмогоров , Альберт Р. Мейер |
Леонид Анатольевич Левин ( / л eɪ . Oʊ п я д л ɛ об ɪ н / лежал-OH- НЕОБХОДИМОСТЬ МВВ -в ; русском : Леонид Анатольевич Левин ; украинский : Леонід Анатолійович Левін ; родился 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 году и также получил степень доктора философии. в Массачусетском технологическом институте (MIT) в 1979 г. [2]Его советником в Массачусетском технологическом институте был Альберт Р. Мейер .
Он хорошо известен своими работами в области случайности в вычислениях , алгоритмической сложности и неразрешимости, средней сложности , [1] основ математики и информатики , алгоритмической вероятности , теории вычислений и теории информации .
Его жизнь описана в главе книги « Из их разума: жизни и открытия 15 великих ученых-компьютерщиков» . [4]
Левин и Стивен Кук независимо друг от друга обнаружили существование NP-полных проблем . Эта теорема о NP-полноте, часто называемая теоремой Кука – Левина , явилась основой для одной из семи проблем, связанных с Премией тысячелетия, объявленных Институтом математики Клэя с предложенной премией в размере 1 000 000 долларов. Теорема Кука – Левина явилась прорывом в информатике и важным шагом в развитии теории вычислительной сложности . Журнальная статья Левина по этой теореме была опубликована в 1973 г .; [6] он читал лекции по содержащимся в ней идеям за несколько лет до этого (см. Обзор Трахтенброта ),[7] хотя полное официальное написание результатов имело место после публикации Кука.
Левину была присуждена премия Кнута в 2012 году [3] за открытие NP-полноты и развитие средней сложности .
В настоящее время он является профессором информатики в Бостонском университете , где начал преподавать в 1980 году.
Заметки [ править ]
- ^ a b Левин, Леонид (1986). «Среднесписочные полные задачи» . SIAM J. Comput . 15 (1): 285–6. DOI : 10.1137 / 0215020 .
- ^ a b c Биографические данные Левина
- ^ a b Пресс-релиз ACM, 22 августа 2012 г. Архивировано 3 марта 2016 г., в Wayback Machine.
- ^ a b Шаша, Деннис; Кэти Лазер (сентябрь 1995 г.). Из их разума: жизни и открытия 15 великих ученых-компьютерщиков . Springer . ISBN 0-387-97992-1.
- ^ Диссертация 1971 ; Английский перевод в arXiv
- ^ Левин, Леонид (1973). «Универсальные поисковые задачи». Проблемы передачи информации . 9 (3): 115–116. (pdf)
- ↑ Борис А. Трахтенброт (1984). «Обзор российских подходов к алгоритмам перебора» . Анналы истории вычислительной техники . IEEE . 6 (4): 384–400. DOI : 10.1109 / MAHC.1984.10036 . S2CID 950581 .
Ссылки [ править ]
- "Леонид Александрович Левин" . Проект «Математическая генеалогия» .
Внешние ссылки [ править ]
 | Викискладе есть медиафайлы по теме Леонида Левина . |
- Домашняя страница Левина в Бостонском университете.
- Премия Кнута 2012 г. Леониду Левину
