Robert Tarjan
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ó
modificaVa 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
modificaTarjan é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
modificaTarjan é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
modificaTarjan 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- ↑ http://www.intertrust.com/robert-tarjan Arxivat 2016-05-29 a Wayback Machine.
- ↑ 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.
- ↑ «Robert Tarjan: The Art of the Algorithm». Hewlett-Packard. Arxivat de l'original el 2012-02-06. [Consulta: 5 setembre 2010].
- ↑ «Robert Endre Tarjan». Mathematics Genealogy Project. [Consulta: 9 gener 2008].
- ↑ Robert, Tarjan. «Curriculum Vitae».
- ↑ 6,0 6,1 «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,0 7,1 7,2 7,3 7,4 7,5 Turing award citation, ACM, retrieved 2014-01-19.
- ↑ 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.
- ↑ http://www.acm.org/awards/fellows_citations_n-z/tarjan.html
- ↑ Nevanlinna prize winners Arxivat 2008-12-27 a Wayback Machine., Unió Matemàtica Internacional, consulta 2014-01-19.
- ↑ http://media.caltech.edu/press_releases/13332 Arxivat 2010-10-10 a Wayback Machine.
Publicacions
modifica- 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
modifica- DBLP: Robert Endre Tarjan
- Web de Robert Tarjan a Princeton.
- Pàgina al Mathematics Genealogy Project de Robert Endre Tarjan.