Роберт Андре Тарджан англ Robert Endre Tarjan народився 30 квітня 1948 у Помоні США американський науковець у галузі тео

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

Роберт Андре Тарджан
англ. Robert Endre Tarjan

Народився	30 квітня 1948(1948-04-30) (76 років) Помона, (штат Каліфорнія, США)
Місце проживання	Принстон
Країна	США^[1]^[2]^[…]
Діяльність	математик, інформатик, викладач університету
Alma mater	Каліфорнійський технологічний інститут Стенфордський університет
Галузь	Інформатика
Заклад	Корнелльський університет Принстонський університет Hewlett-Packard
Науковий керівник	Роберт Флойд, Дональд Кнут
Аспіранти, докторанти	Деніел Слітор ^d ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d^[4] ^d
Членство	Національна академія наук США Американське філософське товариство AAAS Американська академія мистецтв і наук Національна інженерна академія США Association for Computing Machinery^[5] Товариство з промислової та прикладної математики^[6]
Відомий завдяки:	Алгоритми та структури даних
Нагороди	Грант Ґуґґенгайма (1978) премія Тюрінга (1986) Премія Неванлінни (1982) Премія Канеллакіса (1999) O'Reilly Open Source Award (1982) ^d (1994) ^d (2009) ^d (1984) ^d (1984)
Роберт Андре Тарджан у Вікісховищі

Він є автором численних алгоритмів розв'язання задач з теорії графів і дискретної математики, зокрема алгоритм пошуку найменшого спільного предка (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), ^[en] (1997—2001), Compaq (2002) і Hewlett Packard, де продовжує працювати з 2006 р. Він обирався членом різних комітетів ACM і IEEE, а також працював редактором кількох сертифікованих журналів.

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

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

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

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

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

Нагороди

Тарджан отримав Премію Тюрінга разом з Джоном Гопкрофтом у 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.

Примітки

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.
d:Track:Q829984
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 . 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 . OCLC 56319851.
HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
Statistics — Most Cited Authors in Computer Science

Посилання

DBLP: Robert Endre Tarjan
Robert Tarjan's home page at Princeton.

Це незавершена стаття про науковця.
Ви можете проєкту, виправивши або дописавши її.

[[http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations_http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations]<span_class="wef_low_priority_links"></span><div_style="display:none"></div>-1] ttp://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations

[[http://www.in.com/robert-tarjan/profile-238439.html_http://www.in.com/robert-tarjan/profile-238439.html]<span_class="wef_low_priority_links"></span><div_style="display:none"></div>-2] ttp://www.in.com/robert-tarjan/profile-238439.html

[[http://link.springer.com/content/pdf/10.1007%2F978-3-642-15328-0_9.pdf_http://link.springer.com/content/pdf/10.1007%2F978-3-642-15328-0_9.pdf]<span_class="wef_low_priority_links"></span><div_style="display:none"></div>-3] ttp://link.springer.com/content/pdf/10.1007%2F978-3-642-15328-0_9.pdf

[<span_class="wikidata_cite_citetype_Q7094076_citetype_Q33002955_citetype_Q114955954"_data-entity-id="Q829984">Математичний_генеалогічний_проєкт<span_class="wef_low_priority_links">_—_1997.</span></span><div_style="display:none">[[d:Track:Q829984]]</div>-4] Математичний генеалогічний проєкт — 1997.
d:Track:Q829984

[[https://awards.acm.org/fellows/award-recipients_https://awards.acm.org/fellows/award-recipients]<span_class="wef_low_priority_links"></span><div_style="display:none"></div>-5] ttps://awards.acm.org/fellows/award-recipients

[[https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows_https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows]<span_class="wef_low_priority_links"></span><div_style="display:none"></div>-6] ttps://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows

[Out_of_Their_Minds-7] 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 . OCLC 32240355.

[8] Robert Endre Tarjan. Mathematics Genealogy Project. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.

[HP_art_of_algo-9] Robert Endre Tarjan: The art of the algorithm (interview). Hewlett-Packard. September 2004. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.

[10] Kocay, William; Kreher, Donald L (2005). Planar Graphs. Graphs, algorithms, and optimization. Boca Raton. с. 312. ISBN . OCLC 56319851.

[HPfellow-11] HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.

[12] Statistics — Most Cited Authors in Computer Science

[1]

[2]

[4]

[5]

[6]