Loading AI tools
американский учёный в области теории вычислительных систем Из Википедии, свободной энциклопедии
Ричард Мэннинг Карп (англ. Richard Manning Karp; род. 3 января 1935 года, Бостон, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.
Член Национальной академии наук США (1980)[4], Национальной инженерной академии США (1992)[5], иностранный член Французской академии наук (2002)[6].
Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа (1908—1981) и его жены Розы (Роуз) Карп (1912—2000), из семей еврейских иммигрантов из России[7], в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид (род. 1944, социолог) и младшая сестра Кэролин.
Окончив школу, Ричард поступил в Гарвардский университет, где получил степени бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году.
После учёбы Ричард Карп работал 9 лет в исследовательском центре IBM (Исследовательский центр Томаса Вотсона[англ.]). В 1968 году он получил профессуру по информатике, математике и исследованию операций в калифорнийском университете Беркли, где и работает по сей день, не считая четырёхлетнего перерыва на работу в Вашингтонском университете (в Сиэтле).
В 1971 году Карп вместе с Джеком Эдмондсом[англ.] разработал алгоритм для нахождения максимального потока в транспортной сети, названный в их честь. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems»,[8] в котором он доказал NP-полноту для 21 задачи.
В 1973 году Карп и Джон Хопкрофт опубликовали алгоритм Хопкрофта — Карпа, который является самым быстрым известным методом для нахождения максимальных соответствий количества элементов в двудольных графах[9].
В 1980 году, вместе с Ричардом Дж. Липтоном, Карп доказал теорему Карпа — Липтона[англ.].
В 1987 году, вместе с Майклом Рабином, Карп разработал алгоритм поиска подстроки, названный в их честь[9].
Ричард Карп сделал много других важных открытий в информатике и исследовании операций в области комбинаторных алгоритмов. На сегодняшний день он занимается исследованиями в биоинформатике[9].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.