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

(перенаправлено с «Ричард Карп»)

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

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

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

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

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

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

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

Национальная научная медаль США (1996)

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

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

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

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

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

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

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

премия Киото

фелло ACM[d] (1994)

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

Frederick W. Lanchester Prize[d] (1977)

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

Commons-logo.svg Медиафайлы на Викискладе

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

БиографияПравить

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

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

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

ВкладПравить

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

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

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

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

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

ПризнаниеПравить

ЛитератураПравить

См. такжеПравить

СсылкиПравить

ПримечанияПравить