Відкрити головне меню

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

Роберт Андре Тарджан
англ. Robert Endre Tarjan
Bob Tarjan.jpg
Народився 30 квітня 1948(1948-04-30) (71 рік)
Помона, (штат Каліфорнія, США)
Місце проживання
Громадянство
(підданство)
Flag of the United States.svg США[1][2][…]
Діяльність математик, інформатик, викладач університету, науковець
Alma mater Каліфорнійський технологічний інститут
Стенфордський університет
Сфера інтересів Інформатика
Заклад Корнелльський університет
Принстонський університет
Hewlett-Packard
Науковий керівник Роберт Флойд,
Дональд Кнут
Аспіранти, докторанти Деніел Слітор і Ramesh Sitaraman[d]
Член Національна академія наук США, Американське філософське товариство, Американська асоціація сприяння розвитку науки, Американська академія мистецтв і наук, Національна інженерна академія США[d] і Association for Computing Machinery
Відомий завдяки: Алгоритми та структури даних
Нагороди Премія Неванлінни (1982)
Премія Тюрінга (1986)

Роберт Андре Тарджан у Вікісховищі?

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

ОсвітаРедагувати

Батько Роберта Тарджана був дитячим лікарем, що спеціалізувався на затримках розумового розвитку, і керував лікарнею штату[4]. Молодший брат, Джеймс Тарджан — шаховий гросмейстер.

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

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

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

Кар'єраРедагувати

Тарджан працює викладачем в Принстонському університеті починаючи з 1985 року[6]. У нього також були академічні посади у Корнелльському університеті (1972—1973), Університеті Каліфорнії (Берклі) (1973—1975), Стенфордському університеті (1974—1980), Нью-Йоркському університеті (1981—1985). Він також був членом NEC Research Institute (1989—1997) і числиться (на посади Visiting Scientist) в Массачусетському технологічному інститі (1996).

Тарджан працював в AT&T Bell Labs (1980—1989), InterTrust Technologies[en] (1997—2001), Compaq (2002) і Hewlett Packard, де продовжує працювати з 2006 р. Він обирався членом різних комітетів ACM і IEEE, а також працював редактором кількох сертифікованих журналів.

Алгоритми та структури данихРедагувати

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

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

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

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

НагородиРедагувати

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

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

Тарджан також був обраний членом ACM (ACM співробітник) у 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[9].

ПриміткиРедагувати

  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. а б Shasha, Dennis Elliott; Lazere, Cathy A. (1998) [1995]. Robert E. Tarjan: In Search of Good Structure. Out of Their Minds: The Lives and Discoveries of 15 Great Computer. с. 102-119. ISBN 978-0387979922. OCLC 32240355. 
  5. Robert Endre Tarjan. Mathematics Genealogy Project. Архів оригіналу за 2012-03-17. Процитовано 2008-01-09. 
  6. а б Robert Endre Tarjan: The art of the algorithm (interview). Hewlett-Packard. September 2004. Архів оригіналу за 2012-03-17. Процитовано 2008-01-09. 
  7. Kocay, William; Kreher, Donald L (2005). Planar Graphs. Graphs, algorithms, and optimization. Boca Raton. с. 312. ISBN 978-1584883968. OCLC 56319851. 
  8. HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Архів оригіналу за 2012-03-17. Процитовано 2008-01-09. 
  9. Statistics — Most Cited Authors in Computer Science

ПосиланняРедагувати