Robert Tarjan: Die Grammatik effizienter Algorithmen

Fragen Sie einen Informatikstudenten, einen Graphen mit Tiefensuche zu durchlaufen, und er führt, ob er es weiß oder nicht, eine Technik aus, die Robert Tarjan von einer Kuriosität zu einer Disziplin gemacht hat. Sein Artikel aus dem Jahr 1972 „Depth-first search and linear graph algorithms“ liest sich heute wie ein grundlegender Grammatiktext – die Art von Arbeit, die so gründlich in das Fachgebiet aufgenommen wurde, dass der Name ihres Autors fast aus der Art und Weise verschwunden ist, wie die Leute darüber sprechen, obwohl sein Name mit einem halben Dutzend Strukturen verbunden ist, die sie täglich verwenden.

Der Weg eines Mathematikers zu den Maschinen

Robert Endre Tarjan wurde am 30. April 1948 in Pomona, Kalifornien, als Sohn von George Tarjan, einem auf geistige Behinderungen spezialisierten Kinderpsychiater, geboren; sein jüngerer Bruder James wurde Schachgroßmeister. Tarjan wollte als Junge Astronom werden, bis Martin Gardners Rätselkolumnen im Scientific American und ein inspirierender Lehrer in der achten Klasse ihn stattdessen zur Mathematik zogen. Er erwarb 1969 einen Bachelor-Abschluss in Mathematik am Caltech, ging dann 1971 für einen Master in Informatik nach Stanford und promovierte 1972 mit einer Dissertation über Planaritätsalgorithmen unter der Betreuung von Robert Floyd und Donald Knuth. Er beschrieb seine Wahl des Fachgebiets später schlicht: Informatik war eine Art, Mathematik zu betreiben, die praktische Auswirkungen haben konnte – ein Satz, der auch als Beschreibung seines gesamten Lebenswerks dient.

Aufbau des Werkzeugkastens

Tarjans Karriere, die Cornell, UC Berkeley, Stanford, AT&T Bell Labs, NYU, NEC Research Institute, Microsoft Research, Compaq, Hewlett Packard und Intertrust Technologies umfasste, bevor er sich 1985 als James S. McDonnell Distinguished University Professor in Princeton niederließ, brachte eine Reihe von Algorithmen und Datenstrukturen hervor, die ungewöhnlich dafür sind, wie viele von ihnen zu tragender Infrastruktur statt zu theoretischen Kuriositäten wurden. Sein Name ist mit Tarjans Algorithmus zum Finden stark zusammenhängender Komponenten in einem Graphen, einem Offline-Algorithmus zur Berechnung der kleinsten gemeinsamen Vorfahren und einem Linearzeit-Algorithmus zum Finden von Brücken verbunden – alles Techniken, die auf dem von ihm formalisierten Framework der Tiefensuche aufbauen. 1975 lieferte er die erste exakte Analyse der Union-Find-Datenstruktur in Kombination mit Pfadkompression und bewies deren nahezu konstante amortisierte Laufzeit unter Verwendung der inversen Ackermann-Funktion, ein Ergebnis, das so eng mit der realen Leistung verbunden ist, dass es heute allem zugrunde liegt, von Kruskals Algorithmus für den minimalen Spannbaum bis hin zu Compiler-Optimierungen. Mit Daniel Sleator bei den Bell Labs erfand er Splay-Bäume, selbstjustierende binäre Suchbäume, die sich durch Gebrauch selbst ausbalancieren, anstatt explizite Balance-Metadaten mitzuführen, und leistete damit Pionierarbeit bei der kompetitiven Analyse, einem Framework zur Beurteilung von Online-Algorithmen gegenüber einem allwissenden Gegner. Mit Michael Fredman entwickelte er 1985 Fibonacci-Heaps, eine Prioritätswarteschlangenstruktur, die Dijkstras Algorithmus für den kürzesten Pfad und Netzwerkoptimierungsalgorithmen asymptotisch schneller machte als alles, was zuvor existierte. Sein Lehrbuch Data Structures and Network Algorithms gewann den Frederick W. Lancaster Prize und wurde zur Standardlektüre auf diesem Gebiet.

Der Planaritäts-Durchbruch mit Hopcroft

