Тарьян Роберт Андре
| Тарьян Роберт Андре | |
| Robert Endre Tarjan | |
| |
| На английском: | Robert Endre Tarjan |
| Дата рождения: | 30.04.1948 |
| Место рождения: | Помона, США |
| Краткая информация: Специалист в области теории вычислительных систем | |
Содержание
Биография
Родился 30 апреля 1948 года в калифорнийском городе Помона.
Является автором множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка (Tarjan’s off-line least common ancestors algorithm).
Также он является соавтором структур данных «Фибоначчиева куча» и «Splay-дерево».
Образование
Отец Роберта Тарьяна был детским врачом, специализирующимся в мозге и являлся управляющим центральной поликлиники штата. В детстве Тарьян читал много научной фантастики и хотел стать астрономом. Он заинтересовался математикой после прочтения заметок Мартина Гарднера по математическим играм в журнале 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.
Публикации
- Robert E. Tarjan Data structures and network algorithms. — Philadelphia: 1983. — ISBN 978-0898711875
- Robert E. Tarjan Notes on introductory combinatorics. — Boston: 1983. — ISBN 978-0817631703
- OCLC entries for Robert E Tarjan
- DBLP entry for Robert Endre Tarjan
Достижения
- доктор философских наук
- Заслуженный профессор компьютерных наук (в университете Принстона)
Награды
- Премия Тьюринга (Вместе с Джоном Хопкрофтом в 1986. В сопроводительном тексте к награде написано За фундаментальные результаты в области разработки и анализа алгоритмов и структур данных)
- член ACM (ACM Fellow. 1994. В поздравительном тексте указано: За плодотворный труд в области разработки и анализа алгоритмов и структур данных)
- National Academy of Sciences Award (for Initiatives in Research. 1984)
- Paris Kanellakis Award in Theory and Practice (ACM. 1999)
- медаль им. Блеза Паскаля за работы в области математики и компьютерных наук (Европейской академии наук, 2004)
- Премия математика Рольфа Германа Неванлинны (1982. Золотая медаль и денежная премия)
Разное
- Известен своими революционными работами в области алгоритмов на графах.
- Лауреат премии Тьюринга (В сфере информационных технологий премия Тьюринга имеет статус, аналогичный Нобелевской премии в академических науках.) за «За фундаментальные результаты в области разработки и анализа алгоритмов и структур данных».
Библиография
- Математика: 85 лет без Нобелевских премий
- Контактная информация - Факультет компьютерных наук Принстонский университет
- Педагогика
Контакты
- Эл. почта: robert.tarjan AT hp.com, ret@cs.princeton.edu
