Robert Tarjan : La grammaire des algorithmes efficaces

Demandez à n'importe quel étudiant en informatique de parcourir un graphe avec une recherche en profondeur et, qu'il le sache ou non, il exécute une technique que Robert Tarjan a transformée d'une curiosité en une discipline. Son article de 1972 « Depth-first search and linear graph algorithms » se lit aujourd'hui comme un texte de grammaire fondamental — le genre de travail si profondément absorbé par le domaine que le nom de son auteur a presque disparu de la façon dont les gens en parlent, même si son nom est attaché à une demi-douzaine de structures qu'ils utilisent quotidiennement.

Le chemin d'un mathématicien vers les machines

Robert Endre Tarjan est né le 30 avril 1948 à Pomona, en Californie, de George Tarjan, un pédopsychiatre spécialisé dans la déficience intellectuelle ; son frère cadet James est devenu grand maître d'échecs. Tarjan voulait être astronome quand il était enfant, jusqu'à ce que les colonnes de puzzles de Martin Gardner dans Scientific American et un professeur inspirant de huitième année ne l'orientent vers les mathématiques. Il a obtenu une licence en mathématiques à Caltech en 1969, puis est allé à Stanford pour une maîtrise en informatique en 1971 et un doctorat en 1972, avec une thèse sur les algorithmes de planarité supervisée par Robert Floyd et Donald Knuth. Il décrira plus tard son choix de domaine simplement : l'informatique était une façon de faire des mathématiques qui pouvait avoir un impact pratique — une phrase qui sert également de description à l'ensemble de son œuvre.

Construire la boîte à outils

La carrière de Tarjan, qui a traversé Cornell, UC Berkeley, Stanford, AT&T Bell Labs, NYU, NEC Research Institute, Microsoft Research, Compaq, Hewlett Packard et Intertrust Technologies avant de s'installer à Princeton en 1985 en tant que professeur distingué James S. McDonnell, a produit un ensemble d'algorithmes et de structures de données inhabituel par le nombre d'entre eux qui sont devenus une infrastructure porteuse plutôt que des curiosités théoriques. Son nom est attaché à l'algorithme de Tarjan pour trouver des composantes fortement connexes dans un graphe, un algorithme hors ligne pour calculer les ancêtres communs les plus proches, et un algorithme en temps linéaire pour trouver des ponts — toutes des techniques basées sur le cadre de recherche en profondeur qu'il a formalisé. En 1975, il a donné la première analyse exacte de la structure de données union-find combinée à la compression de chemin, prouvant son temps d'exécution amorti presque constant en utilisant la fonction d'Ackermann inverse, un résultat si étroitement lié aux performances réelles qu'il sous-tend désormais tout, de l'algorithme d'arbre couvrant minimal de Kruskal aux optimisations de compilateurs. Avec Daniel Sleator aux Bell Labs, il a co-inventé les splay trees, des arbres de recherche binaires auto-ajustables qui se rééquilibrent par l'utilisation plutôt que par le port de métadonnées d'équilibre explicites, et avec eux, il a été le pionnier de l'analyse compétitive, un cadre pour juger les algorithmes en ligne face à un adversaire omniscient. Avec Michael Fredman, il a développé les tas de Fibonacci en 1985, une structure de file d'attente prioritaire qui a rendu l'algorithme du chemin le plus court de Dijkstra et les algorithmes d'optimisation de réseau asymptotiquement plus rapides que tout ce qui existait auparavant. Son manuel, Data Structures and Network Algorithms, a remporté le prix Frederick W. Lancaster et est devenu une lecture standard dans le domaine.

La percée de la planarité avec Hopcroft

