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