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

Ричард Карп

Richard M. Karp

 

Дата рождения

3 января 1935 года

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

Бостон, США

Ричард Мэннинг Карп (англ. Richard Manning Karp) — американский учёный в области теории вычислительных систем.

Научная карьера

Родился 3 января 1935 года в Бостоне в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа и Розы Карп.

В 1955 году получил степень бакалавра, в 1956 году — степень магистра наук, а в 1959 году — степень доктора философии по прикладной математике в в Гарвардском университете.

Затем 9 лет работал в исследовательском центре IBM (Thomas J. Watson Research Center).

В 1968 году получил профессуру по информатике, математике и исследованию операций при калифорнийском университете Беркли.

4 года работал в университете Вашингтона.

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

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

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

В 1987 году вместе с Майклом Ошером Рабином разработал алгоритм поиска подстроки, названный Алгоритмом Рабина — Карпа.

В конце февраля 2009 года занимал 35 место в списке самых цитируемых авторов в проекте CiteSeer.

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

Награды: в 1977 году — Премия Ланчестера, в 1979 году — Премия Фалкерсона, Американское математическое общество, в 1985 году — Премия Тьюринга «за его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты.», в 1990 году — Теоретическая премия фон Неймана, ORSA, в 1994 году — почётное членство ACM, в 1995 году — Премия имени Чарльза Беббиджа, в 1996 году — Национальная научная медаль США, в 1998 году — Премия Харви, Технион, в 2004 году — Медаль Бенджамина Франклина, в 2008 году — Премия Киото, в 2008 году — Премия Диксона.