WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
Роберт Андре Тарьян
англ. Robert Endre Tarjan
Дата рождения 30 апреля 1948(1948-04-30) (70 лет)
Место рождения Помона (штат Калифорния, США)
Страна
Научная сфера Информатика
Место работы Принстонский университет
Hewlett-Packard
Альма-матер Калифорнийский технологический институт,
Стэнфордский университет
Научный руководитель Роберт Флойд[4]
Награды и премии Премия Неванлинны (1982)
Премия Тьюринга (1986)
 Роберт Андре Тарьян на Викискладе

Роберт Андре Тарьян (англ. Robert Endre Tarjan; род. 30 апреля 1948, Помона, США) — известный американский учёный в области теории вычислительных систем.

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

Образование

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

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

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

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

Карьера

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

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

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

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

Награды

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

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

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

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

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

  • Премия Неванлинны (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[10].

Примечания

  1. ↑ http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations
  2. ↑ http://www.in.com/robert-tarjan/profile-238439.html
  3. ↑ http://link.springer.com/content/pdf/10.1007%2F978-3-642-15328-0_9.pdf
  4. ↑ Математическая генеалогия — 1997.
  5. 1 2 Shasha, Dennis Elliott. Robert E. Tarjan: In Search of Good Structure // Out of Their Minds: The Lives and Discoveries of 15 Great Computer. — 1998. — P. 102-119. — ISBN 978-0387979922.
  6. ↑ Robert Endre Tarjan. Mathematics Genealogy Project. Проверено 9 января 2008. Архивировано 17 марта 2012 года.
  7. 1 2 Robert Endre Tarjan: The art of the algorithm (interview). Hewlett-Packard (September 2004). Проверено 9 января 2008. Архивировано 17 марта 2012 года.
  8. ↑ Kocay, William. Planar Graphs // Graphs, algorithms, and optimization. — Boca Raton, 2005. — P. 312. — ISBN 978-1584883968.
  9. ↑ HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Проверено 9 января 2008. Архивировано 17 марта 2012 года.
  10. ↑ Statistics — Most Cited Authors in Computer Science

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

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии