Роберт Тарьян

Роберт Андре Тарьян
Дата рождения:	30 апреля 1948
Место рождения:	Помона, Калифорния
Научная сфера:	Информатика
Место работы:	Princeton University Альма-матер:	Калтех, Стэнфорд
Награды и премии	Премия Тьюринга

Роберт Андре Тарьян (англ. Robert Endre Tarjan, 30 апреля 1948 года, Помона, США) — известный американский учёный в области теории вычислительных систем. Родился 30 апреля 1948 года в калифорнийском городе Помона. Он является автором множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска низшего общего предшественника (Tarjan’s off-line least common ancestors algorithm). Также он является соавтором структур данных «Фибоначчиева куча» и «Splay-дерево».

Образование

Отец Роберта Тарьяна был детским врачом, специализирующимся в мозге и являлся управляющим центральной поликлиники штата. ^[1]

В детстве Тарьян читал много научной фантастики и хотел стать астрономом. Он заитересовался математикой после прочтения заметок Мартина Гарднера по математическим играм в журнале Scientific American. Серьёзный интерес к математике был привит в восьмом классе «очень мотивирующим» учителем.

Пока Тарьян учился в школе ему посчастливилось поработать в IBM с сортировально-подборочной машиной для перфокарт. В летней школе в 1964 он получил первый серьёзный опыт работы с настоящими компьютерами.^[1]

Тарьян получил звание бакалавра по математике в технологическом институте Калифорнии (California Institute of Technology) в 1969. В Стендфордском университете он получил магистерскую степень по компьютерным наукам (1971) и степень доктора наук (Doctor of Philosophy) в компьютерных науках — в 1972. Его научными руководителями в Стендфорде были Роберт Флойд и Дональд Кнут. Его диссертация называлась «Эффективный алгоритм определения планарности графа» (An Efficient Planarity Algorithm).^[2] Тарьян выбрал компьютерную науку как путь, на котором математика сможет принести ощутимую практическую пользу.^[3]

Карьера

Тарьян работает преподавателем в университете Принстона начиная с 1985 года.^[3] У него также были академическая должности в университете Корнел (1972-73), университете Калифорнии, Беркли (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 статей в реферируемых журналах и монографиях.

Тарьян известен своими революционными работами вобласти алгоритмов на графах. Наиболее яркие из них — Оффлайновый алгоритм Тарьяна поиска ближайшего общего предка для многократного быстрого поиска самого глубокого узла дерева, являющегося общим предком двух заданных узлов, и Алгоритм Тарьяна вычисления сильно связных компонент. Алгоритм Хопкрофта-Тарьяна стал первым линейным алгоритмом определения планарности графа.^[4]

Тарьян разработал ряд важнейших структур данных, таких как «Фибоначчиева куча» и Расширяющееся дерево (splay tree) (один из видов сбалансированного двоичного дерева поиска; в соавторстве с Даниилом Слейтором).

Сегодня Роберт Тарьян заслуженный профессор компьютерных наук (James S. McDonnell Distinguished University Professor of Computer Science) в университете Принстона, а также работает в [5]

Награды

Тарьян получил Премию Тьюринга вместе с Джоном Хопкрофтом в 1986. В сопроводительном тексте к награде написано

За фундаментальные результаты в области разработки и анализа алгоритмов и структур данных.

Тарьян также был избран членом ACM (ACM Fellow) в 1994. В поздравительном тексте [1] указано:

За плодотворный труд в области разработки и анализа алгоритмов и структур данных.

Другие награды роберта Тарьяна:

• Nevanlinna Prize in Information Science (1983) — first recipient
• 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 место в списке самых цитируемых авторов в проекте [6]

Примечания

1. ↑ ^{1 2} Dennis Elliott Shasha Robert E. Tarjan: In Search of Good Structure // Out of Their Minds: The Lives and Discoveries of 15 Great Computer. — 1998. — ISBN 978-0387979922
2. ↑ Robert Endre Tarjan. Mathematics Genealogy Project. Проверено 9 января 2008.
3. ↑ ^{1 2} Robert Endre Tarjan: The art of the algorithm (interview). Hewlett-Packard (September 2004). Проверено 9 января 2008.
4. ↑ William Kocay Planar Graphs // Graphs, algorithms, and optimization. — Boca Raton: 2005. — ISBN 978-1584883968
5. ↑ HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Проверено 9 января 2008.
6. ↑ http://citeseerx.ist.psu.edu/stats/authors?all=true

Библиографические ссылки

• 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

Ссылки

• DBLP: Robert Endre Tarjan
• Robert Tarjan’s home page at Princeton.
• Mathematics Genealogy Project entry for Robert Endre Tarjan.

Лауреаты премии Тьюринга

Перлис (1966) • Уилкс (1967) • Хэмминг (1968) • Минский (1969) • Уилкинсон (1970) • Маккарти (1971) • Дейкстра (1972) • Бахман (1973) • Кнут (1974) • Ньюэлл / Саймон (1975) • Рабин / Скотт (1976) • Бэкус (1977) • Флойд (1978) • Айверсон (1979) • Хоар (1980) • Кодд (1981) • Кук (1982) • Томпсон / Ритчи (1983) • Вирт (1984) • Карп (1985) • Хопкрофт / Тарьян (1986) • Кок (1987) • Сазерленд (1988) • Кэхэн (1989) • Корбато (1990) • Милнер (1991) • Лэмпсон (1992) • Хартманис / Стернс (1993) • Фейгенбаум / Редди (1994) • Блюм (1995) • Пнуели (1996) • Энгельбарт (1997) • Грей (1998) • Брукс (1999) • Яо (2000) • Даль / Нигаард (2001) • Ривест / Шамир / Адлеман (2002) • Кэй (2003) • Серф / Кан (2004) • Наур (2005) • Аллен (2006) • Кларк / Эмерсон / Сифакис (2007) • Лисков (2008)