Ричард Мэннинг Карп
Ричард Мэннинг Карп (англ. Richard Manning Karp) — американский учёный в области теории вычислительных систем[1].
Научная карьера[править]
Родился 3 января 1935 года в Бостоне в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа и Розы Карп.
В 1955 году получил степень бакалавра, в 1956 году — степень магистра наук, а в 1959 году — степень доктора философии по прикладной математике в в Гарвардском университете.
Затем 9 лет работал в исследовательском центре IBM (Thomas J. Watson Research Center).
В 1968 году получил профессуру по информатике, математике и исследованию операций при калифорнийском университете Беркли.
4 года работал в университете Вашингтона.
В 1971 году вместе с Джэком Эдмондсом разработал алгоритм для нахождения максимального потока в транспортной сети, названный в их честь. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems», в котором доказал NP-полноту для 21 задачи.
В 1973 году Карп и Джон Хопкрофт опубликовали алгоритм Хопкрофта-Карпа, который является самым быстрым известным методом для нахождения максимальных соответствий количества элементов в двудольных графах.
В 1980 году вместе с Ричардом Дж. Липтоном доказал теорему Карпа-Липтона.
В 1987 году вместе с Майклом Ошером Рабином разработал алгоритм поиска подстроки, названный Алгоритмом Рабина — Карпа.
В конце февраля 2009 года занимал 35 место в списке самых цитируемых авторов в проекте CiteSeer.
Совершил большое число других важных открытий в информатике и исследовании операций в области комбинаторных алгоритмов. Занимается исследованиями в биоинформатике.
Награды: в 1977 году — Премия Ланчестера, в 1979 году — Премия Фалкерсона, Американское математическое общество, в 1985 году — Премия Тьюринга «за его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты.», в 1990 году — Теоретическая премия фон Неймана, ORSA, в 1994 году — почётное членство ACM, в 1995 году — Премия имени Чарльза Беббиджа, в 1996 году — Национальная научная медаль США, в 1998 году — Премия Харви, Технион, в 2004 году — Медаль Бенджамина Франклина, в 2008 году — Премия Киото, в 2008 году — Премия Диксона.
Источники[править]
- Родившиеся 3 января
- Родившиеся в 1935 году
- Персоналии по алфавиту
- Родившиеся в Бостоне
- Учёные по алфавиту
- Фелло Ассоциации вычислительной техники
- Преподаватели Калифорнийского университета в Беркли
- Выпускники Гарвардского университета
- Учёные в области информатики США
- Члены и члены-корреспонденты Национальной академии наук США
- Математики США
- Награждённые Национальной медалью науки США
- Лауреаты премии Харви
- Члены Французской академии наук
- Евреи в США
- Награждённые медалью Бенджамина Франклина
- Лауреаты премии Диксона
- Лауреаты премии Киото
- Лауреаты премии Тьюринга
- Ашкеназы
- Евреи-математики