Из Википедии, бесплатной энциклопедии
  (Перенаправлено от Ричарда Карпа )
Перейти к навигации Перейти к поиску
Ричард Мэннинг Карп
Карп мг 7725-b.cr2.jpg
Ричард Карп на EPFL 13 июля 2009 г.
Родившийся (1935-01-03) 3 января 1935 г. (86 лет)
Бостон, Массачусетс , США
НациональностьАмериканец
Альма-матерГарвардский университет
ИзвестенАлгоритм Эдмондса –
Карпа 21 NP-полная
задача Карпа Алгоритм Хопкрофта – Карпа
Теорема Карпа – Липтона
Алгоритм поиска строки Рабина – Карпа
НаградыПремия Тьюринга (1985)
Теоретическая премия Джона фон Неймана (1990)
Национальная медаль науки (1996)
Премия Харви
Медаль Бенджамина Франклина
Киотская премия Компьютерное общество IEEE Премия
Чарльза Бэббиджа
Научная карьера
ПоляИнформатика
УчрежденияКалифорнийский университет в Беркли
IBM
ТезисНекоторые приложения логического синтаксиса к программированию цифровых компьютеров  (1959)
ДокторантЭнтони Эттингер [1]
Докторанты

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

Биография [ править ]

Родившийся от родителей Авраама и Роуз Карп в Бостоне, штат Массачусетс , Карп имеет трех младших братьев и сестер: Роберт, Дэвид и Кэролин. Его семья была еврейской , [3] , и он вырос в маленькой квартире, в то в основном еврейских окрестности Dorchester в Бостоне. Оба его родителя были выпускниками Гарварда (его мать в конечном итоге получила степень Гарварда в возрасте 57 лет после вечерних курсов), в то время как его отец имел амбиции поступить в медицинскую школу после Гарварда, но стал учителем математики, поскольку он не мог позволить себе медицинскую школу сборы. [3]

Он учился в Гарвардском университете , где получил степень бакалавра в 1955 году, степень магистра в 1956 году и докторскую степень. в прикладной математике в 1959 году он начал работать в IBM «s Thomas J. Watson Research Center . В 1968 году он стал профессором компьютерных наук, математики и исследований операций в Калифорнийском университете в Беркли . Помимо 4-летнего периода работы профессором Вашингтонского университета , он остался в Беркли. С 1988 по 1995 год и с 1999 года по настоящее время он также работал научным сотрудником в Международном институте компьютерных наук. в Беркли, где в настоящее время возглавляет группу алгоритмов.

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

В 2012 году Карп стал основателем директор Института Simons для теории вычислений в Университете Калифорнии, Беркли . [5]

Работа [ править ]

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

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

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

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

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

Премия Тьюринга [ править ]

Его ссылка [7] на премию Тьюринга (1985 г.) была следующей:

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

Ссылки [ править ]

  1. ^ a b Ричард М. Карп в проекте « Математическая генеалогия» .
  2. ^ Ричард Мэннинг Карп - ПРИЗ КИОТО 2008 - Передовые технологии
  3. ^ a b Сила и пределы алгоритмов Ричард Мэннинг Карп, Киотская премия, 2008 г.
  4. ^ Fellows: Alphabetical List , Institute for Operations Research and the Management Sciences , извлечено 2019-10-09.
  5. ^ "Калифорния выбрана домом для вычислительного института" . Нью-Йорк Таймс . 30 апреля 2012 . Проверено 23 октября +2016 .
  6. ^ Ричард М. Карп (1972). «Сводимость среди комбинаторных проблем» (PDF) . В RE Miller; Дж. У. Тэтчер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. С. 85–103.
  7. ^ Ассоциация вычислительной техники. "Цитата на премию ACM / Ричард М. Карп" . Архивировано из оригинала на 2012-07-03 . Проверено 17 января 2010 .

Внешние ссылки [ править ]

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