 |
Ричард Мэннинг КарпАмериканский учёный в области теории вычислительных систем
Дата рождения: 03.01.1935
Страна:  США |
Содержание:
- Детство и образование
- Профессиональная карьера
- Вклад в теорию вычислительных систем
- Доказательство NP-полноты
- Алгоритм Карпа-Рабина
- Признание и награды
Детство и образование
Ричард Карп родился в Бостоне, Массачусетс, в 1935 году, в семье педагогов. Будучи сыном учителя математики и директора средней школы, он получил раннее образование в области математики. После окончания школы Карп поступил в Гарвардский университет, где получил степени бакалавра, магистра и доктора философии по прикладной математике к 1959 году.
Профессиональная карьера
После получения степени Карп девять лет работал в исследовательском центре IBM Thomas J. Watson. В 1968 году он стал профессором информатики, математики и исследования операций в Калифорнийском университете в Беркли. Карп продолжал преподавать и исследовать в Беркли до настоящего времени, сделав четырехлетний перерыв для работы в Вашингтонском университете.
Вклад в теорию вычислительных систем
Разработка алгоритма Карпа-ЭдмондсаВ 1971 году Карп и Джэк Эдмондс разработали алгоритм Карпа-Эдмондса для определения максимального потока в транспортной сети. Этот алгоритм стал основой для разработки транспортных моделей и других приложений.
Доказательство NP-полноты
В 1972 году Карп опубликовал свой труд "Reducibility Among Combinatorial Problems", в котором доказал, что 21 задача относится к классу NP-полных. Это открытие означало, что эти задачи в высшей степени трудно было решить эффективно.
Алгоритм Карпа-Рабина
В 1987 году Карп и Майкл Рабин разработали алгоритм Карпа-Рабина для поиска подстрок. Этот алгоритм широко используется в обработке текста, биоинформатике и других областях.
Признание и награды
Карп является лауреатом престижной премии Тьюринга за вклад в теорию вычислительных систем. Он также был включен в список самых цитируемых авторов в проекте CiteSeer. Вклад Карпа в области компьютерных наук значительно повлиял на разработку алгоритмов, оптимизации и других фундаментальных концепций.
