Джон Эдвард Хопкрофт (англ. John Edward Hopcroft ; род. 7 октября 1939 года , Сиэтл , США ) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга .
Член Национальной инженерной академии США (1989)[ 2] , Национальной академии наук США (2009)[ 3] .
Биография
Хопкрофт получил в 1961 году степень бакалавра в университете Сиэтла , после чего перешёл в Стэнфордский университет и получил там звания мастера наук (1962 ) и доктора философии (1964 ). После трёхлетней работы доцентом в Принстонском университете , Хопкрофт начинает работать в Корнеллском университете , где с 1972 года имеет полную профессуру по прикладной математике и информатике . Он получал именные стипендии Joseph C. Ford-профессор и Joseph Silbert-декан. В настоящее время — IBM-профессор.
Его исследовательская деятельность состоит из теоретических аспектов информатики , в частности анализа алгоритмов , теории автоматов и теории графов . Хопкрофт — соавтор нескольких книг о формальных языках и конечных автоматах .
Вместе с Ричардом Карпом Хопкрофт разработал в 1973 году алгоритм для нахождения максимального паросочетания в двудольных графах , работающий за время
O
(
V
E
)
{\displaystyle O({\sqrt {V}}E)}
. Кроме того, Роберт Тарьян и Джон Хопкрофт разработали алгоритм для нахождения ориентации рёбер в неориентированном графе с целью создания сильно связного графа. Оба алгоритма были названы в честь их изобретателей.
В 1986 году Хопкрофт и Тарджан были награждены премией Тьюринга за «фундаментальный вклад в разработку и анализ алгоритмов и структур данных »[ 4] .
В 1992 году Джон Хопкрофт был назначен президентом США Джорджем Бушем в Национальный научный совет .
В 2008 году Джону Хопкрофту была присуждена премия АСМ имени Карла В. Карлстрома (Karl V. Karlstrom) как выдающемуся преподавателю[ 5] .
31 августа 2009 года учёный совет СПбГУ ИТМО избрал Джона Хопкрофта почётным доктором Санкт-Петербургского государственного университета информационных технологий, механики и оптики [ 6] .
Награды и отличия
Библиография
На русском языке
Ахо, Альфред В. ; Хопкрофт, Джон; Ульман, Джеффри . Структуры данных и алгоритмы = 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 .
См. также
Примечания
Ссылки
Ссылки на внешние ресурсы
Словари и энциклопедии
В библиографических каталогах