Daniel Sleator

informaticien américain

Daniel Dominic Kaplan Sleator est un informaticien, professeur d'informatique à l'université Carnegie-Mellon de Pittsburgh, né le 10 décembre 1953 à Saint-Louis (Missouri)[1].

Daniel Sleator
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Nationalité
Domicile
Formation
Activités
Fratrie
William Sleator (en)Voir et modifier les données sur Wikidata
Autres informations
A travaillé pour
Directeur de thèse
Distinction

Biographie

modifier

Sleator a obtenu un B. Sc. à l'université de l'Illinois et un Ph. D. en 1981 à l'université Stanford sous la direction de Robert Tarjan[2] avec pour titre An O(nm logn) Algorithm for Maximum Network Flow.

De 1981 à 1985, il a travaillé aux Bell Laboratories avant de devenir professeur à Carnegie-Mellon, où il est professeur émérite.

Sleator est le frère cadet de William Sleator (en), qui a écrit de la science-fiction pour jeunes adultes.

Activité scientifiques

modifier

Daniel Sleator est l'un des pionniers de l'analyse amortie des algorithmes, dont les premiers exemples sont les analyses de l'heuristique move-to-front (« déplacer vers l'avant ») et les arbres splay[3]. Il a conçu, avec Robert Tarjan, diverses autres structures de données, en plus des arbres splay, dont les arbres de liaison-coupe (en) et les tas asymétriques.

L'article de Sleator et Tarjan sur l'heuristique move-to-front est l'un des premiers à comparer un algorithme en ligne et un algorithme hors ligne optimal[4], pour lequel le terme competitive analysis (en) a été proposé dans un article de Karlin, Mark S. Manasse, Larry Rudolph et Daniel Sleator[5]. Sleator a également développé une théorie de grammaires à liens (en)[6] avec Dave Temperley et un analyseur de musique appelé Serioso pour analyser la mesure et l'harmonie dans la musique écrite.

Prix et distinctions

modifier

En 1999, Sleator est co-lauréat avec Robert Tarjan du prix Paris-Kanellakis de l'ACM pour l'invention de la structure de données des arbres splay[7].

Autres activités

modifier

Sleator a commercialisé un serveur d'échecs en ligne alimenté au départ par des bénévoles dans l'Internet Chess Club, ce qui a suscité des protestations de contributeurs bénévoles. L'Internet Chess Club est depuis devenu l'un des serveurs d'échecs commerciaux sur Internet les plus performants.

Sleator a également été un contributeur actif de la plateforme de programmation compétitive Codeforces[8].

Références

modifier
  1. D'après American Men and Women of Science, Thomson Gale, 2004.
  2. (en) « Daniel Dominic Kaplan Sleator », sur le site du Mathematics Genealogy Project
  3. Daniel D. Sleator et Robert E. Tarjan, « Self-Adjusting Binary Search Trees », Journal of the ACM, vol. 32, no 3,‎ , p. 652–686 (DOI 10.1145/3828.3835, S2CID 1165848, lire en ligne)
  4. Daniel D. Sleator et Robert E. Tarjan, « Amortized efficiency of list update and paging rules », Communications of the ACM, vol. 28, no 2,‎ , p. 202–208 (DOI 10.1145/2786.2793, S2CID 2494305, CiteSeerx 10.1.1.367.6317, lire en ligne).
  5. Anna R. Karlin, Mark S. Manasse, Larry Rudolph et Daniel D. Sleator, « Competitive snoopy caching », Algorithmica, vol. 3, no 1,‎ , p. 79–119 (DOI 10.1007/BF01762111, MR 925479, S2CID 33446072).
  6. Link Grammar Bibliography
  7. Citation pour Sleator et Tarjan sur le prix Paris Kanellakis de l'ACM.
  8. (en) « Darooha », Codeforces (consulté le ).

Liens externes

modifier