Публикация статьи 1972 года «Сводимость комбинаторных задач» (Reducibility Among Combinatorial Problems) утвердила Ричарда М. Карпа как ключевую фигуру в теории вычислительной сложности. Доказав, что 21 различная задача является NP-полной, он предоставил методологию, необходимую исследователям для определения того, какие теоретические и практические задачи в информатике принципиально трудноразрешимы с использованием эффективных полиномиальных алгоритмов.
Академические основы и начало карьеры
Ричард Мэннинг Карп родился в Бостоне в 1935 году и получил все свое формальное образование в Гарвардском университете. Он получил степень бакалавра в 1955 году, степень магистра в 1956 году и завершил докторскую диссертацию по прикладной математике в 1959 году в Гарвардской школе инженерных и прикладных наук. После завершения учебы он начал свою профессиональную карьеру в Исследовательском центре IBM имени Томаса Дж. Уотсона.
Разработка комбинаторных алгоритмов
Работа Карпа охватывает несколько десятилетий алгоритмических разработок. В 1962 году он в сотрудничестве с Майклом Хелдом создал алгоритм Хелда-Карпа для задачи коммивояжера. За этим последовал алгоритм Эдмондса-Карпа 1971 года, разработанный совместно с Джеком Эдмондсом для решения задач о максимальном потоке в сетях. В 1973 году он в партнерстве с Джоном Хопкрофтом создал алгоритм Хопкрофта-Карпа, который остается самым быстрым методом поиска максимального паросочетания в двудольных графах. Кроме того, в 1987 году он совместно с Майклом О. Рабином разработал алгоритм поиска строк Рабина-Карпа.
Институциональные роли и признание
В 1968 году Карп присоединился к преподавательскому составу Калифорнийского университета в Беркли, где стал первым заместителем председателя отделения компьютерных наук. Помимо четырехлетнего пребывания на посту профессора в Вашингтонском университете, он сохранил связь с Беркли. В 2012 году он стал директором-основателем Саймонсовского института теории вычислений. Его вклад в науку был отмечен многочисленными наградами, включая премию Тьюринга (1985), премию Харви (1998), медаль Бенджамина Франклина (2004), премию Киото (2008) и премию Диксона (2009).
Двадцать вопросов, восемь минут на часах и процентиль, измеренный по всем, кто его проходил. Без регистрации.
Пройти тест IQ →Краткие факты
- Дата рождения: 1935 год, Бостон, Массачусетс - Образование: Гарвардский университет (бакалавр, магистр, доктор наук) - Основное место работы: Калифорнийский университет в Беркли - Премия Тьюринга: 1985 год - Премия Киото в области передовых технологий: 2008 год - Основные области исследований: биоинформатика и теория вычислений - Важнейшая публикация 1972 года: Reducibility Among Combinatorial Problems - Директор-основатель: Саймонсовский институт теории вычислений
Часто задаваемые вопросы
### В чем заключается значимость статьи Ричарда Карпа 1972 года?
Она доказала, что 21 различная задача является NP-полной, предоставив стандартную методологию для классификации вычислительной сложности задач.
### Какие важные награды получил Ричард Карп?
Он был удостоен премии Тьюринга, премии Киото, премии Харви, медали Бенджамина Франклина, премии Джона фон Неймана по теории и других наград.
.jpg)
