Хопкрофт, Джон Эдвард

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