Robert Tarjan: La gramática de los algoritmos eficientes

Pídale a cualquier estudiante de informática que rastree un grafo con búsqueda en profundidad y, lo sepa o no, estará ejecutando una técnica que Robert Tarjan convirtió de una curiosidad en una disciplina. Su artículo de 1972 "Depth-first search and linear graph algorithms" se lee hoy como un texto de gramática fundamental: el tipo de trabajo tan profundamente absorbido por el campo que el nombre de su autor casi ha desaparecido de cómo la gente habla de él, incluso cuando su nombre se asocia a media docena de estructuras que utilizan a diario.

El camino de un matemático hacia las máquinas

Robert Endre Tarjan nació el 30 de abril de 1948 en Pomona, California, hijo de George Tarjan, un psiquiatra infantil especializado en discapacidad intelectual; su hermano menor, James, se convirtió en gran maestro de ajedrez. Tarjan quería ser astrónomo de niño, hasta que las columnas de acertijos de Martin Gardner en Scientific American y un inspirador profesor de octavo grado lo llevaron hacia las matemáticas. Obtuvo una licenciatura en matemáticas en Caltech en 1969, luego fue a Stanford para obtener una maestría en ciencias de la computación en 1971 y un doctorado en 1972, con una tesis sobre algoritmos de planaridad supervisada por Robert Floyd y Donald Knuth. Más tarde describiría su elección de campo con sencillez: la informática era una forma de hacer matemáticas que podía tener un impacto práctico, una frase que también sirve como descripción de toda su obra.

Construyendo el conjunto de herramientas

La carrera de Tarjan, que abarcó Cornell, UC Berkeley, Stanford, AT&T Bell Labs, NYU, NEC Research Institute, Microsoft Research, Compaq, Hewlett Packard e Intertrust Technologies antes de establecerse en Princeton en 1985 como profesor universitario distinguido James S. McDonnell, produjo un conjunto de algoritmos y estructuras de datos inusual por la cantidad de ellos que se convirtieron en infraestructura de soporte en lugar de curiosidades teóricas. Su nombre se asocia al algoritmo de Tarjan para encontrar componentes fuertemente conectados en un grafo, un algoritmo fuera de línea para calcular ancestros comunes mínimos y un algoritmo de tiempo lineal para encontrar puentes: todas técnicas construidas sobre el marco de búsqueda en profundidad que él formalizó. En 1975 dio el primer análisis exacto de la estructura de datos union-find combinada con compresión de caminos, demostrando su tiempo de ejecución amortizado casi constante utilizando la función de Ackermann inversa, un resultado tan estrechamente ligado al rendimiento en el mundo real que ahora subyace a todo, desde el algoritmo de árbol de expansión mínima de Kruskal hasta las optimizaciones de compiladores. Con Daniel Sleator en Bell Labs co-inventó los árboles splay, árboles de búsqueda binaria autoajustables que se reequilibran mediante el uso en lugar de llevar metadatos de equilibrio explícitos, y con ellos fue pionero en el análisis competitivo, un marco para juzgar algoritmos en línea frente a un adversario que todo lo sabe. Con Michael Fredman desarrolló los montículos de Fibonacci en 1985, una estructura de cola de prioridad que hizo que el algoritmo de camino más corto de Dijkstra y los algoritmos de optimización de red fueran asintóticamente más rápidos que cualquier cosa anterior. Su libro de texto, Data Structures and Network Algorithms, ganó el Premio Frederick W. Lancaster y se convirtió en lectura estándar en el campo.

El avance de la planaridad con Hopcroft

