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

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

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

Биография

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

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

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

Вклад

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

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

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

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

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

Признание

Литература

См. также

Ссылки

  • от 19 декабря 2016 на Wayback Machine при университете Беркли (англ.)
  • , биография на сайте ACM
  • (англ.) . — Биография. Дата обращения: 8 декабря 2014. 19 февраля 2015 года.
  • (англ.) . — Information Science. Архивировано из 16 февраля 2013 года.

Примечания

  1. Deutsche Nationalbibliothek Record #170367800 // (нем.) — 2012—2016.
  2. Richard M. Karp // (англ.) — 2010.
  3. (англ.) — 1997.
  4. на сайте Национальной академии наук США (англ.)
  5. от 2 мая 2019 на Wayback Machine (англ.)
  6. от 8 сентября 2019 на Wayback Machine (фр.)
  7. Семья матери происходила из местечка Эйшишки Гродненской губернии .
  8. от 29 июня 2011 на Wayback Machine , Р. Карп, 1972 год (англ.)
  9. (англ.) . — Биография. Дата обращения: 8 декабря 2014. 19 февраля 2015 года.
  10. . Дата обращения: 27 февраля 2009. 1 мая 2012 года.
  11. от 1 июня 2010 на Wayback Machine
Источник —

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