Карп, Ричард Мэннинг

Ричард Мэннинг Карп
Richard Manning Karp
ж
Дата рождения:	3 января 1935(1935-01-03) (89 лет)
Место рождения:	Бостон
Страна:	США
Научная сфера:	Теория вычислений, Биоинформатика
Место работы:	Гарвардский университет
Альма-матер:	Калифорнийский университет в Беркли
Научный руководитель:	Энтони Оттингер
Известен как:	Алгоритм Эдмондса-Карпа
Награды и премии:	Премия Тьюринга, Премия Киото и другие
Сайт:	[www.eecs.berkeley.edu/~karp/ s.berkeley.edu/~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», в котором он доказал NP-полноту для 21 задачи.

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

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

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

В конце февраля 2009 года Карп занимал 35 место в списке самых цитируемых авторов в проекте CiteSeer.

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

Награды

• 1977 — Премия Ланчестера (англ. Frederick W. Lanchester Prize), ORSA
• 1979 — Премия Фалкерсона, Американское математическое общество
• 1985 — Премия Тьюринга «за его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты.»
• 1987 — Лекция Джона фон Неймана
• 1990 — Теоретическая премия фон Неймана, ORSA
• 1994 — почётное членство ACM
• 1995 — Премия имени Чарльза Беббиджа
• 1996 — Национальная научная медаль США
• 1998 — Премия Харви, Израильский технологический институт
• 2004 — Медаль Бенджамина Франклина
• 2008 — Премия Киото
• 2008 — Премия Диксона

Литература

• Р. Карп. = Complexity of Computation. — Американское математическое общество, 1974. — 166 с. — ISBN 978-0821813270.

См. также

• Алгоритм Эдмондса — Карпа
• Алгоритм Рабина — Карпа

Ссылки

• [www.eecs.berkeley.edu/~karp/ Сайт Ричарда Карпа] при университете Беркли  (англ.)
• [www.acm.org/crossroads/dayinlife/bios/richard_karp.html «A day in the life of Richard Karp»], биография на сайте ACM
• [www.eecs.berkeley.edu/Faculty/Homepages/karp.html Richard M. Karp] (англ.). — Биография.
• [www.inamori-f.or.jp/laureates/k24_a_richard/prs_e.html Inamori Foundation] (англ.). — Information Science.

Отрывок, характеризующий Карп, Ричард Мэннинг

– Как здесь? Да как же не взорвали мост, когда он минирован?
– А это я у вас спрашиваю. Этого никто, и сам Бонапарте, не знает.
Болконский пожал плечами.
– Но ежели мост перейден, значит, и армия погибла: она будет отрезана, – сказал он.
– В этом то и штука, – отвечал Билибин. – Слушайте. Вступают французы в Вену, как я вам говорил. Всё очень хорошо. На другой день, то есть вчера, господа маршалы: Мюрат Ланн и Бельяр, садятся верхом и отправляются на мост. (Заметьте, все трое гасконцы.) Господа, – говорит один, – вы знаете, что Таборский мост минирован и контраминирован, и что перед ним грозный tete de pont и пятнадцать тысяч войска, которому велено взорвать мост и нас не пускать. Но нашему государю императору Наполеону будет приятно, ежели мы возьмем этот мост. Проедемте втроем и возьмем этот мост. – Поедемте, говорят другие; и они отправляются и берут мост, переходят его и теперь со всею армией по сю сторону Дуная направляются на нас, на вас и на ваши сообщения.
– Полноте шутить, – грустно и серьезно сказал князь Андрей.
Известие это было горестно и вместе с тем приятно князю Андрею.
Как только он узнал, что русская армия находится в таком безнадежном положении, ему пришло в голову, что ему то именно предназначено вывести русскую армию из этого положения, что вот он, тот Тулон, который выведет его из рядов неизвестных офицеров и откроет ему первый путь к славе! Слушая Билибина, он соображал уже, как, приехав к армии, он на военном совете подаст мнение, которое одно спасет армию, и как ему одному будет поручено исполнение этого плана.
– Полноте шутить, – сказал он.
– Не шучу, – продолжал Билибин, – ничего нет справедливее и печальнее. Господа эти приезжают на мост одни и поднимают белые платки; уверяют, что перемирие, и что они, маршалы, едут для переговоров с князем Ауэрспергом. Дежурный офицер пускает их в tete de pont. [мостовое укрепление.] Они рассказывают ему тысячу гасконских глупостей: говорят, что война кончена, что император Франц назначил свидание Бонапарту, что они желают видеть князя Ауэрсперга, и тысячу гасконад и проч. Офицер посылает за Ауэрспергом; господа эти обнимают офицеров, шутят, садятся на пушки, а между тем французский баталион незамеченный входит на мост, сбрасывает мешки с горючими веществами в воду и подходит к tete de pont. Наконец, является сам генерал лейтенант, наш милый князь Ауэрсперг фон Маутерн. «Милый неприятель! Цвет австрийского воинства, герой турецких войн! Вражда кончена, мы можем подать друг другу руку… император Наполеон сгорает желанием узнать князя Ауэрсперга». Одним словом, эти господа, не даром гасконцы, так забрасывают Ауэрсперга прекрасными словами, он так прельщен своею столь быстро установившеюся интимностью с французскими маршалами, так ослеплен видом мантии и страусовых перьев Мюрата, qu'il n'y voit que du feu, et oubl celui qu'il devait faire faire sur l'ennemi. [Что он видит только их огонь и забывает о своем, о том, который он обязан был открыть против неприятеля.] (Несмотря на живость своей речи, Билибин не забыл приостановиться после этого mot, чтобы дать время оценить его.) Французский баталион вбегает в tete de pont, заколачивают пушки, и мост взят. Нет, но что лучше всего, – продолжал он, успокоиваясь в своем волнении прелестью собственного рассказа, – это то, что сержант, приставленный к той пушке, по сигналу которой должно было зажигать мины и взрывать мост, сержант этот, увидав, что французские войска бегут на мост, хотел уже стрелять, но Ланн отвел его руку. Сержант, который, видно, был умнее своего генерала, подходит к Ауэрспергу и говорит: «Князь, вас обманывают, вот французы!» Мюрат видит, что дело проиграно, ежели дать говорить сержанту. Он с удивлением (настоящий гасконец) обращается к Ауэрспергу: «Я не узнаю столь хваленую в мире австрийскую дисциплину, – говорит он, – и вы позволяете так говорить с вами низшему чину!» C'est genial. Le prince d'Auersperg se pique d'honneur et fait mettre le sergent aux arrets. Non, mais avouez que c'est charmant toute cette histoire du pont de Thabor. Ce n'est ni betise, ni lachete… [Это гениально. Князь Ауэрсперг оскорбляется и приказывает арестовать сержанта. Нет, признайтесь, что это прелесть, вся эта история с мостом. Это не то что глупость, не то что подлость…]
– С'est trahison peut etre, [Быть может, измена,] – сказал князь Андрей, живо воображая себе серые шинели, раны, пороховой дым, звуки пальбы и славу, которая ожидает его.
– Non plus. Cela met la cour dans de trop mauvais draps, – продолжал Билибин. – Ce n'est ni trahison, ni lachete, ni betise; c'est comme a Ulm… – Он как будто задумался, отыскивая выражение: – c'est… c'est du Mack. Nous sommes mackes , [Также нет. Это ставит двор в самое нелепое положение; это ни измена, ни подлость, ни глупость; это как при Ульме, это… это Маковщина . Мы обмаковались. ] – заключил он, чувствуя, что он сказал un mot, и свежее mot, такое mot, которое будет повторяться.
Собранные до тех пор складки на лбу быстро распустились в знак удовольствия, и он, слегка улыбаясь, стал рассматривать свои ногти.
– Куда вы? – сказал он вдруг, обращаясь к князю Андрею, который встал и направился в свою комнату.