El logro único más explícitamente acreditado en su cita del Premio Turing es el trabajo conjunto con John Hopcroft: el primer algoritmo de tiempo lineal para probar si un grafo puede dibujarse en un plano sin que se crucen aristas, publicado en 1974. Las pruebas de planaridad habían sido un problema lento y difícil antes de que su algoritmo lo redujera a una cuestión de cuidadoso recorrido en profundidad, una técnica tan central para su solución que la formalización anterior de Tarjan de la búsqueda en profundidad se convirtió, en retrospectiva, en la herramienta que hizo posible el resultado de Hopcroft-Tarjan. Ambos compartieron el Premio ACM Turing de 1986 "por logros fundamentales en el diseño y análisis de algoritmos y estructuras de datos", una cita que acredita un cuerpo de trabajo conjunto y paralelo en lugar de un solo artículo.

Reconocimiento a lo largo de cuatro décadas

Tarjan fue el primer receptor del Premio Nevanlinna en Ciencias de la Computación en 1983, honrando contribuciones sobresalientes a los aspectos matemáticos de la informática. Ganó el Premio Turing en 1986, fue elegido miembro de la Academia Estadounidense de las Artes y las Ciencias en 1985, de la Academia Nacional de Ciencias en 1987 y de la Academia Nacional de Ingeniería en 1988. Recibió el Premio Paris Kanellakis en Teoría y Práctica en 1999 y el Premio al Alumno Distinguido de Caltech en 2010. Su historial de publicaciones supera los 250 artículos con decenas de miles de citas, y posee más de una docena de patentes estadounidenses en estructuras de datos y seguridad, lo que refleja una carrera que se movió con fluidez entre la teoría académica en Princeton y la investigación aplicada en laboratorios industriales como Bell Labs, NEC y Microsoft.

Por qué Robert es llamado un genio

El caso de Tarjan para la palabra se basa en algo específico: no solo resolvió problemas difíciles individuales, sino que identificó la maquinaria combinatoria subyacente (búsqueda en profundidad, análisis amortizado, autoajuste) que hizo rápidos a clases enteras de algoritmos previamente lentos, y lo hizo repetidamente a lo largo de cuatro décadas en lugar de una sola vez. El análisis de union-find y el algoritmo de planaridad de Hopcroft-Tarjan siguen siendo material de libro de texto precisamente porque no son trucos inteligentes, sino técnicas generales que otros investigadores podrían reutilizar; esa reutilización, más que cualquier resultado único, es lo que los comités del Premio Nevanlinna y del Premio Turing estaban recompensando. La complicación honesta es que su resultado más célebre, el algoritmo de planaridad de tiempo lineal, es explícitamente un trabajo conjunto con John Hopcroft, y la cita del Premio Turing acredita a ambos hombres conjuntamente en lugar de coronar a cualquiera como un genio solitario; el premio en sí es prueba de que el campo considera esto como un logro colaborativo, no una invención singular. Otros resultados emblemáticos de Tarjan se construyeron de manera similar con coautores nombrados: árboles splay con Daniel Sleator, montículos de Fibonacci con Michael Fredman. Lo que no se discute es la gran densidad de resultados fundamentales y aún enseñados que llevan su nombre, un récord que pocos en el campo han igualado.

Legado

Todo estudiante de informática que aprende búsqueda en profundidad, union-find, árboles splay o montículos de Fibonacci está, en efecto, siendo enseñado por los artículos de Tarjan, décadas después de que fueron escritos. Su trabajo se encuentra debajo de compiladores, enrutamiento de red y sistemas de información geográfica sin que la mayoría de sus usuarios conozcan su nombre: el destino silencioso de las matemáticas a nivel de infraestructura que tuvieron éxito por completo. Continuó produciendo nuevos resultados hasta bien entrados los setenta años, moviéndose entre el profesorado de Princeton y roles como científico jefe en Intertrust Technologies e investigador en Microsoft y Hewlett Packard, una forma de carrera que argumenta en contra de tratarlo como una figura puramente académica: gran parte de su trabajo más citado se realizó, probó y aplicó dentro de laboratorios de investigación industrial en lugar de en un vacío universitario. Esa doble vida, publicar matemáticas rigurosas mientras también patenta sistemas prácticos, es parte de lo que separa su historial de los teóricos cuyas ideas permanecieron confinadas a las revistas.