Robert Tarjan

Robert Tarjan

Nom original	(en) Robert Endre Tarjan
Biografia
Naixement	30 abril 1948 (76 anys) Pomona (Califòrnia)
Residència	Princeton (1985–)
Formació	Institut Tecnològic de Califòrnia Universitat Stanford
Director de tesi	Robert Floyd
Activitat
Camp de treball	Ciència computacional i combinatòria
Ocupació	matemàtic, informàtic, professor d'universitat
Ocupador	Hewlett-Packard (2002–) Institut de Tecnologia de Massachusetts (1996–1996) Universitat de Princeton (1985–) Universitat de Nova York (1981–1985) Bell Labs (1980–1989) Universitat Stanford (1974–1980) Universitat de Califòrnia a Berkeley (1973–1975) Universitat Cornell (1972–1973)
Membre de	Societat de Matemàtiques Aplicades i Industrials (membre de la Societat de Matemàtiques Aplicades i Industrials) (2009–) Association for Computing Machinery (membre de l'Association for Computing Machinery) (1994–) Acadèmia Nacional d'Enginyeria Acadèmia Americana de les Arts i les Ciències Societat Filosòfica Americana Associació americana per l'avanç de la ciència Acadèmia Nacional de Ciències dels Estats Units
Influències	Martin Gardner
Obra
Estudiant doctoral	Daniel Sleator, Ramesh Sitaraman ^(en) , John Russell Gilbert ^(en) , Jeff Westbrook, Monika Henzinger, Thomas Lengauer, Bengt Ingemar Aspvall ^(en) , Jacabo Valdes Ayesta ^(en) , Konstantinos Tsioutsiouliklis ^(en) , Joan Marie Lucas ^(en) , Samuel Watkins Bent ^(en) , Heather D. Booth ^(en) , Xiaofeng Han ^(en) , Neal E. Young ^(en) , Adam L. Buchsbaum ^(en) , Brandon D. Dixon ^(en) , Lesley R. Matheson ^(en) , Haim Kaplan ^(en) , Peter N. Yianilos ^(en) , C. Gregory (Charles) Nelson ^(en) , Donald Roy Woods ^(en) , Neil Ivor Sarnak ^(en) , Warren Douglas Smith ^(en) , Loukas Georgiadis ^(en) , Renato Werneck ^(en) , Siddhartha Sen ^(en) , Caleb Levy ^(en) i Charles Gregory Nelson ^(en)
Premis
(2009)  membre de la Societat de Matemàtiques Aplicades i Industrials (1999)  premi Paris Kanellakis (1994)  membre de l'Association for Computing Machinery (1986)  Premi Turing (1984)  Premi Frederick W. Lanchester (1984)  Premi William O. Baker d'iniciatives de recerca (1982)  O'Reilly Open Source Award (1982)  Premi Nevanlinna (1978)  Beca Guggenheim

Robert Endre Tarjan (nascut el 30 d'abril de 1948) és un informàtic i matemàtic estatunidenc. És el descobridor d'uns quants algorismes sobre grafs, com l'algorisme dels mínims avantpassats comuns de Tarjan, i co-inventor dels arbres bisellats i els monticles de Fibonacci. Tarjan ocupa la càtedra McDonnell com a professor distingit d'Informàtica a la universitat de Princeton i és cap científic d'Intertrust Technologies.^[1]

Primers anys i educació

Va néixer a Pomona, Califòrnia. El seu pare era psiquiatre infantil, especialitzat en retard mental, i dirigia un hospital estatal.^[2] De nen, Tarjan llegia molta ciència-ficció i volia ser astrònom. Es va interessar en les matemàtiques en llegir la secció de jocs matemàtics de Martin Gardner al Scientific American. S'hi va interessar encara més als 12 anys, gràcies a un professor "molt estimulant".^[3]

Mentre era a l'institut, Tarjan va trobar feina amb màquines lectores de targetes perforades. Va treballar per primera vegada amb ordinadors de veritat durant un curs d'astronomia en un campus d'estiu (Summer Science Program) el 1964.^[2]

Tarjan es va llicenciar en matemàtiques a l'Institut Tecnològic de Califòrnia el 1969. A Stanford, va obtenir un màster en informàtica el 1971 i un doctorat en informàtica (parcial en matemàtiques) el 1972. A Stanford, el supervisaven Robert Floyd^[4] i Donald Knuth,^[5] tots dos informàtics cèlebres, i la seva tesi fou An Efficient Planarity Algorithm. Tarjan va triar la informàtica com a àrea d'interès perquè creia que era una manera de fer matemàtiques que podia tenir un impacte pràctic.^[6]

Carrera professional

Tarjan és professor a Princeton des de 1985.^[6] També ha treballat dins del món acadèmic a Cornell University (1972–73), la Universitat de Califòrnia a Berkeley (1973–1975), Stanford (1974–1980), i New York University (1981–1985). També va ser fellow del NEC Research Institute (1989–1997).^[7] L'abril de 2013 va entrar a Microsoft Research Silicon Valley conservant el lloc a Princeton. L'octubre de 2014 va tornar a Intertrust Technologies com a cap científic.

Tarjan ha treballat als AT&T Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014–actualitat), Compaq (2002) i Hewlett Packard (2006–2013).

Algorismes i estructures de dades

Tarjan és conegut per la seva feina pionera en algorismes i estructures de dades per als grafs. Alguns dels seus algorismes més coneguts són: l'algorisme dels mínims avantpassats comuns de Tarjan, i l'algorisme de Tarjan per components fortament connectats. Va ser un dels cinc coautors de l'algorisme de selecció en temps lineal de la mediana de les medianes. L'algorisme Hopcroft-Tarjan de prova de planaritat fou el primer algorisme en temps lineal per provar la planaritat.^[8]

Tarjan també ha desenvolupat estructures de dades importants com el monticle de Fibonacci (una estructura de dades en monticle que consisteix en un bosc d'arbres), i l'arbre bisellat (un arbre de cerca auto-ajustable; co-inventat per Tarjan i Daniel Sleator). Una altra contribució significativa fou l'anàlisi de la estructura de dades per a conjunts disjunts; fou el primer que va demostrar el temps d'execució òptim que implica la funció d'Ackermann inversa.

Premis

Tarjan va rebre el Premi Turing conjuntament amb John Hopcroft el 1986. La justificació del premi explica^[7] que fou:

«

Per assoliments fonamentals en el disseny i anàlisi d'algorismes i estructures de dades.

»

Tarjan també fou elegit ACM Fellow el 1994. La justificació d'aquest premi diu:^[9]

«

Per avenços pioners en el disseny i anàlisi d'estructures de dades i algorismes.

»

Altres premis que ha rebut Tarjan inclouen:

• Premi Nevanlinna de Ciències de la Informació (1983)^[7] – primer a rebre'l^[10]
• Premi de l'Acadèmia Nacional de Ciències per Iniciatives en la Recerca (1984)^[7]
• Premi Paris Kanellakis en Teoria i Pràctica, ACM (1999)^[7]
• Blaise Pascal Medal in Mathematics and Computer Science, Acadèmia Europea de Ciències (2004)^[7]
• Caltech Distinguished Alumni Award, California Institute of Technology (2010)^[11]

Referències

1. ^{[enllaç sense format]} http://www.intertrust.com/robert-tarjan Arxivat 2016-05-29 a Wayback Machine.
2. Shasha, Dennis Elliott; Lazere, Cathy A.. «Robert E. Tarjan: In Search of Good Structure». A: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Copernicus/Springer, 1998, p. 102–119. ISBN 978-0-387-97992-2. OCLC 32240355. 
3. «Robert Tarjan: The Art of the Algorithm». Hewlett-Packard. Arxivat de l'original el 2012-02-06. [Consulta: 5 setembre 2010].
4. «Robert Endre Tarjan». Mathematics Genealogy Project. [Consulta: 9 gener 2008].
5. Robert, Tarjan. «Curriculum Vitae».
6. «Robert Endre Tarjan: The art of the algorithm (interview)». Hewlett-Packard, 01-09-2004. Arxivat de l'original el 2012-02-06. [Consulta: 9 gener 2008].
7. Turing award citation, ACM, retrieved 2014-01-19.
8. Kocay, William; Kreher, Donald L. «Planar Graphs». A: Graphs, algorithms, and optimization. Boca Raton: Chapman & Hall/CRC, 2005, p. 312. ISBN 978-1-58488-396-8. OCLC 56319851. 
9. ^{[enllaç sense format]} http://www.acm.org/awards/fellows_citations_n-z/tarjan.html
10. Nevanlinna prize winners Arxivat 2008-12-27 a Wayback Machine., Unió Matemàtica Internacional, consulta 2014-01-19.
11. ^{[enllaç sense format]} http://media.caltech.edu/press_releases/13332 Arxivat 2010-10-10 a Wayback Machine.

Publicacions

• Tarjan, Robert E. Data structures and network algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 1983. ISBN 978-0-89871-187-5. OCLC 10120539. 
• Tarjan, Robert E.; Pólya, George; Woods, Donald R Notes on introductory combinatorics. Boston: Birkhauser, 1983. ISBN 978-0-8176-3170-3. OCLC 10018128. 
• Cerca d'OCLC per a Robert E Tarjan
• Secció a DBLP Arxivat 2012-10-17 a Wayback Machine. de Robert Endre Tarjan

Enllaços externs

• DBLP: Robert Endre Tarjan
• Web de Robert Tarjan a Princeton.
• Pàgina al Mathematics Genealogy Project de Robert Endre Tarjan.