Ричард М. Карп - Richard M. Karp
Ричард Мэннинг Карп | |
---|---|
Родившийся |
Бостон, Массачусетс , США
|
3 января 1935 г.
Национальность | Американец |
Альма-матер | Гарвардский университет |
Известен |
Алгоритм Эдмондса – Карпа 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-полноты задач, которая привела к идентификации многих теоретических и практических проблем как трудных в вычислительном отношении.
Рекомендации
- ^ a b Ричард М. Карп в проекте « Математическая генеалогия» .
- ^ Ричард Мэннинг Карп - ПРИЗ КИОТО 2008 - Передовые технологии
- ^ a b Сила и пределы алгоритмов Ричард Мэннинг Карп, Киотская премия, 2008 г.
- ^ Fellows: Alphabetical List , Institute for Operations Research and the Management Sciences , извлечено 2019-10-09.
- ^ "Калифорния выбрана домом для вычислительного института" . Нью-Йорк Таймс . 30 апреля 2012 . Проверено 23 октября 2016 года .
- ^ Ричард М. Карп (1972). «Сводимость среди комбинаторных проблем» (PDF) . В RE Miller; Дж. У. Тэтчер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. С. 85–103.
- ^ Ассоциация вычислительной техники. "Цитата на премию ACM / Ричард М. Карп" . Архивировано из оригинала на 2012-07-03 . Проверено 17 января 2010 .
Внешние ссылки
- Интервью журналу ACM Crossroads / биография Ричарда Карпа
- Домашняя страница Карпа в Беркли
- Биография Ричарда Карпа из Института исследований операций и наук управления
Предшественник Джон Маккарти |
Медаль Бенджамина Франклина в области компьютерных и когнитивных наук 2004 |
Преемник Аравинд Джоши |