Ричард М. Карп

Ричард Мэннинг Карп
Ричард Карп в EPFL в 2009 году
Рожденный	( 1935-01-03 )3 января 1935 г. (89 лет) Бостон, Массачусетс , США
Национальность	американский
Альма-матер	Гарвардский университет ( бакалавр , магистр , доктор философии )
Известный	Гипотеза Аандеры–Карпа–Розенберга Алгоритм Эдмондса–Карпа Алгоритм Хельда–Карпа Алгоритм Хопкрофта–Карпа Алгоритм Кармаркара–Карпа Алгоритм поиска строки Рабина–Карпа Теорема Карпа–Липтона 21 NP-полная задача Карпа Система сложения векторов
Награды	Премия Фулкерсона (1979) Премия Тьюринга (1985) Премия Джона фон Неймана за теорию (1990) Премия Чарльза Бэббиджа IEEE Computer Society (1995) Национальная медаль науки (1996) Премия Харви (1998) Премия EATCS (2000) Медаль Бенджамина Франклина (2004) Премия Киото (2008)
Научная карьера
Поля	Информатика
Учреждения	Калифорнийский университет в Беркли IBM
Тезис	Некоторые приложения логического синтаксиса к программированию цифровых компьютеров  (1959)
научный руководитель	Энтони Эттингер [1]
Докторанты	Фейт Эллен Салли Флойд Филлип Гиббонс Дэн Гасфилд Нарендра Кармаркар Валери Кинг Майкл Луби Раджив Мотвани Ноам Нисан Раймонд Рейтер Юнис Сантос Томас Дж. Шефер Рон Шамир Барбара Саймонс Эрик Син Норман Заде [1]

Ричард Мэннинг Карп (родился 3 января 1935 года) — американский учёный-компьютерщик и теоретик вычислений в Калифорнийском университете в Беркли . Он наиболее известен своими исследованиями в области теории алгоритмов , за которые он получил премию Тьюринга в 1985 году, медаль Бенджамина Франклина в области компьютерных и когнитивных наук в 2004 году и премию Киото в 2008 году ^{. [2]}

Карп был избран членом Национальной инженерной академии (1992) за большой вклад в теорию и применение NP-полноты, построение эффективных комбинаторных алгоритмов и применение вероятностных методов в информатике.

Родился в Бостоне, штат Массачусетс , у родителей Авраама и Роуз Карп , у Карпа есть трое младших братьев и сестер: Роберт, Дэвид и Кэролин. Его семья была еврейской , ^[3] и он вырос в маленькой квартире, в тогдашнем преимущественно еврейском районе Дорчестер в Бостоне.

Оба его родителя были выпускниками Гарварда (его мать в конечном итоге получила степень Гарварда в возрасте 57 лет после окончания вечерних курсов), в то время как его отец имел амбиции поступить в медицинскую школу после Гарварда, но стал учителем математики, так как не мог позволить себе плату за обучение. ^[3] Он учился в Гарвардском университете , где получил степень бакалавра в 1955 году, степень магистра в 1956 году и степень доктора философии по прикладной математике в 1959 году. Он начал работать в исследовательском центре Томаса Дж. Уотсона компании IBM .

В 1968 году он стал профессором компьютерных наук, математики и исследования операций в Калифорнийском университете в Беркли . Карп был первым ассоциированным заведующим кафедрой компьютерных наук в составе кафедры электротехники и компьютерных наук. ^[4] За исключением 4-летнего периода работы профессором в Вашингтонском университете , он оставался в Беркли. С 1988 по 1995 и с 1999 года по настоящее время он также был научным сотрудником в Международном институте компьютерных наук в Беркли, где в настоящее время возглавляет группу алгоритмов.

Ричард Карп был награжден Национальной медалью науки , а также был удостоен премии Харви Техниона и медали Бенджамина Франклина 2004 года в области компьютерных и когнитивных наук за свои идеи в области вычислительной сложности . В 1994 году он был введен в должность члена Ассоциации вычислительной техники . Он был избран в 2002 году в состав членов Института исследований операций и управленческих наук . ^[5] Он является обладателем нескольких почетных степеней и членом Национальной академии наук США , ^[6] Американской академии искусств и наук , ^[7] и Американского философского общества . ^[8]

В 2012 году Карп стал директором-основателем Института теории вычислений Саймонса при Калифорнийском университете в Беркли . ^[9]

Карп сделал много важных открытий в области компьютерных наук, комбинаторных алгоритмов и исследования операций . Его основные текущие исследовательские интересы включают биоинформатику .

В 1962 году он совместно с Майклом Хелдом разработал алгоритм Хелда–Карпа , точный экспоненциальный алгоритм для задачи коммивояжера .

В 1971 году он совместно с Джеком Эдмондсом разработал алгоритм Эдмондса–Карпа для решения задачи максимального потока в сетях, а в 1972 году опубликовал знаменательную статью по теории сложности «Сводимость среди комбинаторных задач», в которой доказал, что 21 задача является NP-полной . ^[10]

В 1973 году он и Джон Хопкрофт опубликовали алгоритм Хопкрофта–Карпа , самый быстрый из известных методов поиска паросочетаний максимальной мощности в двудольных графах .

В 1980 году Карп совместно с Ричардом Дж . Липтоном доказал теорему Карпа–Липтона (которая доказывает, что если задачу SAT можно решить с помощью булевых схем с полиномиальным числом логических элементов , то полиномиальная иерархия схлопывается до своего второго уровня).

В 1987 году он совместно с Майклом О. Рабином разработал алгоритм поиска строк Рабина–Карпа .

Его цитата ^[11] для премии Тьюринга (1985) была следующей:

За его постоянный вклад в теорию алгоритмов, включая разработку эффективных алгоритмов для сетевых потоков и других задач комбинаторной оптимизации, идентификацию вычислимости за полиномиальное время с интуитивным понятием алгоритмической эффективности , и, что наиболее примечательно, за вклад в теорию NP-полноты . Карп представил ныне стандартную методологию доказательства того, что задачи являются NP-полными, что привело к идентификации многих теоретических и практических задач как вычислительно сложных.

На Викискладе есть медиафайлы по теме Ричард Карп .

• Интервью/биография Ричарда Карпа журналу ACM Crossroads
• Домашняя страница Карпа в Беркли
• Биография Ричарда Карпа из Института исследований операций и управленческих наук