Robert Tarjan Endre (, 30 de abril de 1948) es un americano científico informático y matemático . Él es el descubridor de varios algoritmos de gráficos , incluido el algoritmo de ancestros comunes más bajos fuera de línea de Tarjan , y co-inventor de los árboles de extensión y los montones de Fibonacci . Tarjan es actualmente profesor universitario distinguido James S. McDonnell de ciencias de la computación en la Universidad de Princeton y científico jefe en Intertrust Technologies Corporation . [1]
Robert Endre Tarjan | |
---|---|
Nació | |
Ciudadanía | americano |
alma mater | Instituto de Tecnología de California ( BS ) Universidad de Stanford ( MS , PhD ) |
Conocido por | Algoritmos y estructuras de datos |
Premios | Premio Paris Kanellakis (1999) Premio Turing (1986) Premio Nevanlinna (1982) |
Carrera científica | |
Campos | Ciencias de la Computación |
Instituciones | Universidad de Princeton Universidad de Nueva York Universidad de Stanford Universidad de California, Berkeley Universidad de Cornell Microsoft Research Intertrust Technologies Hewlett-Packard Compaq NEC Research Bell Labs |
Tesis | Un algoritmo de planaridad eficiente (1972) |
Asesor de doctorado | Robert W. Floyd |
Otros asesores académicos | Donald Knuth |
Estudiantes de doctorado | |
Sitio web | www |
Temprana edad y educación
Nació en Pomona , California . Su padre era un psiquiatra infantil especializado en retraso mental y dirigía un hospital estatal. [2] Cuando era niño, 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 el octavo grado, gracias a una maestra "muy estimulante". [3]
Mientras estaba en la escuela secundaria, Tarjan consiguió un trabajo, donde trabajó en clasificadores de tarjetas perforadas de IBM. Primero trabajó 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 de computación muy prominentes, y su Ph.D. tesis 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]
Carrera informática
Tarjan ha estado enseñando en la Universidad de Princeton desde 1985. [6] También ha ocupado cargos académicos en la Universidad de Cornell (1972–73), la Universidad de California, Berkeley (1973–1975), la Universidad de Stanford (1974–1980) y Nueva York. Universidad (1981-1985). También ha sido miembro del NEC Research Institute (1989-1997). [7] 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 la mediana de las medianas . El algoritmo de prueba de planaridad de Hopcroft-Tarjan fue el primer algoritmo de tiempo lineal para la prueba de planaridad. [8]
Tarjan también ha desarrollado estructuras de datos importantes como el montón de Fibonacci (una estructura de datos del montón que consta de un bosque de árboles) y el árbol de 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 probar el tiempo de ejecución óptimo que involucra la función inversa de Ackermann . [9]
Premios
Tarjan recibió el premio Turing junto con John Hopcroft en 1986. La cita para el premio dice [7] 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 para este premio dice: [10]
Para avances fundamentales en el diseño y análisis de estructuras de datos y algoritmos.
Algunos de los otros premios para Tarjan incluyen:
- Premio Nevanlinna en Ciencias de la Información (1983) [7] - primer galardonado [11]
- Miembro de la Academia Estadounidense de Artes y Ciencias , elegido en 1985 [12]
- Premio de la Academia Nacional de Ciencias a las iniciativas de investigación (1984) [7]
- Miembro de la Academia Nacional de Ciencias , elegido en 1987 [13]
- Miembro de la Academia Nacional de Ingeniería , elegido en 1988 [14]
- Premio Paris Kanellakis de Teoría y Práctica, ACM (1999) [7]
- Premio Caltech Distinguished Alumni, Instituto de Tecnología de California (2010) [15]
Patentes
Tarjan posee al menos 18 patentes estadounidenses. [5] Estos incluyen:
- J. Bentley, D. Sleator y RE Tarjan, Patente de EE.UU. 4.796.003, Compactación de datos , 1989 [16]
- N. Mishra, R. Schreiber y RE Tarjan, Patente de EE. UU. 7,818,272, Método para el descubrimiento de grupos de objetos en un gráfico arbitrario no dirigido usando una diferencia entre una fracción de conexiones internas y una fracción máxima de conexiones por un objeto externo , 2010 [17 ]
- B. Pinkas, S. Haber, RE Tarjan y T. Sander, Patente de EE. UU. 8220036, Establecimiento de un canal seguro con un usuario humano , 2012 [18]
Trabajos de investigación
Según Google Scholar , ha publicado más de 500 artículos de investigación que han sido citados más de 80.000 veces. [19]
Algunos de sus papeles principales incluyen:
- 1972: Búsqueda en profundidad y algoritmos de gráficos lineales, R Tarjan, Revista SIAM sobre informática 1 (2), 146-160 [20]
- 1987: Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados, ML Fredman, RE Tarjan, Journal of the ACM (JACM) 34 (3), 596-615 [21]
- 1983: Estructuras de datos y algoritmos de red, RE Tarjan, Sociedad de Matemáticas Industriales y Aplicadas [22]
- 1988: Un nuevo enfoque al problema del flujo máximo, V Goldberg, RE Tarjan, Journal of the ACM (JACM) 35 (4), 921-940 [23]
Notas
- ^ "Liderazgo intertrust" . intertrust.com .
- ^ a b 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 científicos informáticos . Copérnico / Springer. págs. 102-119 . ISBN 978-0-387-97992-2. OCLC 32240355 .
- ^ "Robert Tarjan: el arte del algoritmo" . Hewlett-Packard . Consultado el 5 de septiembre de 2010 .
- ^ "Robert Endre Tarjan" . Proyecto de genealogía matemática . Consultado el 9 de enero de 2008 .
- ^ a b 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 .
- ^ a b "Robert Endre Tarjan: el arte del algoritmo (entrevista)" . Hewlett Packard. Septiembre de 2004 . Consultado el 9 de enero de 2008 .
- ^ a b c d e King, V. "Robert E Tarjan - AM Turing Award Laureate" . ACM . Consultado el 19 de enero de 2014 .
- ^ 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 .
- ^ Tarjan, Robert E .; van Leeuwen, Jan (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 .
- ^ "Premio Fellows - Robert E. Tarjan" . ACM . 25 de septiembre de 1998 . Consultado el 18 de noviembre de 2005 .
- ^ "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 .
- ^ "Robert Endre Tarjan" . Academia Estadounidense de Artes y Ciencias . Consultado el 15 de junio de 2020 .
- ^ "Robert Tarjan" . www.nasonline.org . Consultado el 15 de junio de 2020 .
- ^ "Dr. Robert E. Tarjan" . Sitio web de NAE . Consultado el 15 de junio de 2020 .
- ^ "Caltech nombra a cinco alumnos distinguidos" (Comunicado de prensa). 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 .
- ^ Bentley, Jon L .; Sleator, Daniel DK; Tarjan, Robert E. (3 de enero de 1989). "Patente de Estados Unidos 4796003 - Compactación de datos" .
- ^ 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 usando una diferencia entre una fracción de conexiones internas y una fracción máxima de conexiones por un objeto externo" .
- ^ 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" .
- ^ "Robert Tarjan" . scholar.google.com . Consultado el 2 de febrero de 2021 .
- ^ Tarjan, Robert (1 de junio de 1972). "Búsqueda en profundidad primero y algoritmos de gráficos lineales" . Revista SIAM de Computación . 1 (2): 146–160. doi : 10.1137 / 0201010 . ISSN 0097-5397 .
- ^ Fredman, Michael L .; Tarjan, Robert Endre (1 de julio de 1987). "Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados" . Revista de la ACM . 34 (3): 596–615. doi : 10.1145 / 28869.28874 . ISSN 0004-5411 . S2CID 7904683 .
- ^ "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.
- ^ Goldberg, Andrew V .; Tarjan, Robert E. (1 de octubre de 1988). "Un nuevo enfoque al problema del caudal máximo" . Revista de la ACM . 35 (4): 921–940. doi : 10.1145 / 48014.61051 . ISSN 0004-5411 . S2CID 14492800 .
Referencias
- Tarjan, Robert E. (1983). Estructuras de datos y algoritmos de red . Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 978-0-89871-187-5. OCLC 10120539 .
- Tarjan, Robert E .; Pólya, George; Woods, Donald R. (1983). Notas sobre combinatoria introductoria . Boston: Birkhauser. ISBN 978-0-8176-3170-3. OCLC 10018128 .
- Entradas de OCLC para Robert E Tarjan
- Robert E. Tarjan en el servidor de bibliografía DBLP
enlaces externos
- Robert E. Tarjan en el servidor de bibliografía DBLP
- Lista de patentes de Robert Tarjan en el directorio de patentes de IPEXL
- Página de inicio de Robert Tarjan en Princeton .
- Robert Endre Tarjan en el Proyecto de genealogía matemática