Роберт Андре Тарджан
Роберт Андре Тарджан (англ. Robert Endre Tarjan; народився 30 квітня 1948, у Помоні, США) — американський науковець у галузі теорії обчислювальних систем.
Він є автором численних алгоритмів розв'язання задач з теорії графів і дискретної математики, зокрема алгоритм пошуку найменшого спільного предка (Tarjan's off-line least common ancestors algorithm). Також він є співавтором структур даних «Фібоначчієва купа» і «Розширюване дерево».
Батько Роберта Тарджана був дитячим лікарем, що спеціалізувався на затримках розумового розвитку, і керував лікарнею штату[7]. Молодший брат, Джеймс Тарджан — шаховий гросмейстер.
У дитинстві читав багато наукової фантастики і хотів стати астрономом. Він зацікавився математикою після прочитання заміток Мартіна Гарднера з математичних ігор, в журналі Scientific American. Серйозний інтерес до математики виник у восьмому класі, завдяки «дуже мотивуючиму» вчителю.
Під час навчання в школі, Тарджан пощастило попрацювати в IBM з сортувально-підбиральною машиною для перфокарт. 1964 року, в літній школі він отримав перший серйозний досвід роботи зі справжніми комп'ютерами[7].
Тарджан отримав звання бакалавра з математики в Каліфорнійському технологічному інституті (California Institute of Technology) в 1969 році. У Стенфордському університеті він отримав ступінь магістра з комп'ютерних наук у 1971 і ступінь доктора філософії (Doctor of Philosophy) в комп'ютерних науках у 1972 р. Його науковими керівниками в Стенфорді були Роберт Флойд і Дональд Кнут. Дисертація Тарджана називалася «Ефективний алгоритм визначення планарності графа» (An Efficient Planarity Algorithm)[8]. Тарджан вибрав компьютерну науку, як шлях, на якому математика зможе принести відчутну користь на практиці, а не лише в теорії[9].
Тарджан працює викладачем в Принстонському університеті починаючи з 1985 року[9]. У нього також були академічні посади у Корнелльському університеті (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 статей у сертифікованих журналах і монографіях.
Тарджан відомий своїми революційними працями в галузі алгоритмів на графах. Найбільш яскраві з них — офлайновий алгоритм Тарджана для знаходження найменшого спільного предка, для багаторазового швидкого пошуку найглибшого вузла дерева, що є спільним предком двох заданих вузлів, і Алгоритм Тарджана для обчислення сильно зв'язкових компонентів. Алгоритм Гопкрофта - Тарджана став першим лінійним алгоритмом визначення планарності графа[10].
Тарджан розробив ряд найбільш важливих структур даних, таких як «Фібоначчієва купа», «Система неперетинних множин» і «Розширюване дерево» (англ. splay tree) (один із видів збалансованого двійкового дерева пошуку; у співавторстві з Данилом Слейтером).
Сьогодні Роберт Тарджан визнаний професор комп'ютерних наук (James S. McDonnell Distinguished University Professor of Computer Science) в університеті Принстона, а також працює в Hewlett-Packard[11].
Тарджан отримав Премію Тюрінга разом з Джоном Гопкрофтом у 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[12].
- ↑ http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations
- ↑ http://www.in.com/robert-tarjan/profile-238439.html
- ↑ http://link.springer.com/content/pdf/10.1007%2F978-3-642-15328-0_9.pdf
- ↑ а б в г д е ж и к л м н п р с т у ф х ц ш щ ю я аа Математичний генеалогічний проєкт — 1997.
- ↑ https://awards.acm.org/fellows/award-recipients
- ↑ https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows
- ↑ а б 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.
- ↑ Robert Endre Tarjan. Mathematics Genealogy Project. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
- ↑ а б Robert Endre Tarjan: The art of the algorithm (interview). Hewlett-Packard. September 2004. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
- ↑ Kocay, William; Kreher, Donald L (2005). Planar Graphs. Graphs, algorithms, and optimization. Boca Raton. с. 312. ISBN 978-1584883968. OCLC 56319851.
- ↑ HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
- ↑ Statistics — Most Cited Authors in Computer Science
|
Це незавершена стаття про науковця. Ви можете допомогти проєкту, виправивши або дописавши її. |
- Народились 30 квітня
- Народились 1948
- Члени і члени-кореспонденти Національної академії наук США
- Члени Американського філософського товариства
- Члени Американської асоціації сприяння розвитку науки
- Члени Американської академії мистецтв і наук
- Отримувачі гранту Ґуґґенгайма
- Лауреати премії Тюрінга
- Лауреати премії Невалінни
- Лауреати премії Канеллакіса
- Дійсні члени ACM
- Члени Товариства з промислової та прикладної математики
- Програмісти США
- Математики США
- Науковці Принстонського університету
- Уродженці Помони
- Члени Національної інженерної академії США
- Випускники Каліфорнійського технологічного інституту