Robert Tarjan

De la Viquipèdia, l'enciclopèdia lliure
Infotaula de personaRobert Tarjan

Modifica el valor a Wikidata
Nom original(en) Robert Endre Tarjan Modifica el valor a Wikidata
Biografia
Naixement30 abril 1948 Modifica el valor a Wikidata (75 anys)
Pomona (Califòrnia) Modifica el valor a Wikidata
Dades personals
FormacióInstitut Tecnològic de Califòrnia
Universitat de Stanford Modifica el valor a Wikidata
Director de tesiRobert Floyd Modifica el valor a Wikidata
Activitat
Camp de treballCiència computacional i combinatòria Modifica el valor a Wikidata
Ocupaciómatemàtic, informàtic, professor d'universitat Modifica el valor a Wikidata
OcupadorHewlett-Packard (2002–)
Institut de Tecnologia de Massachusetts (1996–1996)
Universitat de Princeton (1985–)
Universitat de Nova York (1981–1985)
Bell Labs (1980–1989)
Universitat de Stanford (1974–1980)
Universitat de Califòrnia a Berkeley (1973–1975)
Universitat Cornell (1972–1973) Modifica el valor a Wikidata
Membre de
Societat de Matemàtiques Aplicades i Industrials (membre de la Societat de Matemàtiques Aplicades i Industrials) (2009–)
Acadèmia Nacional d'Enginyeria
Association for Computing Machinery
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 Modifica el valor a Wikidata
Influències
Obra
Estudiant doctoralDaniel Sleator, Ramesh Sitaraman (en) Tradueix, John Russell Gilbert (en) Tradueix, Jeff Westbrook, Monika Henzinger, Thomas Lengauer, Bengt Ingemar Aspvall (en) Tradueix, Jacabo Valdes Ayesta (en) Tradueix, Konstantinos Tsioutsiouliklis (en) Tradueix, Joan Marie Lucas (en) Tradueix, Samuel Watkins Bent (en) Tradueix, Heather D. Booth (en) Tradueix, Xiaofeng Han (en) Tradueix, Neal E. Young (en) Tradueix, Adam L. Buchsbaum (en) Tradueix, Brandon D. Dixon (en) Tradueix, Lesley R. Matheson (en) Tradueix, Haim Kaplan (en) Tradueix, Peter N. Yianilos (en) Tradueix, C. Gregory (Charles) Nelson (en) Tradueix, Donald Roy Woods (en) Tradueix, Neil Ivor Sarnak (en) Tradueix, Warren Douglas Smith (en) Tradueix, Loukas Georgiadis (en) Tradueix, Renato Werneck (en) Tradueix, Siddhartha Sen (en) Tradueix, Caleb Levy (en) Tradueix i Charles Gregory Nelson (en) Tradueix Modifica el valor a Wikidata
Premis

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ó[modifica]

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[modifica]

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[modifica]

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[modifica]

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[modifica]

  1. ↑ [enllaç sense format] http://www.intertrust.com/robert-tarjan Arxivat 2016-05-29 a Wayback Machine.
  2. ↑ 2,0 2,1 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. ↑ 6,0 6,1 «Robert Endre Tarjan: The art of the algorithm (interview)». Hewlett-Packard, setembre 2004. Arxivat de l'original el 2012-02-06. [Consulta: 9 gener 2008].
  7. ↑ 7,0 7,1 7,2 7,3 7,4 7,5 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[modifica]

Enllaços externs[modifica]

Obtingut de «https://ca.wikipedia.org/w/index.php?title=Robert_Tarjan&oldid=30991138»