Карп, Ричард Мэннинг

Ричард Мэннинг Карп (англ. Richard Manning Karp; род. 3 января 1935 года, Бостон, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.

В Википедии есть статьи о других людях с фамилией Карп.
Ричард Мэннинг Карп
англ. Richard Manning Karp
Дата рождения 3 января 1935(1935-01-03) (87 лет)
Место рождения
Страна
Научная сфера теория алгоритмов и биоинформатика
Место работы
Альма-матер
Научный руководитель Anthony Oettinger[d][1]
Награды и премии

премия Тьюринга (1985)

теоретическая премия фон Неймана (1990)

медаль Столетия Высшей школы искусств и наук Гарвардского университета[d]

премия Харви (1998)

премия Фалкерсона (1979)

премия Европейской ассоциации теоретической информатики[d] (2000)

медаль Бенджамина Франклина (2004)

премия Киото в области передовых технологий[d] (2008)

медаль Бенджамина Франклина (2004)

премия Диксонов за значительный вклад в развитие науки[d] (2009)

почётный доктор Техниона[d]

почётный доктор Института Вейцмана[d]

премия Киото

Фелло ACM (1994)

Fellow of the Society for Industrial and Applied Mathematics[d] (2009)

Frederick W. Lanchester Prize[d] (1977)

почётный доктор Швейцарской высшей технической школы Цюриха[d]
 Медиафайлы на Викискладе

Член Национальной академии наук США (1980)[2], Национальной инженерной академии США (1992)[3], иностранный член Французской академии наук (2002)[4].

Биография

Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа (1908—1981) и его жены Розы (Роуз) Карп (1912—2000), из семей еврейских иммигрантов из России[5], в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид (род. 1944, социолог) и младшая сестра Кэролин.

Окончив школу, Ричард поступил в Гарвардский университет, где получил степени бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году.

После учёбы Ричард Карп работал 9 лет в исследовательском центре IBM (Исследовательский центр Томаса Вотсона). В 1968 году он получил профессуру по информатике, математике и исследованию операций в калифорнийском университете Беркли, где и работает по сей день, не считая четырёхлетнего перерыва на работу в Вашингтонском университете (в Сиэтле).

Вклад

В 1971 году Карп вместе с Джеком Эдмондсом разработал алгоритм для нахождения максимального потока в транспортной сети, названный в их честь. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems»,[6] в котором он доказал NP-полноту для 21 задачи.

В 1973 году Карп и Джон Хопкрофт опубликовали алгоритм Хопкрофта — Карпа, который является самым быстрым известным методом для нахождения максимальных соответствий количества элементов в двудольных графах[7].

В 1980 году, вместе с Ричардом Дж. Липтоном, Карп доказал теорему Карпа — Липтона.

В 1987 году, вместе с Майклом Рабином, Карп разработал алгоритм поиска подстроки, названный в их честь[7].

Ричард Карп сделал много других важных открытий в информатике и исследовании операций в области комбинаторных алгоритмов. На сегодняшний день он занимается исследованиями в биоинформатике[7].

Признание

Литература

См. также

Ссылки

Примечания
  1. Математическая генеалогия (англ.) — 1997.
  2. Карп, Ричард Мэннинг на сайте Национальной академии наук США  (англ.)
  3. Dr. Richard M. Karp (англ.)
  4. Richard Karp (фр.)
  5. Семья матери происходила из местечка Эйшишки Гродненской губернии.
  6. «Reducibility Among Combinatorial Problems» Архивная копия от 29 июня 2011 на Wayback Machine, Р. Карп, 1972 год (англ.)
  7. Richard M. Karp (англ.). — Биография.
  8. Statistics — Most Cited Authors in Computer Science
  9. Richard M. Karp — The Franklin Institute Awards — Laureate Database Архивная копия от 1 июня 2010 на Wayback Machine
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.