Ричард Мэннинг Карп (; род. 3 января 1935 года, Бостон, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.
Член Национальной академии наук США (1980), Национальной инженерной академии США (1992)Dr. Richard M. Karp , иностранный член Французской академии наук (2002)Richard Karp .
Биография Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа (1908—1981) и его жены Розы (Роуз) Карп (1912—2000), из семей еврейских иммигрантов из РоссииСемья матери происходила из местечка Эйшишки Гродненской губернии., в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид (род. 1944, социолог) и младшая сестра Кэролин.
Окончив школу, Ричард поступил в Гарвардский университет, где получил степени бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году.
После учёбы Ричард Карп работал 9 лет в исследовательском центре IBM (). В 1968 году он получил профессуру по информатике, математике и исследованию операций в калифорнийском университете Беркли, где и работает по сей день, не считая четырёхлетнего перерыва на работу в Вашингтонском университете (в Сиэтле).
Вклад В 1971 году Карп вместе с разработал алгоритм для нахождения максимального потока в транспортной сети, названный в их честь. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems»,«Reducibility Among Combinatorial Problems» , Р. Карп, 1972 год в котором он доказал NP-полноту для 21 задачи.
В 1973 году Карп и Джон Хопкрофт опубликовали алгоритм Хопкрофта — Карпа, который является самым быстрым известным методом для нахождения максимальных соответствий количества элементов в двудольных графах.
В 1980 году, вместе с Ричардом Дж. Липтоном, Карп доказал .
В 1987 году, вместе с Майклом Рабином, Карп разработал алгоритм поиска подстроки, названный в их честь.
Ричард Карп сделал много других важных открытий в информатике и исследовании операций в области комбинаторных алгоритмов. На сегодняшний день он занимается исследованиями в биоинформатике.
Признание В конце февраля 2009 года Карп занимал 35 место в списке самых цитируемых авторов в проекте CiteSeer. 1977 — , 1979 — Премия Фалкерсона, Американское математическое общество 1985 — Премия Тьюринга «за его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты.» 1987 — Лекция Джона фон Неймана 1990 — Теоретическая премия фон Неймана, 1994 — почётное членство ACM 1995 — Премия имени Чарльза Беббиджа 1996 — Национальная научная медаль США 1998 — Премия Харви, Израильский технологический институт 2004 — Медаль Бенджамина ФранклинаRichard M. Karp — The Franklin Institute Awards — Laureate Database 2008 — Премия Киото 2008 — Премия Диксона
Литература
См. также Алгоритм Эдмондса — Карпа Алгоритм Рабина — Карпа
Примечания
Ссылки Сайт Ричарда Карпа при университете Беркли «A day in the life of Richard Karp», биография на сайте ACM
Категория:Преподаватели Калифорнийского университета в Беркли Категория:Преподаватели Инженерного колледжа Калифорнийского университета в Беркли Категория:Учёные в области информатики США Категория:Математики США Категория:Члены Национальной академии наук США Категория:Члены Национальной инженерной академии США Категория:Члены Американского философского общества Категория:Иностранные члены Французской академии наук Категория:Лауреаты премии Диксона Категория:Почётные доктора Джорджтаунского университета Категория:Почётные доктора Пенсильванского университета Категория:Почётные доктора Карлтонского университета Категория:Почётные доктора Техниона Категория:Лауреаты премии Киото