Robert Tarjan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Robert Tarjan

Robert Endre Tarjan (né le 30 avril en 1948 à Pomona en Californie) est un informaticien américain. Il a découvert de nombreux algorithmes en théorie des graphes, dont plusieurs portent son nom, tels l'algorithme de Tarjan pour les composantes fortement connexes.

Biographie[modifier | modifier le code]

Robert Tarjan est né à Pomona en Californie, le 30 avril en 1948[1]. Il a obtenu son PhD à l'université de Stanford en 1972 sous la direction de Robert W. Floyd[2]. En 2013, il est professeur en informatique à l'université de Princeton.

Travaux[modifier | modifier le code]

Tarjan s'est beaucoup intéressé aux structures de données et aux algorithmes en général. On lui doit notamment l'analyse de la structure Union-Find, des améliorations des algorithmes de flot (avec Danny Sleator), des travaux sur les arbres équilibrés et la recherche du plus petit ancêtre commun, l'invention avec Michael Fredman des tas de Fibonacci et les premiers résultats sur les algorithmes online[3].

Distinctions[modifier | modifier le code]

En 1982, Robert Tarjan reçoit le premier prix Nevanlinna[4].

Il a reçu le prestigieux prix Turing avec John Hopcroft en 1986, pour leur travaux sur la création et l'analyse de structures de données[5], et le prix Paris Kanellakis en 1999[6].

Notes et références[modifier | modifier le code]

  1. CV disponible sur la page personnelle.
  2. (en) Robert Tarjan sur le site du Mathematics Genealogy Project
  3. Description des résultats de Tarjan dans la notice du prix Turing.
  4. Liste des lauréats du prix Nevanlinna sur la page officielle du prix
  5. Site officiel du prix Turing
  6. Page officielle du prix Kanellakis

Liens externes[modifier | modifier le code]