John Hopcroft: El libro de texto que formó un campo

Millones de estudiantes de informática nunca han leído una palabra escrita por John Hopcroft en una revista de investigación, sin embargo, casi todos han aprendido de él, a través de los libros de texto de teoría de autómatas y algoritmos que llevan su nombre junto a los de Jeffrey Ullman y Alfred Aho, libros tan ampliamente adoptados como plan de estudios estándar que dieron forma a cómo se enseña la disciplina.

De hijo de un conserje a Stanford

John Edward Hopcroft nació el 7 de octubre de 1939 en Seattle, Washington, en una familia de clase trabajadora; su padre, un veterano británico de la Primera Guerra Mundial, trabajaba como conserje, y ninguno de sus padres había terminado la escuela secundaria. También era nieto de Jacob Nist, fundador de la Seattle-Tacoma Box Company. A pesar de su limitada escolarización, sus padres fomentaron su curiosidad intelectual, y obtuvo una licenciatura en ingeniería eléctrica en la Universidad de Seattle en 1961, seguida de una maestría en 1962 y un doctorado en 1964, ambos en ingeniería eléctrica, en la Universidad de Stanford. Esa formación en ingeniería, más que una formación en matemáticas puras o informática, dio forma a su instinto posterior para algoritmos que no solo fueran teóricamente elegantes, sino genuinamente eficientes de ejecutar.

Construyendo los libros de texto de la disciplina

Hopcroft comenzó su carrera académica en la Universidad de Princeton como profesor asistente antes de trasladarse a la Universidad de Cornell, donde pasaría la mayor parte de su carrera, ocupando finalmente el título de Profesor IBM de Ingeniería y Matemáticas Aplicadas y desempeñando funciones de liderazgo, incluyendo jefe de departamento y decano de ingeniería. Fue en Cornell donde fue coautor, con Jeffrey Ullman y más tarde Alfred Aho, de una serie de libros de texto sobre lenguajes formales, teoría de autómatas y diseño de algoritmos que se convirtieron en los textos de enseñanza predeterminados para generaciones de estudiantes de informática en todo el mundo. Estos libros hicieron más que resumir el conocimiento existente: codificaron el análisis de complejidad asintótica y la teoría de lenguajes formales en la forma que todavía se enseña en los cursos de teoría introductoria hoy en día, dando al campo un vocabulario compartido antes de que ese vocabulario existiera plenamente en otros lugares.

Algoritmos que todavía se ejecutan hoy

Más allá de los libros de texto, la propia investigación de Hopcroft produjo herramientas que todavía están en uso activo. El algoritmo de Hopcroft-Karp, desarrollado con Richard Karp, encuentra emparejamientos máximos en grafos bipartitos más rápido que cualquier método que lo precediera, y sigue siendo una técnica estándar en problemas de flujo de red y asignación. También desarrolló un algoritmo eficiente para minimizar autómatas finitos deterministas, una herramienta fundamental en el diseño de compiladores y la verificación formal. Su resultado más célebre, sin embargo, fue un trabajo conjunto con Robert Tarjan: el primer algoritmo de tiempo lineal para probar si un grafo es plano —si se puede dibujar en una superficie plana sin que se crucen los bordes— publicado en 1974. Los dos construyeron el algoritmo en torno a un uso sistemático de la búsqueda en profundidad, convirtiendo lo que había sido un problema lento y ad hoc en uno resoluble en un tiempo proporcional al tamaño del grafo mismo.

El Premio Turing y su naturaleza compartida

En 1986, Hopcroft y Tarjan recibieron conjuntamente el Premio ACM A.M. Turing, el honor más alto de la computación, "por sus logros fundamentales en el diseño y análisis de algoritmos y estructuras de datos". La mención nombra a ambos hombres juntos y acredita un cuerpo de trabajo colaborativo y paralelo en lugar de un único avance individual: el algoritmo de planaridad es el principal de los logros que la mención tenía en mente, junto con las contribuciones independientes de cada hombre al campo más amplio del diseño de algoritmos.

Una segunda carrera en China

En las décadas posteriores a su Premio Turing, Hopcroft redirigió gran parte de su energía hacia el fortalecimiento de la educación en informática fuera de los Estados Unidos, particularmente en China. Se convirtió en codirector del Centro de Fronteras de Estudios Informáticos de la Universidad de Pekín y dirige centros que llevan su nombre en la Universidad Jiao Tong de Shanghái y en la Universidad de Ciencia y Tecnología de Huazhong, asesorando a estudiantes y ayudando a construir programas de investigación en algoritmos y, más recientemente, en aprendizaje profundo. China le otorgó su Premio de la Amistad en 2016, un reconocimiento reservado para expertos extranjeros que han hecho contribuciones sobresalientes al desarrollo del país, un segundo acto inusual para un laureado con el Turing que ya llevaba décadas alejado del trabajo que le valió el premio.

Reconocimiento

Hopcroft fue elegido miembro de la Academia Nacional de Ingeniería en 1989, se convirtió en miembro de la ACM en 1994 y recibió la Medalla IEEE John von Neumann en 2010 por sus logros sobresalientes en informática e ingeniería, además del Premio Turing de 1986 y el Premio de la Amistad chino de 2016.

Por qué a John se le llama genio

El caso del genio de Hopcroft no descansa en una sola prueba deslumbrante, sino en una combinación más rara: contribuciones de investigación lo suficientemente sustanciales como para ganar el premio más importante del campo, junto con un don inigualable para destilar los fundamentos de ese campo en una forma enseñable. El algoritmo de planaridad y el algoritmo de emparejamiento de Hopcroft-Karp son el tipo de resultados que los científicos informáticos teóricos señalan como genuinamente inteligentes: reducir problemas que parecían requerir una búsqueda de fuerza bruta a un tiempo lineal o casi lineal a través de la intuición estructural. Pero el marco honesto, que la propia mención del Premio Turing hace explícito, es que su resultado más famoso pertenece conjuntamente a él y a Robert Tarjan; la mención de ninguno de los dos hombres se sostiene por sí sola, y el premio fue por un cuerpo compartido de logros, no por un avance en solitario. Lo que es menos compartido, y menos celebrado a menudo como "genio", es su segundo talento: tres libros de texto separados en coautoría tan bien construidos que se convirtieron en la forma predeterminada en que toda una disciplina se enseña a sí misma sus propios fundamentos, una forma de contribución intelectual más cercana a la enseñanza magistral que a la invención individual.

Legado

El legado de Hopcroft sigue dos caminos paralelos que rara vez coinciden en una carrera: un historial de investigación ganador del Premio Turing en algoritmos y un segundo acto de décadas construyendo infraestructura de educación en informática en China. Pocas figuras en la historia del campo han dado forma a cómo se enseña tan directamente, o durante tanto tiempo, como el autor de sus libros de texto más ampliamente asignados. Que el hombre que ayudó a formalizar la teoría de la computación en las décadas de 1960 y 1970 estuviera, en la década de 2010, asesorando a estudiantes en aprendizaje profundo en la Universidad de Pekín dice algo sobre la inusual duración y alcance de su vida laboral: una carrera que comenzó en la era de la ingeniería eléctrica adyacente a los tubos de vacío y continuó en la era de las redes neuronales, sin perder nunca su hilo conductor de enseñar a la próxima generación la estructura subyacente del campo.