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

Поделись знанием:
(перенаправлено с «Л. А. Левин»)
Перейти к: навигация, поиск
Леонид Анатольевич Левин
Дата рождения:

2 ноября 1948(1948-11-02) (75 лет)

Место рождения:

Днепропетровск, Украинская ССР, СССР

Страна:

СССР, США

Научная сфера:

информатика

Место работы:

Бостонский университет

Учёная степень:

кандидат физико-математических наук (1972)
доктор философии по математике (1979)

Альма-матер:

МГУ (мехмат)
Массачусетский технологический институт

Научный руководитель:

А. Н. Колмогоров
en:Albert R. Meyer

Известен как:

один из авторов теоремы Кука — Левина

Сайт:

[www.cs.bu.edu/~lnd/ bu.edu/~lnd/]

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





Биография

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

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

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

Основные результаты — в области теории вероятностей в применении к информатике, теории сложности вычислений.

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

Награды

Напишите отзыв о статье "Левин, Леонид Анатольевич"

Примечания

  1. [www.cs.bu.edu/fac/lnd/dvi/diss/1-dis.pdf Кандидатская диссертация Л. А. Левина]
  2. [www.cs.bu.edu/fac/lnd/dvi/diss/3-rev.pdf Отзывы на диссертацию Л. А. Левина]
  3. [www.computer-museum.ru/books/n_ershov/3_ershov_trahtenbrot.htm Б. А. Трахтенброт. Памяти Андрея Петровича Ершова]
  4. [a-shen.livejournal.com/42003.html Интервью с Леонидом Левиным]
  5. [trv-science.ru/2012/11/20/premiya-po-informatike-dlya-vykhodca-iz-sssr/ Кутателадзе С. Премия по информатике для выходца из СССР] // Троицкий вариант — Наука. № 23 (117) от 20 ноября 2012. С. 14.
  6. [www.amacad.org/multimedia/pdfs/classlist2014.pdf The New 2014 Academy Members]
  7. Л. А. Левин [www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=914&option_lang=rus Универсальные задачи перебора] (рус.) // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116.
  8. 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.
  9. [www.clrc.rhul.ac.uk/events/kl2004.html Second Annual Kolmogorov Lecture] (англ.)
  10. [www.bu.edu/today/node/11064 Leonid Levin Wins Humboldt Research Award] (англ.)
  11. [www.acm.org/press-room/news-releases/2012/sigact-knuth-prize-2012 ACM press release, August 22, 2012]
  12. [www.math.nsc.ru/LBRT/g2/english/ssk/levin.html Премия Кнута 2012 присуждена Леониду Левину]

Литература

  • Dennis Elliott Shasha, Cathy A. Lazere. Stephen Cook and Leonid Levin: A good solution is hard to find // [books.google.com/books?id=-0tDZX3z-8UC&pg=PA139 Out of their minds: the lives and discoveries of 15 great computer scientists]. — Springer, 1998. — С. 139—156. — 291 с. — (Copernicus Series). — ISBN 0387982698.

Ссылки

  • [www.cs.bu.edu/~lnd/ Персональная страница на сайте Бостонского университета] (англ.). Проверено 7 ноября 2012. [www.webcitation.org/67VwV9Y8j Архивировано из первоисточника 8 мая 2012].
  • [www.cs.bu.edu/fac/lnd/research/cv.htm Curriculum vitae] (англ.). Проверено 7 ноября 2012. [www.webcitation.org/67VwVgEDp Архивировано из первоисточника 8 мая 2012].
  • [scholar.google.com/citations?user=qe_J1w4AAAAJ Список публикаций] (англ.). Проверено 7 ноября 2012. [www.webcitation.org/6ChWADYso Архивировано из первоисточника 6 декабря 2012].
  • [www.cs.bu.edu/fac/lnd/dvi/diss/1-dis.pdf Диссертация А. Л. Левина]
  • [www.cs.bu.edu/fac/lnd/dvi/diss/3-rev.pdf Отзывы о диссертации Л. А. Левина]

Отрывок, характеризующий Левин, Леонид Анатольевич

