stringtranslate.com

Robert Tarjan

Robert Endre Tarjan (nacido el 30 de abril de 1948) es un 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 co-inventor de los árboles splay 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, criado en Hungría, [1] era psiquiatra infantil, especializado en retraso mental, y dirigía un hospital estatal. [2] Cuando era niño, Tarjan leyó 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 una profesora "muy estimulante". [3]

Mientras estaba en la escuela secundaria, Tarjan consiguió un trabajo, donde trabajó con alzadoras de tarjetas perforadas de IBM. Trabajó por primera vez con computadoras reales mientras estudiaba astronomía en el Programa de Ciencias 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 [4] y Donald Knuth , [5] ambos científicos informáticos muy destacados, y su doctorado. La disertación 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 podía tener un impacto práctico. [6]

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

carrera de informatica

Tarjan ha estado enseñando en la Universidad de Princeton desde 1985. [6] También ocupó cargos 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. Universidad (1981-1985). También ha sido miembro del Instituto de Investigación NEC (1989-1997). [9] En abril de 2013 se incorporó a Microsoft Research Silicon Valley, además del 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 y el algoritmo de componentes fuertemente conectados 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 de Hopcroft-Tarjan fue el primer algoritmo de tiempo lineal para pruebas de planaridad. [10]

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

Premios

Tarjan recibió el Premio Turing junto con John Hopcroft en 1986. La cita del premio establece [9] que era:

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

Tarjan también fue elegido miembro de ACM en 1994. La cita de este premio dice: [12]

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

Algunos de los otros premios para Tarjan incluyen:

Publicaciones Seleccionadas

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

Patentes

Tarjan posee al menos 18 patentes estadounidenses. [5] Estos incluyen:

Notas

  1. ^ "Judíos ganadores 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 los descubrimientos de 15 grandes informáticos . Copérnico/Springer. págs. 102-119. ISBN 978-0-387-97992-2. OCLC  32240355.
  3. ^ "Robert Tarjan: el arte del algoritmo". Hewlett Packard . Consultado el 5 de septiembre de 2010 .
  4. ^ "Robert Endre Tarjan". Proyecto Genealogía Matemática . Consultado el 9 de enero de 2008 .
  5. ^ 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 .
  6. ^ ab "Robert Endre Tarjan: El arte del algoritmo (entrevista)". Hewlett Packard. Septiembre de 2004 . Consultado el 9 de enero de 2008 .
  7. ^ "Nayla Rizk y Robert Tarjan". Los New York Times . Julio 2013.
  8. ^ "Fotos del simposio del 60 cumpleaños de Bob Tarjan". DIMACS. Mayo de 2008.
  9. ^ abcde King, V. "Robert E Tarjan - Laureado del premio AM Turing". ACM . Consultado el 19 de enero de 2014 .
  10. ^ Kocay, William; Kreher, Donald L. (2005). "Gráficos planos". Gráficos, algoritmos y optimización . Boca Ratón: Chapman & Hall/CRC. pag. 312.ISBN _ 978-1-58488-396-8. OCLC  56319851.
  11. ^ Tarjan, Robert E .; van Leeuwen, enero (1984). "Análisis del peor de los casos de algoritmos de unión de conjuntos". Revista de la ACM . 31 (2): 245–281. doi : 10.1145/62.2160 . S2CID  5363073.
  12. ^ "Premio de becarios: Robert E. Tarjan". ACM . 25 de septiembre de 1998 . Consultado el 18 de noviembre de 2005 .
  13. ^ "Ganadores del premio Rolf Nevanlinna". Unión Matemática Internacional . Archivado desde el original el 27 de diciembre de 2008 . Consultado el 19 de enero de 2014 .
  14. ^ "Robert Endre Tarjan". Academia Estadounidense de Artes y Ciencias . Consultado el 15 de junio de 2020 .
  15. ^ "Roberto Tarjan". www.nasonline.org . Consultado el 15 de junio de 2020 .
  16. ^ "Dr. Robert E. Tarjan". Sitio web de la NAE . Consultado el 15 de junio de 2020 .
  17. ^ "Historial de miembros de APS". búsqueda.amphilsoc.org . Consultado el 19 de abril de 2022 .
  18. ^ "Caltech nombra a cinco ex alumnos distinguidos" (Presione soltar). Instituto de Tecnología de California . 2010-03-15. Archivado desde el original el 10 de octubre de 2010 . Consultado el 26 de agosto de 2010 .
  19. ^ "Página de Google Scholar de Robert Tarjan". Google Académico . Consultado el 6 de marzo de 2023 .
  20. ^ Tarjan, Robert (1 de junio de 1972). "Algoritmos de gráficos lineales y búsqueda en profundidad". Revista SIAM de Computación . 1 (2): 146–160. doi :10.1137/0201010. ISSN  0097-5397. S2CID  16467262.
  21. ^ 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.
  22. ^ "Asunto posterior". Estructuras de datos y algoritmos de red : 125–131. Enero de 1983. doi :10.1137/1.9781611970265.bm. ISBN 978-0-89871-187-5.
  23. ^ Goldberg, Andrés V.; Tarjan, Robert E. (1 de octubre de 1988). "Un nuevo enfoque al problema del flujo máximo". Revista de la ACM . 35 (4): 921–940. doi : 10.1145/48014.61051 . ISSN  0004-5411. S2CID  14492800.
  24. ^ Bentley, Jon L.; Sleator, Daniel DK; Tarjan, Robert E. (3 de enero de 1989). "Patente de Estados Unidos 4796003 - Compactación de datos".
  25. ^ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (19 de octubre de 2010). "Patente de Estados Unidos 7818272: método para descubrir grupos de objetos en un gráfico arbitrario no dirigido utilizando una diferencia entre una fracción de conexiones internas y una fracción máxima de conexiones por un objeto externo".
  26. ^ Pinkas, Benjamín; 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 tiene medios relacionados con Robert Tarjan.