Леонид Левин
Леонид Анатольевич Левин | |
|---|---|
 Леонид Левин в 2010 году | |
| Рожденный | 2 ноября 1948 г. |
| Альма-матер | Московский университет Массачусетский технологический институт |
| Известный | Теорема Кука – Левина Средняя сложность Исследования сложности, случайности, информации |
| Награды | Премия Кнута (2012) |
| Научная карьера | |
| Поля | Математика Информатика |
| Учреждения | Бостонский университет |
| Докторантура | Андрей Колмогоров , Альберт Р. Мейер |
Anatolievich Levin / l eɪ . oʊ ˈ n iː d ˈ l ɛ ɪ v n / lay -oh- LEV -in ; Russian : Леонид Анатольевич ; ( NEED Ле́вин Leonid -Американский математический и компьютерный ученый .
Он известен своими работами в области случайности в вычислениях , алгоритмической сложности и трудноразрешимости, сложности среднего случая . [1] основы математики и информатики , алгоритмическая вероятность , теория вычислений и теория информации . В 1970 году он получил степень магистра в Московском университете , где учился у Андрея Колмогорова , а в 1972 году получил академическую степень кандидата наук . [2]
Он и Стивен Кук независимо друг от друга обнаружили существование NP-полных задач . Эта теорема NP-полноты, часто называемая теоремой Кука-Левина , легла в основу одной из семи задач Премии тысячелетия, объявленных Математическим институтом Клея с предложенной премией в 1 000 000 долларов. Теорема Кука-Левина стала прорывом в информатике и важным шагом в развитии теории сложности вычислений .
Левин был удостоен премии Кнута в 2012 году. [3] за открытие NP-полноты и развитие сложности в среднем .Он является членом Национальной академии наук США ичлен Американской академии искусств и наук .
Биография [ править ]
В 1970 году он получил степень магистра в Московском университете , где учился у Андрея Колмогорова , а в 1972 году получил академическую степень кандидата наук . [2] [4] После исследования алгоритмических задач теории информации в Московском институте передачи информации Национальной академии наук в 1972–1973 годах и должности старшего научного сотрудника Московского национального научно-исследовательского института комплексной автоматизации нефтяной и газовой промышленности в 1973– В 1977 году он эмигрировал в США , в 1978 году также получил степень доктора философии. в Массачусетском технологическом институте (MIT) в 1979 году. [2] Его советником в Массачусетском технологическом институте был Альберт Р. Мейер .
Он хорошо известен своими работами в области случайности в вычислениях , алгоритмической сложности и трудноразрешимости, сложности среднего случая . [1] основы математики и информатики , алгоритмическая вероятность , теория вычислений и теория информации .
Его жизнь описана в главе книги « Вне их разума: жизнь и открытия 15 великих ученых-компьютерщиков» . [5]
Левин и Стивен Кук независимо друг от друга обнаружили существование NP-полных задач . Эта теорема NP-полноты, часто называемая теоремой Кука-Левина , легла в основу одной из семи задач Премии тысячелетия, объявленных Математическим институтом Клея с предложенной премией в 1 000 000 долларов. Теорема Кука-Левина стала прорывом в информатике и важным шагом в развитии теории сложности вычислений . Журнальная статья Левина по этой теореме была опубликована в 1973 году; [6] до этого он несколько лет читал лекции по изложенным в нем идеям (см. , обзор Трахтенброта) [7] хотя полная формальная запись результатов произошла после публикации Кука.
Левин был удостоен премии Кнута в 2012 году. [3] за открытие NP-полноты и развитие сложности в среднем .
В настоящее время он является профессором информатики в Бостонском университете , где начал преподавать в 1980 году.
Примечания [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Левин, Леонид (1986). «Полные задачи в среднем случае» . СИАМ Дж. Компьютер . 15 (1): 285–6. дои : 10.1137/0215020 .
- ↑ Перейти обратно: Перейти обратно: а б с Карьера Левина
- ↑ Перейти обратно: Перейти обратно: а б Пресс-релиз ACM, 22 августа 2012 г. Архивировано 3 марта 2016 г. в Wayback Machine.
- ^ Диссертация 1971 г. (на русском языке); Английский перевод на arXiv
- ^ Шаша, Деннис; Кэти Лазер (сентябрь 1995 г.). Они сошли с ума: жизнь и открытия 15 великих ученых-компьютерщиков . Спрингер . ISBN 0-387-97992-1 .
- ^ Levin, Leonid (1973). "Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii) . 9 (3): 115–116. (pdf)
- ^ Борис А. Трахтенброт (1984). «Обзор российских подходов к алгоритмам перебора (перебора)» . Анналы истории вычислительной техники . 6 (4). IEEE : 384–400. дои : 10.1109/MAHC.1984.10036 . S2CID 950581 .
Ссылки [ править ]
- "Леонид Алексеевич Левин" . Проект математической генеалогии .
Внешние ссылки [ править ]
- Домашняя страница Левина в Бостонском университете.
- Премия Кнута 2012 Леониду Левину
- 1948 рождений
- Живые люди
- Ученые из Днепра
- Выпускники Массачусетского технологического института
- Выпускники МГУ
- Американские ученые-компьютерщики
- Американский народ украинско-еврейского происхождения
- Американские математики XX века
- Американские математики XXI века
- Преподаватели Бостонского университета
- Российские теоретики информации
- Российские ученые-компьютерщики
- Российские математики
- советские ученые-компьютерщики
- Советские математики
- Советские эмигранты в США
- Американские теоретики информации
- Российские политики XXI века
- Лауреаты премии Кнута
- Украинские математики XXI века
- Украинские евреи
- Российские учёные
- Лауреаты премии Гумбольдта за исследования