Карп, Ричард Мэннинг (Tgjh, Jncgj; Bzuunui)
Ричард Мэннинг Карп (англ. 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].
Признание
[править | править код]- В конце февраля 2009 года Карп занимал 35 место в списке самых цитируемых авторов в проекте CiteSeer.[10]
- 1977 — Премия Фредерика Ланчестера[англ.], ORSA
- 1979 — Премия Фалкерсона, Американское математическое общество
- 1985 — Премия Тьюринга «за его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты.»
- 1987 — Лекция Джона фон Неймана
- 1990 — Теоретическая премия фон Неймана, ORSA
- 1994 — почётное членство ACM
- 1995 — Премия имени Чарльза Беббиджа
- 1996 — Национальная научная медаль США
- 1998 — Премия Харви, Израильский технологический институт
- 2004 — Медаль Бенджамина Франклина[11]
- 2008 — Премия Киото
- 2008 — Премия Диксона
Литература
[править | править код]- Р. Карп. = Complexity of Computation. — Американское математическое общество, 1974. — 166 с. — ISBN 978-0821813270.
См. также
[править | править код]Ссылки
[править | править код]- Сайт Ричарда Карпа Архивная копия от 19 декабря 2016 на Wayback Machine при университете Беркли (англ.)
- «A day in the life of Richard Karp», биография на сайте ACM
- Richard M. Karp (англ.). — Биография. Дата обращения: 8 декабря 2014. Архивировано 19 февраля 2015 года.
- Inamori Foundation (англ.). — Information Science. Архивировано из оригинала 16 февраля 2013 года.
Примечания
[править | править код]- ↑ 1 2 Deutsche Nationalbibliothek Record #170367800 // Gemeinsame Normdatei (нем.) — 2012—2016.
- ↑ Richard M. Karp // SNAC (англ.) — 2010.
- ↑ Mathematics Genealogy Project (англ.) — 1997.
- ↑ Карп, Ричард Мэннинг на сайте Национальной академии наук США (англ.)
- ↑ Dr. Richard M. Karp Архивная копия от 2 мая 2019 на Wayback Machine (англ.)
- ↑ Richard Karp Архивная копия от 8 сентября 2019 на Wayback Machine (фр.)
- ↑ Семья матери происходила из местечка Эйшишки Гродненской губернии.
- ↑ «Reducibility Among Combinatorial Problems» Архивная копия от 29 июня 2011 на Wayback Machine, Р. Карп, 1972 год (англ.)
- ↑ 1 2 3 Richard M. Karp (англ.). — Биография. Дата обращения: 8 декабря 2014. Архивировано 19 февраля 2015 года.
- ↑ Statistics — Most Cited Authors in Computer Science. Дата обращения: 27 февраля 2009. Архивировано 1 мая 2012 года.
- ↑ Richard M. Karp — The Franklin Institute Awards — Laureate Database Архивная копия от 1 июня 2010 на Wayback Machine
 | ||||
|---|---|---|---|---|
| Словари и энциклопедии | ||||
Лауреаты премии Тьюринга | |
|---|---|
| |
- Родившиеся 3 января
- Родившиеся в 1935 году
- Родившиеся в Бостоне
- Преподаватели Калифорнийского университета в Беркли
- Преподаватели Вашингтонского университета
- Выпускники Гарвардского университета
- Выпускники Гарвардской школы инженерных и прикладных наук
- Выпускники Калифорнийского университета в Беркли
- Лауреаты премии Тьюринга
- Лауреаты премии Харви
- Лауреаты премии Фалкерсона
- Награждённые Национальной медалью науки США
- Награждённые медалью Бенджамина Франклина (Королевское общество искусств)
- Награждённые медалью Бенджамина Франклина (Институт Франклина)
- Почётные доктора Института Вейцмана
- Действительные члены Ассоциации вычислительной техники
- Действительные члены Общества промышленной и прикладной математики
- Почётные доктора ETH Zurich
- Персоналии по алфавиту
- Учёные по алфавиту
- Преподаватели Инженерного колледжа Калифорнийского университета в Беркли
- Учёные в области информатики США
- Математики США
- Члены Национальной академии наук США
- Члены Национальной инженерной академии США
- Члены Американского философского общества
- Иностранные члены Французской академии наук
- Лауреаты премии Диксона
- Почётные доктора Джорджтаунского университета
- Почётные доктора Пенсильванского университета
- Почётные доктора Карлтонского университета
- Почётные доктора Техниона