Тар'я, Роберт

Роберт Андре Тар'я ( англ. Robert Endre Tarjan , 30 квітня 1948, Помона, США) - відомий американський учений у галузі теорії обчислювальних систем.

Він є автором безлічі алгоритмів розв'язання задач теорії графів і дискретної математики, включаючи алгоритм пошуку найменшого спільного предка (Tarjan's off-line least common ancestors algorithm). Також він є співавтором структур даних " Фібоначчіева купа "і" Splay-дерево ".


1. Освіта

Батько Роберта Тар'я був дитячим лікарем, що спеціалізується на затримках розумового розвитку, і був керуючим центральної поліклініки штату [1].

У дитинстві Тар'я читав багато наукової фантастики і хотів стати астрономом. Він зацікавився математикою після прочитання заміток Мартіна Гарднера по математичним іграм в журналі Scientific American. Серйозний інтерес до математики був щеплений у восьмому класі "дуже мотивуючим" вчителем.

Під час навчання в школі Тарьяну пощастило попрацювати в IBM з сортувальний-подборочних машиною для перфокарт. У 1964 році в літній школі він отримав перший серйозний досвід роботи з справжніми комп'ютерами [1].

Тар'я отримав звання бакалавра з математики в технологічному інституті Каліфорнії (California Institute of Technology) в 1969 році. У Стенфордському університеті він отримав магістерську ступінь з комп'ютерних наук ( 1971) і ступінь доктора філософії (Doctor of Philosophy) в комп'ютерних науках - в 1972 р. Його науковими керівниками в Стенфорді були Роберт Флойд і Дональд Кнут, дисертація називалася "Ефективний алгоритм визначення планарності графа" (An Efficient Planarity Algorithm) [2]. Тар'я вибрав комп'ютерну науку як шлях, на якому математика зможе принести відчутну практичну користь [3].


2. Кар'єра

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


2.1. Алгоритми і структури даних

Тар'я придумав безліч ефективних алгоритмів і структур даних для вирішення різних прикладних задач. Він опублікував понад 228 статей у реферованих журналах і монографіях.

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

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

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


3. Нагороди

Тар'я отримав Премію Тьюрінга разом з Джоном Хопкрофтом в 1986 р. У супровідному тексті до нагороди написано:

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

Тар'я також був обраний членом ACM (ACM Fellow) в 1994. У вітальному тексті [1] зазначено:

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

Інші нагороди Роберта Тар'я:

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


Примітки

  1. 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
  2. Robert Endre Tarjan - genealogy.math.ndsu.nodak.edu / id.php? id = 53460. Mathematics Genealogy Project. Читальний - www.webcitation.org/66EYpUnG3 з першоджерела 17 березня 2012.
  3. 1 2 Robert Endre Tarjan: The art of the algorithm (interview) - www.hpl.hp.com/news/2004/oct_dec/tarjan.html. Hewlett-Packard (September 2004). Читальний - www.webcitation.org/66EYq6UYp з першоджерела 17 березня 2012.
  4. Kocay William Planar Graphs / / Graphs, algorithms, and optimization. - Boca Raton, 2005. - P. 312. - ISBN 978-1584883968
  5. HP Fellows: Robert Endre Tarjan - www.hpl.hp.com / about / honors / HPfellows / tarjan.html. Hewlett-Packard. Читальний - www.webcitation.org/66EYqjOid з першоджерела 17 березня 2012.
  6. Statistics - Most Cited Authors in Computer Science - citeseerx.ist.psu.edu / stats / authors? all = true

5. Бібліографічні посилання

  • Tarjan Robert E. Data structures and network algorithms. - Philadelphia, 1983. - ISBN 978-0898711875
  • Tarjan Robert E. Notes on introductory combinatorics. - Boston, 1983. - ISBN 978-0817631703
  • OCLC entries - worldcat.org / search? q = au: Robert E Tarjan for Robert E Tarjan
  • DBLP entry - www.informatik.uni-trier.de/ ~ ley / db / indices / a-tree / t / Tarjan: Robert_Endre.html for Robert Endre Tarjan