John Hopcroft: Das Lehrbuch, das ein Fachgebiet prägte

Millionen von Informatikstudenten haben noch nie ein Wort gelesen, das John Hopcroft in einer Fachzeitschrift geschrieben hat, und doch haben fast alle von ihm gelernt – durch die Lehrbücher über Automatentheorie und Algorithmen, die seinen Namen neben denen von Jeffrey Ullman und Alfred Aho tragen, Bücher, die so umfassend als Standardlehrplan übernommen wurden, dass sie die Art und Weise prägten, wie sich die Disziplin selbst lehrt.

Vom Sohn eines Hausmeisters nach Stanford

John Edward Hopcroft wurde am 7. Oktober 1939 in Seattle, Washington, in eine Arbeiterfamilie geboren; sein Vater, ein britischer Veteran des Ersten Weltkriegs, arbeitete als Hausmeister, und keiner seiner Eltern hatte die High School abgeschlossen. Er war auch der Enkel von Jacob Nist, dem Gründer der Seattle-Tacoma Box Company. Trotz ihrer begrenzten Schulbildung förderten seine Eltern seine intellektuelle Neugier, und er erwarb 1961 einen Bachelor-Abschluss in Elektrotechnik an der Seattle University, gefolgt von einem Master-Abschluss 1962 und einem Doktortitel 1964, beide in Elektrotechnik, an der Stanford University. Diese ingenieurwissenschaftliche Ausbildung, eher als ein Hintergrund in reiner Mathematik oder Informatik, prägte seinen späteren Instinkt für Algorithmen, die nicht nur theoretisch elegant, sondern auch wirklich effizient ausführbar waren.

Aufbau der Lehrbücher der Disziplin

Hopcroft begann seine akademische Laufbahn an der Princeton University als Assistenzprofessor, bevor er an die Cornell University wechselte, wo er den Großteil seiner Karriere verbringen sollte. Dort hielt er schließlich den Titel eines IBM-Professors für Ingenieurwesen und angewandte Mathematik und bekleidete Führungspositionen, darunter als Fachbereichsleiter und Dekan für Ingenieurwesen. In Cornell verfasste er zusammen mit Jeffrey Ullman und später Alfred Aho eine Reihe von Lehrbüchern über formale Sprachen, Automatentheorie und Algorithmenentwurf, die für Generationen von Informatikstudenten weltweit zu den Standardlehrtexten wurden. Diese Bücher taten mehr als nur bestehendes Wissen zusammenzufassen – sie kodifizierten die asymptotische Komplexitätsanalyse und die Theorie formaler Sprachen in die Form, die heute noch in einführenden Theoriekursen gelehrt wird, und gaben dem Fachgebiet ein gemeinsames Vokabular, bevor dieses Vokabular anderswo vollständig existierte.

Algorithmen, die heute noch laufen

Über die Lehrbücher hinaus brachte Hopcrofts eigene Forschung Werkzeuge hervor, die noch heute aktiv genutzt werden. Der Hopcroft-Karp-Algorithmus, der zusammen mit Richard Karp entwickelt wurde, findet maximale Matchings in bipartiten Graphen schneller als jede zuvor existierende Methode und bleibt eine Standardtechnik bei Netzwerkfluss- und Zuweisungsproblemen. Er entwickelte auch einen effizienten Algorithmus zur Minimierung deterministischer endlicher Automaten, ein grundlegendes Werkzeug beim Compilerbau und der formalen Verifikation. Sein berühmtestes Ergebnis war jedoch eine gemeinsame Arbeit mit Robert Tarjan: der erste Algorithmus in linearer Zeit, um zu testen, ob ein Graph planar ist – ob er also auf einer flachen Oberfläche gezeichnet werden kann, ohne dass sich Kanten kreuzen –, veröffentlicht 1974. Die beiden bauten den Algorithmus um eine systematische Verwendung der Tiefensuche auf und verwandelten ein zuvor langsames, ad-hoc-Problem in eines, das in einer Zeit gelöst werden kann, die proportional zur Größe des Graphen selbst ist.

Der Turing Award und sein geteilter Charakter

1986 erhielten Hopcroft und Tarjan gemeinsam den ACM A.M. Turing Award, die höchste Auszeichnung in der Informatik, „für grundlegende Leistungen beim Entwurf und der Analyse von Algorithmen und Datenstrukturen“. Die Begründung nennt beide Männer zusammen und würdigt eine Reihe gemeinsamer und paralleler Arbeiten anstelle eines einzelnen individuellen Durchbruchs – der Planaritätsalgorithmus ist dabei die wichtigste der Leistungen, die die Begründung im Sinn hatte, neben den unabhängigen Beiträgen jedes Mannes zum breiteren Feld des Algorithmenentwurfs.

