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

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

Грант Ґуґґенгайма (1978)

премія Тюрінга (1986)

Премія Неванлінни (1982)

Премія Канеллакіса (1999)

O'Reilly Open Source Award (1982)

Дійсний член ACMd (1994)

член Товариства промислової та прикладної математикиd (2009)

Frederick W. Lanchester Prized (1984)

William O. Baker Award for Initiatives in Researchd (1984)

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

Роберт Андре Тарджан (англ. 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].

Примітки

  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. ↑ а б в г д е ж и к л м н п р с т у ф х ц ш щ ю я аа Математичний генеалогічний проєкт — 1997.
  5. ↑ https://awards.acm.org/fellows/award-recipients
  6. ↑ https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows
  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 978-0387979922. OCLC 32240355.
  8. ↑ Robert Endre Tarjan. Mathematics Genealogy Project. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
  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 978-1584883968. OCLC 56319851.
  11. ↑ HP Fellows: Robert Endre Tarjan. Hewlett-Packard. Архів оригіналу за 17 березня 2012. Процитовано 9 січня 2008.
  12. ↑ Statistics — Most Cited Authors in Computer Science

Посилання

Леонард Макс Адлеман, Вітфілд Діффі, Мартін Геллман, Ральф Меркле, Рональд Рівест, Аді Шамір (1996) · Авраам Лемпель, Яков Зів (1997) · Рендел Брайнт, Едмунд Мельсон Кларк, Ернест Аллен Емерсон, Кеннет Макміллан[de] (1998) · Деніел Слітор, Роберт Андре Тарджан (1999) · Нарендра Кармаркар (2000) · Юджин Майерс[en] (2001) · Пітер Франачек (2002) · Ґері Міллер / Міхаель Ошер Рабін / Роберт Соловей / Фолькер Штрассен (2003) · Йоав Фройнд[en] / Роберт Шапіро (2004) · Джерард Гольцманн / Роберт Куршам[de] / Моше Варді / П'єр Вольпе[en] (2005) · Роберт Брайтон (2006) · Бруно Бухбергер (2007) · Корінна Кортес, Володимир Вапник (2008) · Міхір Беллар [en], Філліп Рогавей [en] (2009) · Курт Мельгорн (2010) · Ханан Самет [en] (2011) · Андрей Бродер, Мозес Чарикар, Пьотр Індик (2012) · Роберт Блюмоф, Чарльз Ерік Лейзерсон (2013) · Джеймс Деммел (2014) · Майкл Лабі (2015) · Амос Фіат[en], Моні Наор[en] (2016) · Скотт Шенкер[en] (2017) · Певзнер Павло Аркадійович[en] (2018) · Нога Алон, Пилип Гібонс[en], Йоші Матіас[en], Маріо Жегеді[en] (2019) · Йосі Азар, Андрей Бродер, Анна Карлін[en], Міхаель Міценмахер[en] та Елі Апфал[en] (2020) · Аврім Блюм[en], Іріт Дінур, Синтія Дворк, Френк МакШеррі[en], Коббі Нісім[en] та Адам Д. Сміт[en] (2021) ·


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