- Карп, Ричард Мэннинг
-
Ричард Мэннинг Карп Richard Manning Karp 
Дата рождения: Место рождения: Страна: Научная сфера: Место работы: Альма-матер: Научный руководитель: Энтони Оттингер
Известен как: Награды и премии
Премия Тьюринга, Премия Киото и другиеСайт: Ричард Мэннинг Карп (англ. Richard Manning Karp, 3 января 1935 года, Бостон, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.
Содержание
Биография
Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа (Abraham Louis Karp) и его жены Розы (Роуз) Карп в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид, и младшая сестра Кэролин. Окончив школу, Ричард поступил в Гарвардский университет, где получил титулы бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году.
После учёбы, Ричард Карп работал 9 лет в исследовательском центре IBM (Thomas J. Watson Research Center). В 1968 году он получил профессуру по информатике, математике и исследованию операций при калифорнийском университете Беркли, где и работет по сей день, не учитывая четырёхлетнего перерыва на работу в университете Вашингтона.
В 1971 году Карп вместе с Джэком Эдмондсом разработал алгоритм для нахождения максимального потока в транспортной сети, названный в их честь. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems»,[1] в котором он доказал NP-полноту для 21 задачи.
В 1987 году, вместе с Майклом Рабином, Карп разработал алгоритм поиска подстроки, названный в их честь.
В конце февраля 2009 года Карп занимал 35 место в списке самых цитируемых авторов в проекте CiteSeer.[2]
Награды
- 1977 — Премия Ланчестера (англ. Frederick W. Lanchester Prize), 1979 — Премия Фалкерсона (англ. Fulkerson Prize), Американское математическое общество
- 1985 — Премия Тьюринга «за его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты.»
- 1990 — Премия имени Джона фон Неймана (англ. John von Neumann Theory Prize), 1994 — почётное членство ACM
- 1995 — Премия имени Чарльза Беббиджа
- 1996 — Национальная научная медаль США
- 1998 — Премия Харви, Израильский технологический институт
- 2004 — Медаль имени Бенджамина Франклина[3]
- 2008 — Премия Киото
Литература
- Р. Карп = Complexity of Computation. — Американское математическое общество, 1974. — 166 с. — ISBN 978-0821813270
См. также
Ссылки
- Сайт Ричарда Карпа при университете Беркли (англ.)
- «A day in the life of Richard Karp», биография на сайте ACM (англ.)
- Список известных учеников Карпа на сайте Mathematics Genealogy Project (англ.)
Примечания
Лауреаты премии Тьюринга Перлис (1966) • Уилкс (1967) • Хэмминг (1968) • Минский (1969) • Уилкинсон (1970) • Маккарти (1971) • Дейкстра (1972) • Бахман (1973) • Кнут (1974) • Ньюэлл + Саймон (1975) • Рабин + Скотт (1976) • Бэкус (1977) • Флойд (1978) • Айверсон (1979) • Хоар (1980) • Кодд (1981) • Кук (1982) • Томпсон + Ритчи (1983) • Вирт (1984) • Карп (1985) • Хопкрофт + Тарьян (1986) • Кок (1987) • Сазерленд (1988) • Кэхэн (1989) • Корбато (1990) • Милнер (1991) • Лэмпсон (1992) • Хартманис + Стернс (1993) • Фейгенбаум + Редди (1994) • Блюм (1995) • Пнуели (1996) • Энгельбарт (1997) • Грей (1998) • Брукс (1999) • Яо (2000) • Даль + Нюгорд (2001) • Ривест + Шамир + Адлеман (2002) • Кэй (2003) • Серф + Кан (2004) • Наур (2005) • Аллен (2006) • Кларк + Эмерсон + Сифакис (2007) • Лисков (2008) • Текер (2009) • Вэлиант (2010) • Перл (2011)
Категории:- Персоналии по алфавиту
- Учёные по алфавиту
- Родившиеся 3 января
- Родившиеся в 1935 году
- Лауреаты премии Тьюринга
- Выпускники Гарварда
- Учёные в области информатики США
- Родившиеся в Бостоне
- Члены и члены-корреспонденты Национальной академии наук США
- Математики США
- Награждённые Национальной медалью науки США
- Лауреаты премии Харви
- Члены Французской академии наук
Wikimedia Foundation. 2010.
