Войти
| Ричард Мэннинг Карп | |
|---|---|
 Ричард Карп на EPFL 13 июля 2009 г. | |
| Родившийся | ( 1935-01-03)3 января 1935 г. (86 лет) Бостон, Массачусетс, США |
| Национальность | Американец |
| Альма-матер | Гарвардский университет |
| Известен | Алгоритм Эдмондса – Карпа 21 NP-полная задача Карпа Алгоритм Хопкрофта – Карпа Теорема Карпа – Липтона Алгоритм поиска строки Рабина – Карпа |
| Награды | Премия Тьюринга (1985) Теоретическая премия Джона фон Неймана (1990) Национальная медаль науки (1996) Премия Харви Медаль Бенджамина Франклина Киотская премия IEEE Computer Society Премия Чарльза Бэббиджа |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Калифорнийский университет в Беркли IBM |
| Тезис | Некоторые приложения логического синтаксиса к программированию цифровых компьютеров (1959) |
| Докторант | Энтони Эттингер |
| Докторанты | |
Ричард Мэннинг Карп (родился 3 января 1935) американский ученый и вычислительной теоретик в Университете Калифорнии, Беркли. Он наиболее известен своими исследованиями в области теории алгоритмов, за которые он получил премию Тьюринга в 1985 году, медаль Бенджамина Франклина в области компьютерных и когнитивных наук в 2004 году и премию Киото в 2008 году.
Карп был избран членом Национальной инженерной академии (1992 г.) за большой вклад в теорию и применение NP-полноты, построение эффективных комбинаторных алгоритмов и применение вероятностных методов в информатике.
Родившийся от родителей Авраама и Роуз Карп в Бостоне, штат Массачусетс, Карп имеет трех младших братьев и сестер: Роберт, Дэвид и Кэролин. Его семья была еврейкой, и он вырос в маленькой квартире в тогда еще преимущественно еврейском районе Дорчестер в Бостоне. Оба его родителя были выпускниками Гарварда (его мать в конечном итоге получила степень Гарварда в возрасте 57 лет после вечерних курсов), в то время как его отец имел амбиции поступить в медицинскую школу после Гарварда, но стал учителем математики, поскольку он не мог позволить себе медицинскую школу. сборы.
Он учился в Гарвардском университете, где получил степень бакалавра в 1955 году, степень магистра в 1956 году и докторскую степень. в прикладной математике в 1959 году он начал работать в IBM «s Thomas J. Watson Research Center. В 1968 году он стал профессором компьютерных наук, математики и исследований операций в Калифорнийском университете в Беркли. Помимо 4-летнего периода работы профессором Вашингтонского университета, он остался в Беркли. С 1988 по 1995 год и с 1999 года по настоящее время он также был научным сотрудником Международного института компьютерных наук в Беркли, где в настоящее время возглавляет группу алгоритмов.
Ричард Карп был награжден Национальной медалью науки, и был получателем Харви премии в Технион и 2004 Бенджамин Франклин медаль в компьютерных и когнитивной науке для его проникновения в вычислительной сложности. В 1994 году он был введен в качестве стипендиата от Ассоциации вычислительной техники. Он был избран в классе 2002 стипендиатов в Институт исследования операций и наук управления. Он получил несколько почетных степеней.
В 2012 году Карп стал основателем директор Института Simons для теории вычислений в Университете Калифорнии, Беркли.
Карп сделал много важных открытий в области информатики, комбинаторных алгоритмов и исследования операций. Его основные текущие исследовательские интересы включают биоинформатику.
В 1971 году он совместно с Джеком Эдмондсом разработал алгоритм Эдмондса – Карпа для решения задачи о максимальном потоке в сетях, а в 1972 году он опубликовал знаменательную статью по теории сложности «Сводимость среди комбинаторных проблем», в которой доказал, что 21 задача является решаемой. НП-полный.
В 1973 году он и Джон Хопкрофт опубликовали алгоритм Хопкрофта – Карпа, самый быстрый из известных методов поиска совпадений максимальной мощности в двудольных графах.
В 1980 году вместе с Ричардом Дж. Липтоном Карп доказал теорему Карпа-Липтона (которая доказывает, что если SAT может быть решена с помощью булевых схем с полиномиальным числом логических вентилей, то полиномиальная иерархия схлопывается до второго уровня).
В 1987 году он совместно с Майклом О. Рабином разработал алгоритм поиска строки Рабина-Карпа.
Его ссылка на премию Тьюринга (1985 г.) была следующей:
За его постоянный вклад в теорию алгоритмов, включая разработку эффективных алгоритмов для сетевого потока и других задач комбинаторной оптимизации, определение вычислимости за полиномиальное время с интуитивным понятием алгоритмической эффективности, и, в первую очередь, за вклад в теорию NP -полнота. Карп представил теперь стандартную методологию доказательства NP-полноты задач, которая привела к идентификации многих теоретических и практических проблем как трудных в вычислительном отношении.
| Предшественник Джон Маккарти | Медаль Бенджамина Франклина в области компьютерных и когнитивных наук 2004 | Преемник Аравинд Джоши |
