Главная
Роберт Андре Тарьян (англ. Robert Endre Tarjan; /ˈrɔːbət ˈtɑrdʒæn/; род. 30 апреля 1948, Помона, США) — известный американский учёный в области теории вычислительных систем.
Он является автором множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка (Tarjan’s off-line least common ancestors algorithm). Также он является соавтором структур данных «Фибоначчиева куча» и «Расширяющееся дерево». Ввел термин Амортизационный анализ.
Образование
Отец Роберта Тарьяна был детским врачом, специализирующимся на задержках умственного развития, и руководил больницей штата.
В детстве Тарьян читал много научной фантастики и хотел стать астрономом. Он заинтересовался математикой после прочтения заметок Мартина Гарднера по математическим играм в журнале Scientific American. Серьёзный интерес к математике был привит в восьмом классе «очень мотивирующим» учителем.
Во время обучения в школе Тарьяну посчастливилось поработать в IBM с сортировально-подборочной машиной для перфокарт. В 1964 году в летней школе он получил первый серьёзный опыт работы с настоящими компьютерами.
Тарьян получил звание бакалавра по математике в технологическом институте Калифорнии (California Institute of Technology) в 1969 году. В Стэнфордском университете он получил магистерскую степень по компьютерным наукам (1971) и степень доктора философии (Doctor of Philosophy) в компьютерных науках — в 1972 г. Его научными руководителями в Стэнфорде были Роберт Флойд и Дональд Кнут, диссертация называлась «Эффективный алгоритм определения планарности графа» (An Efficient Planarity Algorithm). Тарьян выбрал компьютерную науку как путь, на котором математика сможет принести ощутимую практическую пользу.
Карьера
Тарьян работает преподавателем в Принстонском университете начиная с 1985 года. У него также были академические должности в Корнеллском университете (1972—1973), Калифорнийском университете в Беркли (1973—1975), Стэнфордском университете (1974—1980), Нью-Йоркском университете (1981—1985). Он также был членом NEC Research Institute (1989—1997) и числится (на должности Visiting Scientist) в университете Массачусетса (1996).
Тарьян работал в AT&T Bell Labs (1980—1989), InterTrust Technologies (1997—2001), Compaq (2002) и Hewlett Packard, где продолжает работать с 2006 г. Он избирался членом различных комитетов ACM и IEEE, а также работал редактором нескольких реферируемых журналов.
Алгоритмы и структуры данных
Тарьян придумал множество эффективных алгоритмов и структур данных для решения различных прикладных задач. Он опубликовал более 228 статей в реферируемых журналах и монографиях.
Тарьян известен своими революционными работами в области алгоритмов на графах. Наиболее яркие из них — Оффлайновый алгоритм Тарьяна поиска ближайшего общего предка для многократного быстрого поиска самого глубокого узла дерева, являющегося общим предком двух заданных узлов, и Алгоритм Тарьяна вычисления сильно связных компонент. Алгоритм Хопкрофта — Тарьяна стал первым линейным алгоритмом определения планарности графа.
Тарьян разработал ряд важнейших структур данных, таких как «Фибоначчиева куча», «Система непересекающихся множеств» и «Расширяющееся дерево» (splay tree) (один из видов сбалансированного двоичного дерева поиска; в соавторстве с Дэниелом Слитором).
Сегодня Роберт Тарьян заслуженный профессор компьютерных наук (James S. McDonnell Distinguished University Professor of Computer Science) в университете Принстона, а также работает в Hewlett-Packard.
Награды
Тарьян получил Премию Тьюринга вместе с Джоном Хопкрофтом в 1986 г. В сопроводительном тексте к награде написано:
За фундаментальные результаты в области разработки и анализа алгоритмов и структур данных.Тарьян также был избран членом ACM (ACM Fellow) в 1994. В поздравительном тексте [1] указано:
За плодотворный труд в области разработки и анализа алгоритмов и структур данных.Другие награды Роберта Тарьяна:
- Стипендия Гуггенхайма (1978)
- Премия Неванлинны (1982) — первый лауреат этой премии
- National Academy of Sciences Award for Initiatives in Research (1984)
- Paris Kanellakis Award in Theory and Practice, ACM (1999)
- Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences (2004)
В конце февраля 2009 года Тарьян занимал 39 место в списке самых цитируемых авторов в проекте CiteSeer.