Daniel Sleator
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].
| Naissance | |
|---|---|
| Nationalité | |
| Domicile | |
| Formation | |
| Activités | |
| Fratrie |
William Sleator (en) |
| A travaillé pour | |
|---|---|
| Directeur de thèse | |
| Distinction |
Biographie
modifierSleator 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
modifierDaniel 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
modifierEn 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
modifierSleator 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- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Daniel Sleator » (voir la liste des auteurs).
- D'après American Men and Women of Science, Thomson Gale, 2004.
- (en) « Daniel Dominic Kaplan Sleator », sur le site du Mathematics Genealogy Project
- 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)
- 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).
- 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).
- Link Grammar Bibliography
- Citation pour Sleator et Tarjan sur le prix Paris Kanellakis de l'ACM.
- (en) « Darooha », Codeforces (consulté le ).
Liens externes
modifier
- Ressources relatives à la recherche :
- La page de Daniel Sleator à la CMU
- Le club d'échecs Internet
- Prix Paris-Kanellakis Théorie et Pratique
- Émission de radio "left out"
