Меню Главная Случайная статья Настройки Карп, Ричард Мэннинг Материал из https://ru.wikipedia.org Ричард Мэннинг Карп (англ. Richard Manning Karp; род. 3 января 1935 года, Бостон, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга. Член Национальной академии наук США (1980)[4], Национальной инженерной академии США (1992)[5], иностранный член Французской академии наук (2002)[6]. Содержание 1 Биография 2 Вклад 3 Признание 4 Литература 5 См. также 6 Ссылки 7 Примечания Биография Ричард Карп родился в 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