Роберт Андре Тарджан (; народився 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), (1997—2001), Compaq (2002) і Hewlett Packard, де продовжує працювати з 2006 р. Він обирався членом різних комітетів ACM і IEEE, а також працював редактором кількох сертифікованих журналів.
Алгоритми та структури даних Тарджан вигадав безліч ефективних алгоритмів і структур даних для вирішення різних прикладних задач. Він опублікував більш ніж 228 статей у сертифікованих журналах і монографіях.
Тарджан відомий своїми революційними працями в галузі алгоритмів на графах. Найбільш яскраві з них — офлайновий алгоритм Тарджана для знаходження найменшого спільного предка, для багаторазового швидкого пошуку найглибшого вузла дерева, що є спільним предком двох заданих вузлів, і Алгоритм Тарджана для обчислення сильно зв'язкових компонентів. Алгоритм Гопкрофта - Тарджана став першим лінійним алгоритмом визначення планарності графа.
Тарджан розробив ряд найбільш важливих структур даних, таких як «Фібоначчієва купа», «Система неперетинних множин» і «Розширюване дерево» () (один із видів збалансованого двійкового дерева пошуку; у співавторстві з Данилом Слейтером).
Сьогодні Роберт Тарджан визнаний професор комп'ютерних наук (James S. McDonnell Distinguished University Professor of Computer Science) в університеті Принстона, а також працює в Hewlett-Packard.
Нагороди Тарджан отримав Премію Тюрінга разом з Джоном Гопкрофтом у 1986 р. У супровідному тексті до нагороди написано:
«За фундаментальні результати в галузі розробки та аналізу алгоритмів і структур даних.»
Тарджан також був обраний членом ACM (ACM співробітник) у 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 місце у списку найцитованіших авторів у проекті CiteSeerStatistics — Most Cited Authors in Computer Science.
Примітки
Посилання DBLP: Robert Endre Tarjan Robert Tarjan's home page at Princeton.