С той минуты, как Пьер увидал это страшное убийство, совершенное людьми, не хотевшими этого делать, в душе его как будто вдруг выдернута была та пружина, на которой все держалось и представлялось живым, и все завалилось в кучу бессмысленного сора. В нем, хотя он и не отдавал себе отчета, уничтожилась вера и в благоустройство мира, и в человеческую, и в свою душу, и в бога. Это состояние было испытываемо Пьером прежде, но никогда с такою силой, как теперь. Прежде, когда на Пьера находили такого рода сомнения, – сомнения эти имели источником собственную вину. И в самой глубине души Пьер тогда чувствовал, что от того отчаяния и тех сомнений было спасение в самом себе. Но теперь он чувствовал, что не его вина была причиной того, что мир завалился в его глазах и остались одни бессмысленные развалины. Он чувствовал, что возвратиться к вере в жизнь – не в его власти.
Вокруг него в темноте стояли люди: верно, что то их очень занимало в нем. Ему рассказывали что то, расспрашивали о чем то, потом повели куда то, и он, наконец, очутился в углу балагана рядом с какими то людьми, переговаривавшимися с разных сторон, смеявшимися.
– И вот, братцы мои… тот самый принц, который (с особенным ударением на слове который)… – говорил чей то голос в противуположном углу балагана.
Молча и неподвижно сидя у стены на соломе, Пьер то открывал, то закрывал глаза. Но только что он закрывал глаза, он видел пред собой то же страшное, в особенности страшное своей простотой, лицо фабричного и еще более страшные своим беспокойством лица невольных убийц. И он опять открывал глаза и бессмысленно смотрел в темноте вокруг себя.
Рядом с ним сидел, согнувшись, какой то маленький человек, присутствие которого Пьер заметил сначала по крепкому запаху пота, который отделялся от него при всяком его движении. Человек этот что то делал в темноте с своими ногами, и, несмотря на то, что Пьер не видал его лица, он чувствовал, что человек этот беспрестанно взглядывал на него. Присмотревшись в темноте, Пьер понял, что человек этот разувался. И то, каким образом он это делал, заинтересовало Пьера.
Размотав бечевки, которыми была завязана одна нога, он аккуратно свернул бечевки и тотчас принялся за другую ногу, взглядывая на Пьера. Пока одна рука вешала бечевку, другая уже принималась разматывать другую ногу. Таким образом аккуратно, круглыми, спорыми, без замедления следовавшими одно за другим движеньями, разувшись, человек развесил свою обувь на колышки, вбитые у него над головами, достал ножик, обрезал что то, сложил ножик, положил под изголовье и, получше усевшись, обнял свои поднятые колени обеими руками и прямо уставился на Пьера. Пьеру чувствовалось что то приятное, успокоительное и круглое в этих спорых движениях, в этом благоустроенном в углу его хозяйстве, в запахе даже этого человека, и он, не спуская глаз, смотрел на него.
– А много вы нужды увидали, барин? А? – сказал вдруг маленький человек. И такое выражение ласки и простоты было в певучем голосе человека, что Пьер хотел отвечать, но у него задрожала челюсть, и он почувствовал слезы. Маленький человек в ту же секунду, не давая Пьеру времени выказать свое смущение, заговорил тем же приятным голосом.
– Э, соколик, не тужи, – сказал он с той нежно певучей лаской, с которой говорят старые русские бабы. – Не тужи, дружок: час терпеть, а век жить! Вот так то, милый мой. А живем тут, слава богу, обиды нет. Тоже люди и худые и добрые есть, – сказал он и, еще говоря, гибким движением перегнулся на колени, встал и, прокашливаясь, пошел куда то.
– Ишь, шельма, пришла! – услыхал Пьер в конце балагана тот же ласковый голос. – Пришла шельма, помнит! Ну, ну, буде. – И солдат, отталкивая от себя собачонку, прыгавшую к нему, вернулся к своему месту и сел. В руках у него было что то завернуто в тряпке.
– Вот, покушайте, барин, – сказал он, опять возвращаясь к прежнему почтительному тону и развертывая и подавая Пьеру несколько печеных картошек. – В обеде похлебка была. А картошки важнеющие!
Пьер не ел целый день, и запах картофеля показался ему необыкновенно приятным. Он поблагодарил солдата и стал есть.
– Что ж, так то? – улыбаясь, сказал солдат и взял одну из картошек. – А ты вот как. – Он достал опять складной ножик, разрезал на своей ладони картошку на равные две половины, посыпал соли из тряпки и поднес Пьеру.
– Картошки важнеющие, – повторил он. – Ты покушай вот так то.
Пьеру казалось, что он никогда не ел кушанья вкуснее этого.
– Нет, мне все ничего, – сказал Пьер, – но за что они расстреляли этих несчастных!.. Последний лет двадцати.
– Тц, тц… – сказал маленький человек. – Греха то, греха то… – быстро прибавил он, и, как будто слова его всегда были готовы во рту его и нечаянно вылетали из него, он продолжал: – Что ж это, барин, вы так в Москве то остались?
– Я не думал, что они так скоро придут. Я нечаянно остался, – сказал Пьер.
– Да как же они взяли тебя, соколик, из дома твоего?
– Нет, я пошел на пожар, и тут они схватили меня, судили за поджигателя.
– Где суд, там и неправда, – вставил маленький человек.
– А ты давно здесь? – спросил Пьер, дожевывая последнюю картошку.