Education
Claire Mathieu Collège de France Informatique et sciences numériques (2017-2018) partenariat Inria Algorithmes Les numéros de pages font référence aux diapositives utilisées pour le cours. Étude de deux problèmes d'algorithmique distribuée par des algorithmes utilisant l'aléa : Définition et applications du problème du stable maximal (p. 5 à 11) Présentation et analyse de l'algorithme de Luby pour le problème du stable maximal (p. 12 à 27) Présentation de l'algorithme "des mouches drosophiles" pour le problème du stable maximal (p. 4 et p. 28) Esquisse de l'algorithme distribué pour Pagerank (p. 34 à 42) Bibliographie Algorithmes distribués pour le problème du stable maximal : Luby, Michael. ”A simple parallel algorithm for the maximal independent set problem.” SIAM journal on computing 15.4 (1986): 1036-1053. Accéder au PDF Afek Y, Alon N, Barad O, Hornstein E, Barkai N, Bar-Joseph Z (2011), "A biological solution to a fundamental distributed computing problem." Science 331: 183–185. Accéder au site Un algorithme distribué pour le calcul de la popularité des pages du Web : H. Ishii and R. Tempo, “Distributed randomized algorithms for the PageRank computation,” IEEE Trans. Autom. Control, vol. 55, no. 9, p. 1987–2002, 2010. Accéder au PDF