Die einzige Leistung, die in seiner Turing-Award-Zitation am explizitesten gewürdigt wird, ist die gemeinsame Arbeit mit John Hopcroft: der erste Linearzeit-Algorithmus zum Testen, ob ein Graph ohne sich kreuzende Kanten auf eine Ebene gezeichnet werden kann, veröffentlicht 1974. Planaritätstests waren ein langsames, schwerfälliges Problem, bevor ihr Algorithmus es auf eine Frage sorgfältiger Tiefensuche reduzierte – eine Technik, die für ihre Lösung so zentral war, dass Tarjans frühere Formalisierung der Tiefensuche im Nachhinein zu dem Werkzeug wurde, das das Hopcroft-Tarjan-Ergebnis erst möglich machte. Die beiden teilten sich den ACM Turing Award 1986 „für grundlegende Leistungen beim Entwurf und der Analyse von Algorithmen und Datenstrukturen“, eine Zitation, die eine Reihe gemeinsamer und paralleler Arbeiten würdigt und nicht nur einen einzelnen Artikel.

Anerkennung über vier Jahrzehnte

Tarjan war 1983 der erste Empfänger des Nevanlinna-Preises für Informationswissenschaft, der herausragende Beiträge zu mathematischen Aspekten der Informatik würdigt. Er gewann 1986 den Turing Award, wurde 1985 in die American Academy of Arts and Sciences, 1987 in die National Academy of Sciences und 1988 in die National Academy of Engineering gewählt. Er erhielt 1999 den Paris Kanellakis Award in Theory and Practice und 2010 den Distinguished Alumni Award des Caltech. Seine Publikationsliste umfasst über 250 Artikel mit zehntausenden Zitierungen, und er hält mehr als ein Dutzend US-Patente im Bereich Datenstrukturen und Sicherheit, was eine Karriere widerspiegelt, die sich fließend zwischen akademischer Theorie in Princeton und angewandter Forschung in Industrielaboren wie Bell Labs, NEC und Microsoft bewegte.

Warum Robert ein Genie genannt wird

Tarjans Fall für das Wort beruht auf etwas Spezifischem: Er löste nicht nur einzelne schwierige Probleme, er identifizierte die zugrunde liegende kombinatorische Maschinerie – Tiefensuche, amortisierte Analyse, Selbstjustierung –, die ganze Klassen zuvor langsamer Algorithmen schnell machte, und er tat dies wiederholt über vier Jahrzehnte hinweg und nicht nur einmal. Die Union-Find-Analyse und der Hopcroft-Tarjan-Planaritätsalgorithmus bleiben genau deshalb Lehrbuchmaterial, weil sie keine cleveren Tricks sind, sondern allgemeine Techniken, die andere Forscher wiederverwenden konnten; diese Wiederverwendbarkeit, mehr als jedes einzelne Ergebnis, ist das, was die Komitees des Nevanlinna-Preises und des Turing Awards belohnten. Die ehrliche Komplikation ist, dass sein berühmtestes Ergebnis, der Linearzeit-Planaritätsalgorithmus, explizit eine gemeinsame Arbeit mit John Hopcroft ist und die Turing-Award-Zitation beide Männer gemeinsam würdigt, anstatt einen von ihnen als einsames Genie zu krönen – der Preis selbst ist der Beweis dafür, dass das Fachgebiet dies als gemeinschaftliche Leistung und nicht als singuläre Erfindung betrachtet. Tarjans andere wegweisende Ergebnisse wurden ebenfalls mit benannten Co-Autoren aufgebaut: Splay-Bäume mit Daniel Sleator, Fibonacci-Heaps mit Michael Fredman. Unbestritten ist die schiere Dichte grundlegender, immer noch gelehrter Ergebnisse, die seinen Namen tragen, ein Rekord, den nur wenige auf diesem Gebiet erreicht haben.

Vermächtnis

Jeder Informatikstudent, der Tiefensuche, Union-Find, Splay-Bäume oder Fibonacci-Heaps lernt, wird effektiv immer noch von Tarjans Artikeln unterrichtet, Jahrzehnte nachdem sie geschrieben wurden. Seine Arbeit liegt unter Compilern, Netzwerk-Routing und geografischen Informationssystemen, ohne dass die meisten ihrer Benutzer seinen Namen kennen – das stille Schicksal von Mathematik auf Infrastrukturebene, die vollständig erfolgreich war. Er produzierte bis weit in seine siebziger Jahre hinein neue Ergebnisse und wechselte zwischen der Fakultät in Princeton und Rollen als Chefwissenschaftler bei Intertrust Technologies sowie als Forscher bei Microsoft und Hewlett Packard, eine Karriereform, die selbst dagegen spricht, ihn als rein akademische Figur zu behandeln: Ein Großteil seiner meistzitierten Arbeiten wurde in Industrieforschungslaboren durchgeführt, getestet und angewendet, anstatt in einem universitären Vakuum. Dieses Doppelleben, das Veröffentlichen strenger Mathematik bei gleichzeitiger Patentierung praktischer Systeme, ist ein Teil dessen, was seine Bilanz von Theoretikern trennt, deren Ideen auf Fachzeitschriften beschränkt blieben.