WikiSort.ru - Не сортированное

Ричард Мэннинг Карп
Richard Manning Karp
Дата рождения	3 января 1935(1935-01-03)[1][2] (84 года)
Место рождения	Бостон, США[1]
Страна	США
Научная сфера	Теория вычислений, Биоинформатика
Место работы	Гарвардский университет
Альма-матер	Калифорнийский университет в Беркли
Научный руководитель	Энтони Оттингер
Известен как	Алгоритм Эдмондса-Карпа
Награды и премии	премия Тьюринга (1985) теоретическая премия фон Неймана (1990) медаль Столетия Высшей школы искусств и наук Гарвардского университета[d] премия Харви (1998) премия Фалкерсона (1979) Национальная научная медаль США (1996) премия Европейской ассоциации теоретической информатики[d] (2000) медаль Бенджамина Франклина[d] (2004) премия Киото в области передовых технологий[d] (2008) медаль Бенджамина Франклина (2004) премия Диксонов за значительный вклад в развитие науки[d] (2009) почётный доктор Техниона[d] почётный доктор Института Вейцмана[d] Fellow of the Association for Computing Machinery[d] (1994) премия Киото член ACM[d] SIAM Fellow[d] Frederick W. Lanchester Prize[d] (1977)
Сайт	eecs.berkeley.edu/~karp/
Ричард Мэннинг Карп на Викискладе

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

Биография

Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа (Abraham Louis Karp) и его жены Розы (Роуз) Карп в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид и младшая сестра Кэролин. Окончив школу, Ричард поступил в Гарвардский университет, где получил степени бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году.

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

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

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

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

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

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

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

Награды

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

Литература

• Р. Карп. = Complexity of Computation. — Американское математическое общество, 1974. — 166 с. — ISBN 978-0821813270.

См. также

• Алгоритм Эдмондса — Карпа
• Алгоритм Рабина — Карпа

Ссылки

• Сайт Ричарда Карпа при университете Беркли  (англ.)
• «A day in the life of Richard Karp», биография на сайте ACM
• Richard M. Karp (англ.). — Биография.
• Inamori Foundation (англ.) (недоступная ссылка). — Information Science. Архивировано 16 февраля 2013 года.

Примечания