Роберт Андре Тарджан

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

Роберт Андре Тарджан
англ. Robert Endre Tarjan
Народився 30 квітня 1948(1948-04-30) (73 роки)
Помона, (штат Каліфорнія, США)
Місце проживання Принстон
Країна  США[1][2][…]
Діяльність математик, інформатик, викладач університету, науковець, дослідник
Alma mater Каліфорнійський технологічний інститут
Стенфордський університет
Галузь Інформатика
Заклад Корнелльський університет
Принстонський університет
Hewlett-Packard
Науковий керівник Роберт Флойд,
Дональд Кнут
Аспіранти, докторанти Деніел Слітор, Ramesh Sitaramand, John Russell Gilbertd[3], Jeff Westbrookd[3], Monika Henzingerd[3], Thomas Lengauerd[3], Bengt Ingemar Aspvalld[3], Jacabo Valdes Ayestad[3], Konstantinos Tsioutsiouliklisd[3], Joan Marie Lucasd[3], Samuel Watkins Bentd[3], Heather D. Boothd[3], Xiaofeng Hand[3], Neal Eric Youngd[3], Adam L. Buchsbaumd[3], Brandon D. Dixond[3], Lesley R. Mathesond[3], Haim Kapland[3], Peter Nicholas Yianilosd[3], C. Gregory (Charles) Nelsond[3], Donald Roy Woodsd[3], Neil Ivor Sarnakd[3], Warren Douglas Smithd[3], Loukas Georgiadisd[3], Renato Werneckd[3], Siddhartha Send[3], Caleb Levyd[3] і Charles Gregory Nelsond
Членство Національна академія наук США, Американське філософське товариство, AAAS, Американська академія мистецтв і наук, Національна інженерна академія США, Association for Computing Machinery і Society for Industrial and Applied Mathematics[4]
Відомий завдяки: Алгоритми та структури даних
Нагороди Премія Неванлінни (1982)
Премія Тюрінга (1986)
 Роберт Андре Тарджан у Вікісховищі

Він є автором численних алгоритмів розв'язання задач з теорії графів і дискретної математики, зокрема алгоритм пошуку найменшого спільного предка (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 співробітник) у 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. Математична генеалогія — 1997.
  4. https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows
  5. 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.
  6. Robert Endre Tarjan. Mathematics Genealogy Project. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
  7. Robert Endre Tarjan: The art of the algorithm (interview). Hewlett-Packard. September 2004. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
  8. Kocay, William; Kreher, Donald L (2005). Planar Graphs. Graphs, algorithms, and optimization. Boca Raton. с. 312. ISBN 978-1584883968. OCLC 56319851.
  9. HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
  10. Statistics — Most Cited Authors in Computer Science

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.