Die Laureaten

Copyright © Klaus Tschira Stiftung / Peter Badge

Robert Endre Tarjan

Prof. Robert Endre Tarjan, * 30. April 1948 in Pomona, Bundesstaat Kalifornien (USA)

Turing Award (1986, zusammen mit John E. Hopcroft) für „grundlegende Fortschritte beim Entwurf und der Analyse von Algorithmen und Datenstrukturen”

Robert Endre Tarjan erwarb seinen Bachelor in Mathematik 1969 am Caltech, dem California Institute of Technology in Pasadena. Zunächst unentschlossen, ob er sich in Mathematik oder Informatik weiter qualifizieren sollte, entschied er sich für die Computerwissenschaften. Denn dort konnte er seine mathematischen Fähigkeiten nutzen, um Probleme in praktischen Anwendungen zu lösen. An der Stanford University machte er zunächst seinen Master (1971, Informatik), dann seinen Ph.D. (1972, Informatik mit Nebenfach Mathematik). Anschließend ging Tarjan als Assistant Professor für Informatik an die Cornell University (1972-1973), als Miller Research Fellow an die University of California, Berkeley (1973-1975) und schließlich zurück an die Stanford University, zunächst als Assistant Professor für Informatik (1974-1977), dann als Associate Professor (1977-1980). Danach wurde er Mitarbeiter der AT&T Bell Laboratories in Murray Hill im Bundesstaat New Jersey (1980-1989). Während dieser Zeit war Tarjan zusätzlich Adjunct Professor für Informatik an der New York University (l98l-1985). Seit 1985 ist er James S. McDonnell Distinguished University Professor für Computerwissenschaften an der Princeton University (bis heute). Nach dem Weggang von AT&T wurde Tarjan Fellow am NEC Research Institute in Princeton (1989-1997), Chef-Wissenschaftler bei InterTrust Technologies in Sunnyvale, Kalifornien, (1997-2002), Senior Fellow in den HP Labs in Palo Alto, Kalifornien (2002-2013), und bis heute Gastwissenschaftler am MSR SVC.

Robert Endre Tarjan ist Fellow der American Academy of Arts and Sciences (1985), Mitglied der National Academy of Sciences (1987) und der National Academy of Engineering (1988). Er ist Träger zahlreicher Preise, darunter des Nevanlinna Prize in Information Science (1983), des National Academy of Sciences Award for Initiatives in Research (1984), des ACM Paris Kanellakis Theory and Practice Award (1999) und der Blaise Pascal Medaille für Mathematik und Informatik der European Academy of Sciences (2004).

Robert Ende Tarjans Vater, George Tarjan (1912-1991) war ein bekannter Kinder-Psychiater, der vor allem in der Erforschung von Entwicklungsstörungen Pionierarbeit leistete. Seine Mutter Helen Tarjan (1918-2009) war Hausfrau.Aus erster Ehe hat Tarjan drei Töchter, Alice Tarjan, Zosia Zawacki und Lily Tarjan. Er ist mit Nayla Rizk verheiratet und liebt Bergwandern, Radfahren und Sudokus.

Robert Endre Tarjan ist ein Erfinder von Algorithmen, Handlungsanweisungen, mit denen Computer mathematische Probleme Schritt für Schritt lösen können. Tarjans Algorithmen behandeln in der Regel graphentheoretische Probleme.

Graphen kann man sich so ähnlich vorstellen wie Straßenkarten oder Rohrleitungsnetze: Knoten (Pumpstationen bzw. Städte) sind durch Kanten (Rohre bzw. Straßen) verbunden. Die Untersuchung von Graphen kann Antworten in vielen mathematischen Bereichen liefern, denn mathematische Fragestellungen lassen sich oft in die Sprache der Graphen übersetzen.

Eine interessante Anwendung sind zum Beispiel Flüsse in gerichteten Graphen: Man lässt durch die „Rohre” im Graphen virtuell Wasser fließen, und jedes Rohr darf nur in eine Richtung durchspült werden. Einige Knoten dienen als Quellen, andere als Abflüsse und der Rest der Knoten dient als Verteiler: Sie leiten das Wasser von den eingehenden Rohren auf die ausgehenden Rohre um. Setzt man nun fest, dass es eine Quelle und einen Abfluss geben soll und dass jedes Rohr nicht mehr als einen gewissen Durchfluss verträgt, dann hat man ein handfestes Problem: Wie viel Wasser kann man durch dieses Rohrnetz schicken? Dieses Problem der „maximalen s-t-Flüsse” wird heute gewöhnlich mit dem Goldberg-Tarjan-Algorithmus gelöst, den Tarjan zusammen mit Andrew Goldberg entwickelt hat. Er ist schnell im mathematischen Sinne und daher inzwischen ein Klassiker der Graphentheorie. Mit einem anderen Algorithmus von Robert Tarjan kann man so genannte „starke Zusammenhangskomponenten” in gerichteten Graphen finden, also die Teile der Graphen, in denen von jedem Knoten aus jeder andere Knoten erreicht werden kann, ohne die Richtung in Einbahnstraßen zu missachten. Berühmt ist auch Tarjans Algorithmus zum Finden „minimaler Spannbäume”, den er zusammen mit David Karger und Philip Klein entwickelt hat. Dieser Algorithmus markiert in einem Graphen genau die Kanten, die man braucht, um von jedem Knoten zu jedem anderen Knoten zu laufen, ohne je in eine Schleife zu geraten. Hat jede Kante im Graphen einen Preis, dann sucht der Algorithmus dabei die Menge an Kanten mit den geringsten Gesamtkosten heraus.