Roberto 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 gráficos, incluido el algoritmo de ancestros comunes más bajos fuera de línea de Tarjan, y co-inventor de árboles splay y montones de Fibonacci. Tarjan es actualmente el Profesor Universitario Distinguido James S. McDonnell de Ciencias de la Computación en la Universidad de Princeton, y el Científico Jefe de Intertrust Technologies Corporation.

Vida temprana y educación

Nació en Pomona, California. Su padre, criado en Hungría, era psiquiatra infantil, se especializaba en retraso mental y dirigía un hospital estatal. De niño, Tarjan leía mucha ciencia ficción y quería ser astrónomo. Se interesó en las matemáticas después de leer la columna de juegos matemáticos de Martin Gardner en Scientific American. Se interesó seriamente en las matemáticas en el octavo grado, gracias a un programa "muy estimulante" profesor.

Mientras estaba en la escuela secundaria, Tarjan consiguió un trabajo, en el que trabajó en recopiladores de tarjetas perforadas de IBM. Primero trabajó con computadoras reales mientras estudiaba astronomía en el Programa de Ciencias de Verano en 1964.

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 informática en 1971 y un doctorado. en informática (con especialización en matemáticas) en 1972. En Stanford, fue supervisado por Robert Floyd y Donald Knuth, ambos científicos informáticos muy destacados, y su Ph.D. 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.

Carrera de informática

Tarjan ha estado enseñando en la Universidad de Princeton desde 1985. 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 Nueva York. Universidad (1981-1985). También ha sido miembro del Instituto de Investigación NEC (1989–1997). 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 de la selección de tiempo lineal mediana de medianas. algoritmo. El algoritmo de prueba de planaridad de Hopcroft-Tarjan fue el primer algoritmo de tiempo lineal para probar la planaridad.

Tarjan también ha desarrollado estructuras de datos importantes 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 binaria autoajustable; inventado conjuntamente 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.

Premios

Tarjan recibió el Premio Turing junto con John Hopcroft en 1986. La mención del premio dice que fue:

Para 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 mención de este premio establece:

Para avances seminales 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) – primer receptor
• Miembro de la Academia Americana de Artes y Ciencias, elegido 1985
• National Academy of Sciences Award for Initiatives in Research (1984)
• Member of the National Academy of Sciences, elected 1987
• Member of the National Academy of Engineering, elected 1988
• Miembro de la Sociedad Filosófica Americana, elegido 1990
• Paris Kanellakis Award in Theory and Practice, ACM (1999)
• Caltech Distinguished Alumni Award, California Institute of Technology (2010)

Patentes

Tarjan posee al menos 18 patentes estadounidenses. Éstos incluyen:

• J. Bentley, D. Sleator, and R. E. Tarjan, U. S. Patent 4,796,003, Compactación de datos, 1989
• N. Mishra, R. Schreiber, and R. E. Tarjan, U. S. Patent 7,818,272, Método para el descubrimiento de racimos 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, 2010
• B. Pinkas, S. Haber, R. E. Tarjan, and T. Sander, U. S. Patent 8220036, Establecer un canal seguro con un usuario humano, 2012

Artículos de investigación

Según Google Scholar, ha publicado más de 500 trabajos de investigación que han sido citados más de 80 000 veces.

Algunos de sus artículos principales incluyen:

• 1972: Depth-first search and linear graph algoritmos, R Tarjan, SIAM Journal on Computing 1 (2), 146-160
• 1987: Fibonacci heaps and their uses in improved network optimization algoritmos, ML Fredman, RE Tarjan, Journal of the ACM (JACM) 34 (3), 596-615
• 1983: Estructuras de datos y algoritmos de red, RE Tarjan, Sociedad para Matemáticas Industriales y Aplicadas
• 1988: A new approach to the maximum-flow problem, V Goldberg, RE Tarjan, Journal of the ACM (JACM) 35 (4), 921-940