Русская Википедия:Карп, Ричард Мэннинг

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Однофамильцы Шаблон:Учёный Ричард Мэннинг Карп (Шаблон:Lang-en; род. 3 января 1935 года, Бостон, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.

Член Национальной академии наук США (1980)[1], Национальной инженерной академии США (1992)[2], иностранный член Французской академии наук (2002)[3].

Биография

Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа (1908—1981) и его жены Розы (Роуз) Карп (1912—2000), из семей еврейских иммигрантов из России[4], в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид (род. 1944, социолог) и младшая сестра Кэролин.

Окончив школу, Ричард поступил в Гарвардский университет, где получил степени бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году.

После учёбы Ричард Карп работал 9 лет в исследовательском центре IBM (Шаблон:Iw). В 1968 году он получил профессуру по информатике, математике и исследованию операций в калифорнийском университете Беркли, где и работает по сей день, не считая четырёхлетнего перерыва на работу в Вашингтонском университете (в Сиэтле).

Вклад

В 1971 году Карп вместе с Шаблон:Iw разработал алгоритм для нахождения максимального потока в транспортной сети, названный в их честь. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems»,[5] в котором он доказал NP-полноту для 21 задачи.

В 1973 году Карп и Джон Хопкрофт опубликовали алгоритм Хопкрофта — Карпа, который является самым быстрым известным методом для нахождения максимальных соответствий количества элементов в двудольных графах[6].

В 1980 году, вместе с Ричардом Дж. Липтоном, Карп доказал Шаблон:Iw.

В 1987 году, вместе с Майклом Рабином, Карп разработал алгоритм поиска подстроки, названный в их честь[6].

Ричард Карп сделал много других важных открытий в информатике и исследовании операций в области комбинаторных алгоритмов. На сегодняшний день он занимается исследованиями в биоинформатике[6].

Признание

Литература

См. также

Ссылки

Примечания

Шаблон:Примечания

Внешние ссылки

  1. ↑ Шаблон:Us nas id
  2. ↑ Dr. Richard M. Karp Шаблон:WaybackШаблон:Ref-en
  3. ↑ Richard Karp Шаблон:WaybackШаблон:Ref-fr
  4. ↑ Семья матери происходила из местечка Эйшишки Гродненской губернии.
  5. ↑ «Reducibility Among Combinatorial Problems» Шаблон:Wayback, Р. Карп, 1972 годШаблон:Ref-en
  6. ↑ 6,0 6,1 6,2 Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Richard M. Karp — The Franklin Institute Awards — Laureate Database Шаблон:Wayback

Шаблон:Выбор языка Шаблон:- Шаблон:Премия Тьюринга

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Карп,_Ричард_Мэннинг&oldid=10092357