01 - Algorithmes

Épisode de Informatique et sciences numériques (2017-2018) - Claire Mathieu par Collège de France · 28 novembre 2017 · 59 min

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

Autres épisodes de « Informatique et sciences numériques (2017-2018) - Claire Mathieu »

À propos du podcast

Ancienne élève de l'ENS et titulaire d'une thèse en informatique de l'université Paris-Sud, Claire Mathieu, actuellement directrice de recherches au CNRS, a travaillé comme chercheur CNRS à l'ENS-Lyon et comme professeur dans des institutions diverses : ENS (professeur attaché), Université…

Informatique et sciences numériques (2017-2018) - Claire Mathieu

Épisodes similaires

Tous les épisodes de Informatique et sciences numériques (2017-2018) - Claire Mathieu · Plus de podcasts Éducation