Роберт Андре Тарджан (англ. Robert Endre Tarjan; народився 30 квітня 1948, у Помоні, США) — американський науковець у галузі теорії обчислювальних систем.
Роберт Андре Тарджан | |
---|---|
англ. Robert Endre Tarjan | |
![]() | |
Народився | 30 квітня 1948 (76 років) Помона, (штат Каліфорнія, США) |
Місце проживання | Принстон |
Країна | ![]() |
Діяльність | математик, інформатик, викладач університету |
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] |
Відомий завдяки: | Алгоритми та структури даних |
Нагороди | |
Він є автором численних алгоритмів розв'язання задач з теорії графів і дискретної математики, зокрема алгоритм пошуку найменшого спільного предка (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.
- 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.
![]() | Це незавершена стаття про науковця. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Robert Andre Tardzhan angl Robert Endre Tarjan narodivsya 30 kvitnya 1948 u Pomoni SShA amerikanskij naukovec u galuzi teoriyi obchislyuvalnih sistem Robert Andre Tardzhanangl Robert Endre TarjanNarodivsya30 kvitnya 1948 1948 04 30 76 rokiv Pomona shtat Kaliforniya SShA Misce prozhivannyaPrinstonKrayina SShA 1 2 Diyalnistmatematik informatik vikladach universitetuAlma materKalifornijskij tehnologichnij institut Stenfordskij universitetGaluzInformatikaZakladKornellskij universitet Prinstonskij universitet Hewlett PackardNaukovij kerivnikRobert Flojd Donald KnutAspiranti doktorantiDeniel Slitor 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 dChlenstvoNacionalna akademiya nauk SShA Amerikanske filosofske tovaristvo AAAS Amerikanska akademiya mistectv i nauk Nacionalna inzhenerna akademiya SShA Association for Computing Machinery 5 Tovaristvo z promislovoyi ta prikladnoyi matematiki 6 Vidomij zavdyaki Algoritmi ta strukturi danihNagorodiGrant Guggengajma 1978 premiya Tyuringa 1986 Premiya Nevanlinni 1982 premiya Kanellakisa 1999 O Reilly Open Source Award 1982 d 1994 d 2009 d 1984 d 1984 Robert Andre Tardzhan u Vikishovishi Vin ye avtorom chislennih algoritmiv rozv yazannya zadach z teoriyi grafiv i diskretnoyi matematiki zokrema algoritm poshuku najmenshogo spilnogo predka Tarjan s off line least common ancestors algorithm Takozh vin ye spivavtorom struktur danih Fibonachchiyeva kupa i Rozshiryuvane derevo OsvitaBatko Roberta Tardzhana buv dityachim likarem sho specializuvavsya na zatrimkah rozumovogo rozvitku i keruvav likarneyu shtatu Molodshij brat Dzhejms Tardzhan shahovij grosmejster U ditinstvi chitav bagato naukovoyi fantastiki i hotiv stati astronomom Vin zacikavivsya matematikoyu pislya prochitannya zamitok Martina Gardnera z matematichnih igor v zhurnali Scientific American Serjoznij interes do matematiki vinik u vosmomu klasi zavdyaki duzhe motivuyuchimu vchitelyu Pid chas navchannya v shkoli Tardzhan poshastilo popracyuvati v IBM z sortuvalno pidbiralnoyu mashinoyu dlya perfokart 1964 roku v litnij shkoli vin otrimav pershij serjoznij dosvid roboti zi spravzhnimi komp yuterami Tardzhan otrimav zvannya bakalavra z matematiki v Kalifornijskomu tehnologichnomu instituti California Institute of Technology v 1969 roci U Stenfordskomu universiteti vin otrimav stupin magistra z komp yuternih nauk u 1971 i stupin doktora filosofiyi Doctor of Philosophy v komp yuternih naukah u 1972 r Jogo naukovimi kerivnikami v Stenfordi buli Robert Flojd i Donald Knut Disertaciya Tardzhana nazivalasya Efektivnij algoritm viznachennya planarnosti grafa An Efficient Planarity Algorithm Tardzhan vibrav kompyuternu nauku yak shlyah na yakomu matematika zmozhe prinesti vidchutnu korist na praktici a ne lishe v teoriyi Kar yeraTardzhan pracyuye vikladachem v Prinstonskomu universiteti pochinayuchi z 1985 roku U nogo takozh buli akademichni posadi u Kornellskomu universiteti 1972 1973 Universiteti Kaliforniyi Berkli 1973 1975 Stenfordskomu universiteti 1974 1980 Nyu Jorkskomu universiteti 1981 1985 Vin takozh buv chlenom NEC Research Institute 1989 1997 i chislitsya na posadi Visiting Scientist v Massachusetskomu tehnologichnomu institi 1996 Tardzhan pracyuvav v AT amp T Bell Labs 1980 1989 en 1997 2001 Compaq 2002 i Hewlett Packard de prodovzhuye pracyuvati z 2006 r Vin obiravsya chlenom riznih komitetiv ACM i IEEE a takozh pracyuvav redaktorom kilkoh sertifikovanih zhurnaliv Algoritmi ta strukturi danih Tardzhan vigadav bezlich efektivnih algoritmiv i struktur danih dlya virishennya riznih prikladnih zadach Vin opublikuvav bilsh nizh 228 statej u sertifikovanih zhurnalah i monografiyah Tardzhan vidomij svoyimi revolyucijnimi pracyami v galuzi algoritmiv na grafah Najbilsh yaskravi z nih oflajnovij algoritm Tardzhana dlya znahodzhennya najmenshogo spilnogo predka dlya bagatorazovogo shvidkogo poshuku najglibshogo vuzla dereva sho ye spilnim predkom dvoh zadanih vuzliv i Algoritm Tardzhana dlya obchislennya silno zv yazkovih komponentiv Algoritm Gopkrofta Tardzhana stav pershim linijnim algoritmom viznachennya planarnosti grafa Tardzhan rozrobiv ryad najbilsh vazhlivih struktur danih takih yak Fibonachchiyeva kupa Sistema neperetinnih mnozhin i Rozshiryuvane derevo angl splay tree odin iz vidiv zbalansovanogo dvijkovogo dereva poshuku u spivavtorstvi z Danilom Slejterom Sogodni Robert Tardzhan viznanij profesor komp yuternih nauk James S McDonnell Distinguished University Professor of Computer Science v universiteti Prinstona a takozh pracyuye v Hewlett Packard NagorodiTardzhan otrimav Premiyu Tyuringa razom z Dzhonom Gopkroftom u 1986 r U suprovidnomu teksti do nagorodi napisano Za fundamentalni rezultati v galuzi rozrobki ta analizu algoritmiv i struktur danih Tardzhan takozh buv obranij chlenom ACM ACM spivrobitnik u 1994 r U vitalnomu teksti 1 zaznacheno Za plidnu pracyu v galuzyah rozrobki i analizu algoritmiv i struktur danih Inshi nagorodi Roberta Tardzhana Premiya Nevanlinni 1982 pershij laureat ciyeyi premiyi 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 Naprikinci lyutogo 2009 roku Tardzhan zajmav 39 misce u spisku najcitovanishih avtoriv u proekti CiteSeer Primitkihttp 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 Matematichnij genealogichnij proyekt 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 s 102 119 ISBN 978 0387979922 OCLC 32240355 Robert Endre Tarjan Mathematics Genealogy Project Arhiv originalu za 17 bereznya 2012 Procitovano 9 sichnya 2008 Robert Endre Tarjan The art of the algorithm interview Hewlett Packard September 2004 Arhiv originalu za 17 bereznya 2012 Procitovano 9 sichnya 2008 Kocay William Kreher Donald L 2005 Planar Graphs Graphs algorithms and optimization Boca Raton s 312 ISBN 978 1584883968 OCLC 56319851 HP Fellows Robert Endre Tarjan Hewlett Packard Arhiv originalu za 17 bereznya 2012 Procitovano 9 sichnya 2008 Statistics Most Cited Authors in Computer SciencePosilannyaDBLP Robert Endre Tarjan Robert Tarjan s home page at Princeton Ce nezavershena stattya pro naukovcya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi