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 году , вместе с Майклом Рабином , Карп разработал алгоритм поиска подстроки , названный в их честь .

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