John E. Hopcroft, 1986 ACM Turing Award Recipient

Посчастливилось услышать вживую Джона Эдварда Хопкрофта, лауреата премии Тьюринга. Хопкрофт получил после трёхлетней работы доцентом в Принстонском университете именные стипендии. В настоящее время — IBM-профессор.Его исследовательская деятельность состоит из теоретических аспектов информатики, в частности анализа алгоритмов, теории автоматов и теории графов. Хопкрофт — соавтор нескольких книг о формальных языках и конечных автоматов. Хопкрофт разработал в 1973 году алгоритм для нахождения максимального паросочетания в двудольных графах, работающий за время ?(??). Кроме того, Роберт Тарьян и Джон Хопкрофт разработали алгоритм для нахождения ориентации рёбер в неориентированном графе с целью создания сильно связного графа. Оба алгоритма были названы в честь их изобретателей. В 1986 году Хопкрофт и Тарджан были награждены премией Тьюринга за "фундаментальный вклад в разработку и анализ алгоритмов". Более полное интервью Хопкрофта об открытии связанных графов можно посмотреть по ссылке https://yandex.ru/video/touch/preview/12541722623108123913

Источник: yandex.ru

Комментарии: