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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Ричард Мэннинг Карп
англ. Richard Manning Karp
Karp mg 7725-b.cr2.jpg
Дата рождения 3 января 1935(1935-01-03) (87 лет)
Место рождения
Страна
Научная сфера теория алгоритмов и биоинформатика
Место работы
Альма-матер
Научный руководитель Anthony Oettinger[d][1]
Награды и премии
премия Тьюринга (1985) теоретическая премия фон Неймана (1990) медаль Столетия Высшей школы искусств и наук Гарвардского университета[d] премия Харви (1998) премия Фалкерсона (1979) Национальная научная медаль США премия Европейской ассоциации теоретической информатики[d] (2000) медаль Бенджамина Франклина[d] (2004) премия Киото в области передовых технологий[d] (2008) медаль Бенджамина Франклина (2004) премия Диксонов за значительный вклад в развитие науки[d] (2009) почётный доктор Техниона[d] почётный доктор Института Вейцмана[d] премия Киото Фелло ACM (1994) член Общества промышленной и прикладной математики[d] (2009) Frederick W. Lanchester Prize[d] (1977) почётный доктор Швейцарской высшей технической школы Цюриха[d]
Логотип Викисклада Медиафайлы на Викискладе

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

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

Биография[править | править код]

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

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

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

Вклад[править | править код]

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

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

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

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

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

Признание[править | править код]

Литература[править | править код]

См. также[править | править код]

Ссылки[править | править код]

Примечания[править | править код]

  1. Математическая генеалогия (англ.) — 1997.
  2. Карп, Ричард Мэннинг на сайте Национальной академии наук США  (англ.)
  3. Dr. Richard M. Karp Архивная копия от 2 мая 2019 на Wayback Machine (англ.)
  4. Richard Karp Архивная копия от 8 сентября 2019 на Wayback Machine (фр.)
  5. Семья матери происходила из местечка Эйшишки Гродненской губернии.
  6. «Reducibility Among Combinatorial Problems» Архивная копия от 29 июня 2011 на Wayback Machine, Р. Карп, 1972 год (англ.)
  7. 1 2 3 Richard M. Karp (англ.). — Биография. Дата обращения: 8 декабря 2014. Архивировано 19 февраля 2015 года.
  8. Statistics — Most Cited Authors in Computer Science. Дата обращения: 27 февраля 2009. Архивировано 1 мая 2012 года.
  9. Richard M. Karp — The Franklin Institute Awards — Laureate Database Архивная копия от 1 июня 2010 на Wayback Machine