Eine zweite Karriere in China

In den Jahrzehnten nach seinem Turing Award lenkte Hopcroft einen Großteil seiner Energie darauf, die Informatikausbildung außerhalb der Vereinigten Staaten zu stärken, insbesondere in China. Er wurde Co-Direktor des Center on Frontiers of Computing Studies an der Peking-Universität und leitet Zentren, die seinen Namen tragen, an der Shanghai Jiao Tong University und der Huazhong University of Science and Technology. Dort betreut er Studenten und hilft beim Aufbau von Forschungsprogrammen in Algorithmen und, in jüngerer Zeit, im Deep Learning. China verlieh ihm 2016 seinen Friendship Award, eine Anerkennung, die ausländischen Experten vorbehalten ist, die herausragende Beiträge zur Entwicklung des Landes geleistet haben – ein ungewöhnlicher zweiter Akt für einen Turing-Preisträger, der bereits Jahrzehnte von der Arbeit entfernt war, die ihm den Preis einbrachte.

Anerkennung

Hopcroft wurde 1989 in die National Academy of Engineering gewählt, wurde 1994 ACM Fellow und erhielt 2010 die IEEE John von Neumann Medal für herausragende Leistungen in Informatik und Ingenieurwesen, zusätzlich zum Turing Award 1986 und dem chinesischen Friendship Award 2016.

Warum John als Genie bezeichnet wird

Das Argument für Hopcrofts Genie beruht nicht auf einem einzigen blendenden Beweis, sondern auf einer selteneren Kombination: Forschungsbeiträge, die substanziell genug sind, um den wichtigsten Preis des Fachgebiets zu gewinnen, gepaart mit einer unübertroffenen Begabung, die Grundlagen dieses Fachgebiets in eine lehrbare Form zu bringen. Der Planaritätsalgorithmus und der Hopcroft-Karp-Matching-Algorithmus sind die Art von Ergebnissen, die theoretische Informatiker als wirklich clever bezeichnen – sie reduzieren Probleme, die eine Brute-Force-Suche zu erfordern schienen, durch strukturelle Einsicht auf eine lineare oder nahezu lineare Zeit. Aber die ehrliche Einordnung, die die Begründung des Turing Awards selbst explizit macht, ist, dass sein berühmtestes Ergebnis gemeinsam ihm und Robert Tarjan gehört; die Begründung für keinen der beiden Männer steht für sich allein, und der Preis wurde für eine gemeinsame Gesamtheit von Leistungen verliehen, nicht für einen Solo-Durchbruch. Was weniger geteilt und seltener als „Genie“ gefeiert wird, ist sein zweites Talent: drei separate, gemeinsam verfasste Lehrbücher, die so gut konstruiert waren, dass sie zur Standardmethode wurden, mit der sich eine ganze Disziplin ihre eigenen Grundlagen selbst belehrt – eine Form des intellektuellen Beitrags, die eher dem meisterhaften Lehren als der individuellen Erfindung nahekommt.

Vermächtnis

Hopcrofts Vermächtnis verläuft auf zwei parallelen Spuren, die in einer Karriere selten zusammenfallen – eine mit dem Turing Award ausgezeichnete Forschungsbilanz bei Algorithmen und ein jahrzehntelanger zweiter Akt beim Aufbau der Infrastruktur für Informatikausbildung in China. Nur wenige Persönlichkeiten in der Geschichte des Fachgebiets haben die Art und Weise, wie es gelehrt wird, so direkt oder so lange geprägt wie der Autor seiner am weitesten verbreiteten Lehrbücher. Dass der Mann, der in den 1960er und 1970er Jahren half, die Theorie der Berechnung zu formalisieren, in den 2010er Jahren Studenten im Bereich Deep Learning an der Peking-Universität betreute, sagt etwas über die ungewöhnliche Länge und Reichweite seines Arbeitslebens aus: eine Karriere, die in der Ära der vakuumröhrennahen Elektrotechnik begann und in der Ära der neuronalen Netze fortgesetzt wurde, ohne jemals ihren roten Faden zu verlieren, der nächsten Generation die zugrunde liegende Struktur des Fachgebiets zu vermitteln.