Страна: США

Образование: John Е. Hopcroft - Доктор философии в области прикладной математики, Стэнфордский университет, 1964

Robert E. Tarjan - Доктор философии в области информатики, Стэнфордский университет, 1972

О лауреатах

Hopcraft попал в сферу информатики случайно, когда его попросили преподавать курс в этой области. У него не было опыта, однако ему удалось создать и преподавать курс своим первым шести ученикам, которые, в свою очередь, мотивировали его. Один из его первых студентов, J. Ullman, стал главным соавтором в его работах. Вместе они взяли учебные заметки и расширили их в одну из самых ранних и влиятельных книг в этой области [1]. Первые исследования, которые сделал Hopcraft, в области информатики стали известны, как теория формального языка. Работа над формальными языками и анализ алгоритмов сделали его одним из новаторов среди ученых, которые поставили эту дисциплину на прочную теоретическую основу. В Стэнфорде Tarjan и Hopcraft начали разработку эффективных алгоритмов для решения проблемы графов. Они решили, что модель вычисления будет гипотетическим компьютером, целью которого является разработка алгоритма, чтобы минимизировать наихудшее время работы. Эта работа привела к первому линейному алгоритму определения планарности графа, который Tarjan исследовал в своей диссертации. Кроме того, его работы о формальных языках и их связи с автоматами, а также по разработке и анализу алгоритмов, стали стандартами для нескольких поколений учёных.

Ключевые слова: Algorithms and data structures

Краткая библиография

1.	Hopcroft, J. and J. D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Massachusetts, 1969. Книга, которая началась как набор заметок для первого преподавательского курса по информатике.
2.	Hopcroft, J., and J. D. Ullman, Introduction to Automata Theory, Language, and Computation, Addison-Wesley, Reading, Massachusetts, 1979. Second Edition (with Rajeev Motwani), 2001. Книга, объединяющая авторов, которые уже более 30 лет устанавливают стандарты для обучения теоретическим вычислениям.
3.	Hopcroft, J. E. and R. E. Tarjan, “Efficient Planarity Testing,” Journal of the ACM, Vol. 21, No. 4, pp. 549-568, October, 1974. Эта статья описывает линейный алгоритм определения планарности графа.