Левин, Леонид Анатольевич

В Википедии есть статьи о других людях с такой фамилией, см. Левин (фамилия).

Леонид Анатольевич Левин
Дата рождения:	2 ноября 1948(1948-11-02) (64 года)
Место рождения:	Днепропетровск, Украинская ССР, СССР
Страна:	СССР  США
Научная сфера:	информатика
Место работы:	Бостонский университет
Учёная степень:	кандидат физико-математических наук (1972) доктор философии по математике (1979)
Альма-матер:	МГУ Массачусетский технологический институт
Научный руководитель:	А. Н. Колмогоров
Известен как:	один из авторов теоремы Кука — Левина
Сайт:	cs.bu.edu/~lnd/

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

Биография

Родился 2 ноября 1948 года в Днепропетровске. В 1970 году окончил Московский государственный университет, после чего работал там же на должности научного сотрудника под научным руководством А. Н. Колмогорова. В 1971 году представил кандидатскую диссертацию^[1], выполнив все формальные требования по её предварительному апробированию. Диссертация была одобрена А. Н. Колмогоровым, всеми оппонентами и головной организацией^[2], однако учёная степень Левину формально так присуждена и не была.

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

В 1978 году эмигрировал в США. В 1979 году получил диплом доктора философии по математике в Массачусетском технологическом институте. С 1980 года работает и преподаёт в Бостонском университете.

Широко известен своими научными достижениями в области теории вероятностей в применении к компьютерам, теории сложности вычислений, один из основателей таких научных направлений как информатика, теория вычислений, теория информации.

Независимо от Стивена Кука доказал в 1971 году теорему Кука — Левина, которая легла в основу одной из проблем тысячелетия, сформулированных институтом Клэя. Работа была опубликована только в 1973 году^[3], но была доложена на конференциях, что позже позволило установить приоритет Левина^[4].

Награды

• 2004 — Медаль Колмогорова, Лондонский университет^[5]
• 2010 — Исследовательская премия Гумбольдта (англ.)^[6]
• 2012 — Премия Кнута^[7][8]

Названы в его честь

• Теорема Кука — Левина

Примечания

1. ↑ Кандидатская диссертация Л. А. Левина
2. ↑ Отзывы на диссертацию Л. А. Левина
3. ↑ Л. А. Левин Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 1973. — Т. 9. — № 3. — С. 115—116.
4. ↑ Boris A. Trakhtenbrot A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms (англ.) // Annals of the History of Computing. — 1984. — Т. 6. — № 4. — С. 384—400.
5. ↑ Second Annual Kolmogorov Lecture (англ.)
6. ↑ Leonid Levin Wins Humboldt Research Award (англ.)
7. ↑ ACM press release, August 22, 2012
8. ↑ Премия Кнута 2012 присуждена Леониду Левину

Литература

• 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. Проверено 7 ноября 2012.
• Curriculum vitae  (англ.). Архивировано из первоисточника 8 мая 2012. Проверено 7 ноября 2012.
• Список публикаций  (англ.). Архивировано из первоисточника 6 декабря 2012. Проверено 7 ноября 2012.
• Диссертация А. Л. Левина
• Отзывы о диссертации Л. А. Левина