stringtranslate.com

Roberto Tarjan

Robert Endre Tarjan (nacido el 30 de abril de 1948) es un científico informático y matemático estadounidense . Es el descubridor de varios algoritmos de teoría de grafos , incluido su algoritmo de componentes fuertemente conectados , y coinventor de los árboles de dispersión y los montones de Fibonacci . Tarjan es actualmente profesor distinguido de Ciencias de la Computación James S. McDonnell en la Universidad de Princeton .

Vida personal y educación

Nació en Pomona, California . Su padre, George Tarjan (1912-1991), criado en Hungría, [1] era un psiquiatra infantil, especializado en retraso mental, y dirigía un hospital estatal. [2] El hermano menor de Robert Tarjan, James, se convirtió en gran maestro de ajedrez. [3] De niño, Robert Tarjan leía mucha ciencia ficción y quería ser astrónomo . Se interesó por las matemáticas después de leer la columna de juegos matemáticos de Martin Gardner en Scientific American . Se interesó seriamente por las matemáticas en octavo grado, gracias a un maestro "muy estimulante". [4]

Mientras estaba en la escuela secundaria, Tarjan consiguió un trabajo en el que trabajaba con las alzadoras de tarjetas perforadas de IBM. Trabajó por primera vez con computadoras reales mientras estudiaba astronomía en el Programa Científico de Verano en 1964. [2]

Tarjan obtuvo una licenciatura en matemáticas del Instituto de Tecnología de California en 1969. En la Universidad de Stanford , recibió su maestría en ciencias de la computación en 1971 y un doctorado en ciencias de la computación (con especialización en matemáticas) en 1972. En Stanford, fue supervisado por Robert Floyd [5] y Donald Knuth [6] , ambos científicos informáticos muy destacados, y su disertación de doctorado fue Un algoritmo de planaridad eficiente . Tarjan seleccionó la informática como su área de interés porque creía que la informática era una forma de hacer matemáticas que podría tener un impacto práctico. [7]

Tarjan vive actualmente en Princeton, Nueva Jersey, y Silicon Valley. Está casado con Nayla Rizk. [8] Tiene tres hijas: Alice Tarjan, Sophie Zawacki y Maxine Tarjan. [9]

Carrera de informática

Tarjan ha sido profesor en la Universidad de Princeton desde 1985. [7] También ha ocupado puestos académicos en la Universidad de Cornell (1972-73), la Universidad de California, Berkeley (1973-1975), la Universidad de Stanford (1974-1980) y la Universidad de Nueva York (1981-1985). También ha sido miembro del Instituto de Investigación NEC (1989-1997). [10] En abril de 2013 se incorporó a Microsoft Research Silicon Valley además de ocupar el puesto en Princeton. En octubre de 2014 se reincorporó a Intertrust Technologies como científico jefe.

Tarjan ha trabajado en AT&T Bell Labs (1980-1989), Intertrust Technologies (1997-2001, 2014-presente), Compaq (2002) y Hewlett Packard (2006-2013).

Algoritmos y estructuras de datos

Tarjan es conocido por su trabajo pionero en algoritmos de teoría de grafos y estructuras de datos. Algunos de sus algoritmos más conocidos incluyen el algoritmo de ancestros menos comunes fuera de línea de Tarjan , el algoritmo de componentes fuertemente conectados de Tarjan y el algoritmo de búsqueda de puentes de Tarjan , y fue uno de los cinco coautores del algoritmo de selección de tiempo lineal de mediana de medianas . El algoritmo de prueba de planaridad Hopcroft-Tarjan fue el primer algoritmo de tiempo lineal para pruebas de planaridad. [11]

Tarjan también ha desarrollado importantes estructuras de datos como el montículo de Fibonacci (una estructura de datos de montículo que consiste en un bosque de árboles) y el árbol splay (un árbol binario de búsqueda autoajustable; co-inventado por Tarjan y Daniel Sleator ). Otra contribución significativa fue el análisis de la estructura de datos de conjunto disjunto ; fue el primero en demostrar el tiempo de ejecución óptimo que involucra la función inversa de Ackermann . [12]

Premios

Tarjan recibió el premio Turing junto con John Hopcroft en 1986. La cita del premio indica [10] que fue:

Por logros fundamentales en el diseño y análisis de algoritmos y estructuras de datos.

Tarjan también fue elegido miembro de la ACM en 1994. La mención de este premio dice: [13]

Por avances fundamentales en el diseño y análisis de estructuras de datos y algoritmos.

Algunos de los otros premios que recibió Tarjan incluyen:

Publicaciones seleccionadas

Los artículos de Tarjan han sido citados colectivamente más de 94.000 veces. [20] Entre los más citados se encuentran:

Patentes

Tarjan posee al menos 18 patentes estadounidenses. [6] Estas incluyen:

