Robert Tarjan

De Viquipèdia
Salta a: navegació, cerca
Infotaula de personaRobert Endre Tarjan
Bob Tarjan.jpg
Robert Tarjan, el 2010
Dades biogràfiques
Naixement 30 d'abril de 1948 (1948-04-30) (69 anys)
Pomona, Califòrnia
Residència Princeton
Nacionalitat Estats Units
Alma mater Caltech,
Stanford
Tesi [1972 An Efficient Planarity Algorithm]
Es coneix per Algorismes i estructures de dades
Activitat professional
Camp de treball Ciència computacional
Ocupació Informàtica
Organització Cornell
Berkeley
Stanford
New York University
Princeton
Hewlett-Packard
Microsoft
Intertrust
Premis i reconeixements
Modifica dades a Wikidata

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 co-autors 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. http://www.intertrust.com/robert-tarjan
  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. [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. [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. http://www.acm.org/awards/fellows_citations_n-z/tarjan.html
  10. Nevanlinna prize winners, Unió Matemàtica Internacional, consulta 2014-01-19.
  11. http://media.caltech.edu/press_releases/13332

Publicacions[modifica]

Enllaços externs[modifica]