Ричард М. Карп
Ричард Мэннинг Карп | |
|---|---|
 Ричард Карп в EPFL в 2009 году | |
| Рожденный | 3 января 1935 г. Бостон, Массачусетс , США |
| Национальность | Американский |
| Альма-матер | Гарвардский университет |
| Известный | Гипотеза Андераа – Карпа – Розенберга Алгоритм Эдмондса – Карпа Алгоритм Хелда – Карпа Алгоритм Хопкрофта – Карпа Алгоритм Кармаркара – Карпа Алгоритм поиска строки Рабина – Карпа Теорема Карпа – Липтона 21 NP-полная задача Карпа Система векторного сложения |
| Награды | Премия Фулкерсона (1979) Премия Тьюринга (1985) Премия Джона фон Неймана за теорию (1990) Премия Чарльза Бэббиджа компьютерного общества IEEE (1995) Национальная медаль науки (1996 г.) Премия Харви (1998) Премия EATCS (2000) Медаль Бенджамина Франклина (2004 г.) Киотская премия (2008 г.) |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Калифорнийский университет, Беркли ИБМ |
| Диссертация | Некоторые приложения логического синтаксиса к цифровому компьютерному программированию (1959) |
| Докторантура | Энтони Эттингер [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-полноты задач, что привело к идентификации многих теоретических и практических задач как вычислительно сложных.
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Ричард М. Карп в проекте «Математическая генеалогия» .
- ^ Ричард Мэннинг Карп - КИОТСКАЯ ПРЕМИЯ 2008 ГОДА - Передовые технологии
- ↑ Перейти обратно: Перейти обратно: а б Сила и пределы алгоритмов Ричард Мэннинг Карп, Речь о Киотской премии, 2008 г.
- ^ Карп, Ричард. «Личный взгляд на информатику в Беркли» . www2.eecs.berkeley.edu . Проверено 1 декабря 2021 г.
- ^ Стипендиаты: Алфавитный список , Институт исследования операций и наук управления , получено 9 октября 2019 г.
- ^ «Ричард М. Карп» . www.nasonline.org . Проверено 22 февраля 2022 г.
- ^ «Ричард М. Карп» . Американская академия искусств и наук . Проверено 22 февраля 2022 г.
- ^ «История участников APS» . search.amphilsoc.org . Проверено 22 февраля 2022 г.
- ^ «Калифорния выбрана домом для вычислительного института» . Нью-Йорк Таймс . 30 апреля 2012 года . Проверено 23 октября 2016 г.
- ^ Ричард М. Карп (1972). «Сводимость среди комбинаторных задач» (PDF) . В Р.Э. Миллере; Дж. Тэтчер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. стр. 85–103.
- ^ Ассоциация вычислительной техники. «Цитирование премии ACM / Ричард М. Карп» . Архивировано из оригинала 3 июля 2012 г. Проверено 17 января 2010 г.
Внешние ссылки [ править ]
- Интервью/биография Ричарда Карпа журналу ACM Crossroads
- Домашняя страница Карпа в Беркли
- Биография Ричарда Карпа из Института исследования операций и наук управления
- Американские ученые-компьютерщики
- Американские исследователи операций
- 1935 рождений
- Живые люди
- Американские ученые-теоретики-компьютерщики
- 1994 г. Члены Ассоциации вычислительной техники.
- Члены Общества промышленной и прикладной математики
- Стипендиаты Института исследования операций и наук управления
- Лауреаты Киотского протокола в области передовых технологий
- Члены Национальной инженерной академии США
- Члены Национальной академии наук США
- Лауреаты премии Джона фон Неймана по теории
- Американские учёные-евреи
- Лауреаты Национальной медали науки
- Лауреаты премии Тьюринга
- Инженерный факультет Калифорнийского университета в Беркли
- Члены Французской академии наук
- Люди из Бостона
- Американские инженеры 20-го века
- Американские инженеры XXI века
- Американские математики XX века
- Американские математики XXI века
- Американские учёные XX века
- Американские учёные XXI века
- Выпускники Гарвардской школы инженерии и прикладных наук имени Джона А. Полсона
- Члены Американского философского общества