Notas

  1. ^ "Destinatarios judíos del premio ACM AM Turing". jinfo.org .
  2. ^ ab Shasha, Dennis Elliott; Lazere, Cathy A. (1998) [1995]. "Robert E. Tarjan: En busca de una buena estructura". Fuera de sus mentes: Las vidas y descubrimientos de 15 grandes científicos informáticos . Copernicus/Springer. págs. 102–119. ISBN 978-0-387-97992-2.OCLC 32240355  .
  3. ^ Melvin, Shabsin (agosto de 1984). "George Tarjan, MD, centésimo duodécimo presidente, 1983-1984". The American Journal of Psychiatry . 141 (8): 931–934. doi :10.1176/ajp.141.8.931.
  4. ^ "Robert Tarjan: El arte del algoritmo". Hewlett-Packard . Consultado el 5 de septiembre de 2010 .
  5. ^ "Robert Endre Tarjan". Proyecto de genealogía matemática . Consultado el 9 de enero de 2008 .
  6. ^ ab Tarjan, Robert Endre (15 de noviembre de 2019). «Curriculum Vitae» (PDF) . Archivado desde el original (PDF) el 23 de noviembre de 2019. Consultado el 23 de noviembre de 2019 .
  7. ^ ab "Robert Endre Tarjan: El arte del algoritmo (entrevista)". Hewlett-Packard. Septiembre de 2004. Consultado el 9 de enero de 2008 .
  8. ^ "Nayla Rizk y Robert Tarjan". Los New York Times . Julio de 2013.
  9. ^ "Fotos del simposio por el 60º aniversario del nacimiento de Bob Tarjan". DIMACS. Mayo de 2008.
  10. ^ abcde King, V. "Robert E Tarjan — Ganador del premio AM Turing". ACM . Consultado el 19 de enero de 2014 .
  11. ^ Kocay, William; Kreher, Donald L (2005). "Gráficos planares". Gráficos, algoritmos y optimización . Boca Raton: Chapman & Hall/CRC. pág. 312. ISBN 978-1-58488-396-8.OCLC 56319851  .
  12. ^ Tarjan, Robert E. ; van Leeuwen, Jan (1984). "Análisis del peor caso de algoritmos de unión de conjuntos". Revista de la ACM . 31 (2): 245–281. doi : 10.1145/62.2160 . S2CID  5363073.
  13. ^ "Premio Fellows — Robert E. Tarjan". ACM . 25 de septiembre de 1998 . Consultado el 18 de noviembre de 2005 .
  14. ^ "Ganadores del premio Rolf Nevanlinna". Unión Matemática Internacional . Archivado desde el original el 2008-12-27 . Consultado el 2014-01-19 .
  15. ^ "Robert Endre Tarjan". Academia Estadounidense de las Artes y las Ciencias . Consultado el 15 de junio de 2020 .
  16. ^ "Robert Tarjan". www.nasonline.org . Consultado el 15 de junio de 2020 .
  17. ^ "Dr. Robert E. Tarjan". Sitio web de la NAE . Consultado el 15 de junio de 2020 .
  18. ^ "Historial de miembros de la APS". search.amphilsoc.org . Consultado el 19 de abril de 2022 .
  19. ^ "Caltech nombra a cinco exalumnos distinguidos" (Comunicado de prensa). Instituto Tecnológico de California . 15 de marzo de 2010. Archivado desde el original el 10 de octubre de 2010. Consultado el 26 de agosto de 2010 .
  20. ^ "Página de Google Académico de Robert Tarjan". Google Académico . Consultado el 6 de marzo de 2023 .
  21. ^ Tarjan, Robert (1 de junio de 1972). "Búsqueda en profundidad y algoritmos de grafos lineales". Revista SIAM de Computación . 1 (2): 146–160. doi :10.1137/0201010. ISSN  0097-5397. S2CID  16467262.
  22. ^ Fredman, Michael L.; Tarjan, Robert Endre (1 de julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes". Revista de la ACM . 34 (3): 596–615. doi : 10.1145/28869.28874 . ISSN  0004-5411. S2CID  7904683.
  23. ^ "Back Matter". Estructuras de datos y algoritmos de red : 125-131. Enero de 1983. doi :10.1137/1.9781611970265.bm. ISBN 978-0-89871-187-5.
  24. ^ Goldberg, Andrew V.; Tarjan, Robert E. (1 de octubre de 1988). "Un nuevo enfoque para el problema del flujo máximo". Revista de la ACM . 35 (4): 921–940. doi : 10.1145/48014.61051 . ISSN  0004-5411. S2CID  14492800.
  25. ^ Bentley, Jon L.; Sleator, Daniel DK; Tarjan, Robert E. (3 de enero de 1989). "Patente de los Estados Unidos 4796003 — Compactación de datos".
  26. ^ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (19 de octubre de 2010). "Patente de Estados Unidos 7818272: método para el descubrimiento de grupos de objetos en un gráfico arbitrario no dirigido utilizando una diferencia entre una fracción de conexiones internas y la fracción máxima de conexiones por un objeto externo".
  27. ^ Pinkas, Binyamin; Haber, Stuart A.; Tarjan, Robert E.; Sander, Tomas (10 de julio de 2012). "Patente de Estados Unidos 8220036: Establecimiento de un canal seguro con un usuario humano".

Referencias

Enlaces externos

Wikimedia Commons alberga una categoría multimedia sobre Robert Tarjan.