La réalisation unique la plus explicitement créditée dans sa citation du prix Turing est un travail conjoint avec John Hopcroft : le premier algorithme en temps linéaire pour tester si un graphe peut être dessiné sur un plan sans croisement d'arêtes, publié en 1974. Le test de planarité était un problème lent et difficile avant que leur algorithme ne le réduise à une question de parcours en profondeur minutieux — une technique si centrale à leur solution que la formalisation antérieure de la recherche en profondeur par Tarjan est devenue, rétrospectivement, l'outil qui a rendu le résultat Hopcroft-Tarjan possible. Les deux ont partagé le prix ACM Turing 1986 « pour des réalisations fondamentales dans la conception et l'analyse d'algorithmes et de structures de données », une citation qui crédite un ensemble de travaux conjoints et parallèles plutôt qu'un seul article.

Reconnaissance sur quatre décennies

Tarjan a été le premier récipiendaire du prix Nevanlinna en sciences de l'information en 1983, honorant des contributions exceptionnelles aux aspects mathématiques de l'informatique. Il a remporté le prix Turing en 1986, a été élu à l'American Academy of Arts and Sciences en 1985, à la National Academy of Sciences en 1987 et à la National Academy of Engineering en 1988. Il a reçu le prix Paris Kanellakis en théorie et pratique en 1999 et le prix des anciens élèves distingués de Caltech en 2010. Son dossier de publication dépasse 250 articles avec des dizaines de milliers de citations, et il détient plus d'une douzaine de brevets américains dans les structures de données et la sécurité, reflétant une carrière qui a évolué avec fluidité entre la théorie académique à Princeton et la recherche appliquée dans des laboratoires industriels comme Bell Labs, NEC et Microsoft.

Pourquoi Robert est qualifié de génie

Le cas de Tarjan pour ce mot repose sur quelque chose de spécifique : il n'a pas seulement résolu des problèmes difficiles individuels, il a identifié la machinerie combinatoire sous-jacente — recherche en profondeur, analyse amortie, auto-ajustement — qui a rendu rapides des classes entières d'algorithmes auparavant lents, et il l'a fait à plusieurs reprises sur quatre décennies plutôt qu'une seule fois. L'analyse union-find et l'algorithme de planarité Hopcroft-Tarjan restent du matériel de manuel précisément parce qu'ils ne sont pas des astuces intelligentes mais des techniques générales que d'autres chercheurs pourraient réutiliser ; cette réutilisabilité, plus que tout résultat unique, est ce que les comités du prix Nevanlinna et du prix Turing récompensaient. La complication honnête est que son résultat le plus célèbre, l'algorithme de planarité en temps linéaire, est explicitement un travail conjoint avec John Hopcroft, et la citation du prix Turing crédite les deux hommes conjointement plutôt que de couronner l'un ou l'autre comme un génie solitaire — le prix lui-même est la preuve que le domaine considère cela comme une réalisation collaborative, et non comme une invention singulière. Les autres résultats marquants de Tarjan ont été construits de la même manière avec des co-auteurs nommés : les splay trees avec Daniel Sleator, les tas de Fibonacci avec Michael Fredman. Ce qui est incontesté, c'est la densité pure des résultats fondamentaux, toujours enseignés, portant son nom, un record que peu dans le domaine ont égalé.

Héritage

Chaque étudiant en informatique qui apprend la recherche en profondeur, l'union-find, les splay trees ou les tas de Fibonacci est, en effet, toujours enseigné par les articles de Tarjan, des décennies après leur rédaction. Son travail se situe sous les compilateurs, le routage réseau et les systèmes d'information géographique sans que la plupart de ses utilisateurs ne connaissent son nom — le destin silencieux des mathématiques au niveau de l'infrastructure qui ont parfaitement réussi. Il a continué à produire de nouveaux résultats bien après ses soixante-dix ans, alternant entre le corps professoral de Princeton et des rôles de scientifique en chef chez Intertrust Technologies et chercheur chez Microsoft et Hewlett Packard, une forme de carrière qui plaide elle-même contre le fait de le traiter comme une figure purement académique : une grande partie de son travail le plus cité a été réalisé, testé et appliqué au sein de laboratoires de recherche industrielle plutôt que dans un vide universitaire. Cette double vie, publiant des mathématiques rigoureuses tout en brevetant des systèmes pratiques, fait partie de ce qui sépare son dossier des théoriciens dont les idées sont restées confinées aux revues.