Хопкрофт

Хопкрофт, Джон

Джон Эдвард Хопкрофт
John Edward Hopcroft
Дата рождения:	7 октября 1939(1939-10-07) (70 лет)
Место рождения:	Сиэтл
Гражданство:	США
Научная сфера:	Информатика
Место работы:	Корнелльский университет
Альма-матер:	Стэнфордский университет
Награды и премии	Премия Тьюринга
Сайт:	http://www.cs.cornell.edu/jeh/

Джон Эдвард Хопкрофт (англ. John Edward Hopcroft, 7 октября 1939 года, Сиэтл, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.

Биография

Хопкрофт получил в 1961 году степень бакалавра в университете Сиэтла, после чего перешёл в Стэнфордский университет и получил там звания мастера наук (1962) и доктора философии (1964). После трёхлетней работы доцентом в Принстонском университете, Хопкрофт начинает работать в Корнелльском университете, где с 1972 года имеет полную профессуру по прикладной математике и информатике. Он получал именные стипендии Joseph C. Ford-профессор и Joseph Silbert-декан. В настоящее время — IBM-профессор.

Его исследовательская деятельность состоит из теоретических аспектов информатики, в частности анализа алгоритмов, теории автоматов и теории графов. Хопкрофт — соавтор нескольких книг о формальных языках и конечных автоматах.

Вместе с Ричардом Карпом Хопкрофт разработал в 1973 году алгоритм для нахождения максимального паросочетания в двудольных графах, работающий за время $O(\sqrt{V}E)$. Кроме того, Роберт Тарьян и Джон Хопкрофт разработали алгоритм для нахождения ориентации рёбер в неориентированном графе с целью создания сильно связного графа. Оба алгоритма были названы в честь их изобретателей.

В 1986 году Хопкрофт и Тарьян были награждены премией Тьюринга за «фундаментальный вклад в разработку и анализ алгоритмов и структур данных».^[1]

В 1992 году Джон Хопкрофт был назначен Президентом США Дж. Бушем в Национальный научный совет.

В 2008 году Джону Хопкрофту была присуждена премия АСМ Карла В. Карлстрома (Karl V. Karlstrom) как выдающемуся преподавателю. ^[2]

31 августа 2009 г. Ученый совет СПбГУ ИТМО избрал Джона Хопкрофта почетным доктором Санкт-Петербургского государственного университета информационных технологий, механики и оптики.^[3]

Награды

• 1986 — Премия Тьюринга
• 1986 — почетный член Американской академии искусств и наук
• 1987 — почетный член Американской ассоциации по поддержке науки
• 1987 — почетный член Института инженеров по электротехнике и электронике (IEEE)
• 1989 — член Национальной инженерной академии США
• 1990 — Honoris causa от университета Сиэтла
• 1994 — почётное членство в Ассоциации вычислительной техники (ACM)
• 2005 — Мемориальная премия Гарри М. Гуда
• 2008 — премия АСМ Карла В. Карлстрома (Karl V. Karlstrom) как выдающемуся преподавателю
• 2009 — почетный член Общества промышленной и прикладной математики
• 2009 — член Национальной академии наук
• 2009 — почетный доктор Санкт-Петербургского государственного университета информационных технологий, механики и оптики

См. также

• Алгоритм Хопкрофта—Тарьяна
• Алгоритм Хопкрофта—Карпа

Примечания

1. ↑ http://awards.acm.org/citation.cfm?id=1053917&srt=alpha&alpha=H&aw=140&ao=AMTURING
2. ↑ http://awards.acm.org/citation.cfm?id=1053917&srt=all&aw=142&ao=KARLSTRM
3. ↑ http://www.ifmo.ru/news/1482/2009_09_24.htm

Литература

• Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы = Data Structures and Algorithms. — Издательский дом «Вильямс», 2000. — С. 384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)

• Хопкрофт, Джон, Мотвани, Раджив, Ульман, Джеффри, Д. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1

Ссылки

• Сайт Хопкрофта при Корнелльском университете (англ.)
• Список публикаций (англ.)

Лауреаты премии Тьюринга

Перлис (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)