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] .
Biographie
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
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
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
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
↑ 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, 1985 , 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, 1985 , 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, 1988 , 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 13 avril 2020 ) .
Liens externes
Adleman , Diffie , Hellman , Merkle , Rivest et Shamir (1996)
Lempel et Ziv (1997)
Bryant , Clarke , Emerson et McMillan (en) (1998)
Sleator et Tarjan (1999)
Karmarkar (2000)
Myers (2001)
Franaszek (2002)
Miller , Rabin , Solovay et Strassen (2003)
Freund et Schapire (2004)
Holzmann , Kurshan (de) , Vardi et Wolper (2005)
Robert Brayton (2006)
Bruno Buchberger (2007)
Corinna Cortes et Vladimir Vapnik (2008)
Bellare et Rogaway (2009)
Kurt Mehlhorn (2010)
Hanan Samet (2011)
Andrei Broder , Moses Charikar et Piotr Indyk (2012)
Robert D. Blumofe et Charles E. Leiserson (2013)
James Demmel (2014)
Michael Luby (2015)
Amos Fiat et Moni Naor (2016)
Scott Shenker (2017)
Pevzner (2018)
Noga Alon , Phillip Gibbons , Yossi Matias et Mario Szegedy (2019)
Yossi Azar (de) , Andrei Broder , Anna Karlin , Michael Mitzenmacher et Eli Upfal (2020)
Avrim Blum (en) , Irit Dinur , Cynthia Dwork , Frank McSherry , Kobbi Nissim et Adam Davison Smith (2021)
Michael Burrows , Paolo Ferragina (it) et Giovanni Manzini (it) (2022)
Guy Blelloch (en) , Laxman Dhulipala et Julian Shun (2023)