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

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesBibliographieLes numéros de pages font référence aux diapositives utilisées pour le cours.p. 4-13 et p. 22Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"Sections 13.1 et 13.2Accéder au sitep. 7-13Bush V., "As We May Think", juillet 1945Accéder au sitep. 15-20Easley-Kleinberg, Section 18.7p. 23-29Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., "Distance in the Forest Fire Model: How far are you from Eve?", ACM-SIAM SODA (Symposium on Discrete Algorithms), 2016Accéder au PDFp. 30-39Avin C., Keller B., Lotker Z., Mathieu C., Peleg D., Pignolet Y.-A., "Homophily and the Glass Ceiling Effect in Social Networks", ITCS (Innovations in Theoretical Computer Science), 2015Accéder au PDFp. 41Easley-Kleinberg, Section 16.2

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesBibliographieLes numéros de pages font référence aux diapositives utilisées pour le cours.p. 4-13 et p. 22Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"Sections 13.1 et 13.2Accéder au sitep. 7-13Bush V., "As We May Think", juillet 1945Accéder au sitep. 15-20Easley-Kleinberg, Section 18.7p. 23-29Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., "Distance in the Forest Fire Model: How far are you from Eve?", ACM-SIAM SODA (Symposium on Discrete Algorithms), 2016Accéder au PDFp. 30-39Avin C., Keller B., Lotker Z., Mathieu C., Peleg D., Pignolet Y.-A., "Homophily and the Glass Ceiling Effect in Social Networks", ITCS (Innovations in Theoretical Computer Science), 2015Accéder au PDFp. 41Easley-Kleinberg, Section 16.2

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesBibliographieLes numéros de pages font référence aux diapositives utilisées pour le cours.p. 4-13 et p. 22Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"Sections 13.1 et 13.2Accéder au sitep. 7-13Bush V., "As We May Think", juillet 1945Accéder au sitep. 15-20Easley-Kleinberg, Section 18.7p. 23-29Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., "Distance in the Forest Fire Model: How far are you from Eve?", ACM-SIAM SODA (Symposium on Discrete Algorithms), 2016Accéder au PDFp. 30-39Avin C., Keller B., Lotker Z., Mathieu C., Peleg D., Pignolet Y.-A., "Homophily and the Glass Ceiling Effect in Social Networks", ITCS (Innovations in Theoretical Computer Science), 2015Accéder au PDFp. 41Easley-Kleinberg, Section 16.2

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesBibliographieLes numéros de pages font référence aux diapositives utilisées pour le cours.p. 4-13 et p. 22Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"Sections 13.1 et 13.2Accéder au sitep. 7-13Bush V., "As We May Think", juillet 1945Accéder au sitep. 15-20Easley-Kleinberg, Section 18.7p. 23-29Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., "Distance in the Forest Fire Model: How far are you from Eve?", ACM-SIAM SODA (Symposium on Discrete Algorithms), 2016Accéder au PDFp. 30-39Avin C., Keller B., Lotker Z., Mathieu C., Peleg D., Pignolet Y.-A., "Homophily and the Glass Ceiling Effect in Social Networks", ITCS (Innovations in Theoretical Computer Science), 2015Accéder au PDFp. 41Easley-Kleinberg, Section 16.2

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesBibliographieLes numéros de pages font référence aux diapositives utilisées pour le cours.p. 4-13 et p. 22Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"Sections 13.1 et 13.2Accéder au sitep. 7-13Bush V., "As We May Think", juillet 1945Accéder au sitep. 15-20Easley-Kleinberg, Section 18.7p. 23-29Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., "Distance in the Forest Fire Model: How far are you from Eve?", ACM-SIAM SODA (Symposium on Discrete Algorithms), 2016Accéder au PDFp. 30-39Avin C., Keller B., Lotker Z., Mathieu C., Peleg D., Pignolet Y.-A., "Homophily and the Glass Ceiling Effect in Social Networks", ITCS (Innovations in Theoretical Computer Science), 2015Accéder au PDFp. 41Easley-Kleinberg, Section 16.2

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesBibliographieLes numéros de pages font référence aux diapositives utilisées pour le cours.p. 4-13 et p. 22Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"Sections 13.1 et 13.2Accéder au sitep. 7-13Bush V., "As We May Think", juillet 1945Accéder au sitep. 15-20Easley-Kleinberg, Section 18.7p. 23-29Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., "Distance in the Forest Fire Model: How far are you from Eve?", ACM-SIAM SODA (Symposium on Discrete Algorithms), 2016Accéder au PDFp. 30-39Avin C., Keller B., Lotker Z., Mathieu C., Peleg D., Pignolet Y.-A., "Homophily and the Glass Ceiling Effect in Social Networks", ITCS (Innovations in Theoretical Computer Science), 2015Accéder au PDFp. 41Easley-Kleinberg, Section 16.2

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesBibliographieLes numéros de pages font référence aux diapositives utilisées pour le cours.p. 4-13 et p. 22Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"Sections 13.1 et 13.2Accéder au sitep. 7-13Bush V., "As We May Think", juillet 1945Accéder au sitep. 15-20Easley-Kleinberg, Section 18.7p. 23-29Kanade V., Levi R., Lotker Z., Mallmann-Trenn F., Mathieu C., "Distance in the Forest Fire Model: How far are you from Eve?", ACM-SIAM SODA (Symposium on Discrete Algorithms), 2016Accéder au PDFp. 30-39Avin C., Keller B., Lotker Z., Mathieu C., Peleg D., Pignolet Y.-A., "Homophily and the Glass Ceiling Effect in Social Networks", ITCS (Innovations in Theoretical Computer Science), 2015Accéder au PDFp. 41Easley-Kleinberg, Section 16.2

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesLes 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)BibliographieAlgorithmes 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 PDFAfek 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 siteUn 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

Claire MathieuCollège de FranceInformatique et sciences numériques (2017-2018) partenariat InriaAlgorithmesLeçon inauguraleLa recherche en conception et analyse d'algorithmes a beaucoup évolué ces dernières années. De nouveaux modèles de calcul sont apparus, car les données, désormais trop massives pour tenir en mémoire en un seul lieu, sont d'accès plus difficile que dans les modèles classiques ; ou elles sont accessibles partiellement, modulo certaines incertitudes (algorithmes stochastiques). Pour les problèmes les plus difficiles, on apprend à se contenter de solutions approchées, ou de solutions qui ne marchent en temps raisonnable qu'en posant des hypothèses supplémentaires. Des méthodes de conception plus sophistiquées se sont également développées : méthodes de type Monte-Carlo, méthodes de type primal-dual de la programmation linéaire, ou hiérarchie de relaxations semi-définies. À travers des exemples de quelques problèmes phares, on montrera la diversité des techniques. Les séances seront largement indépendantes les unes des autres. Les questions suivantes seront abordées :Reconstruction de données cachéesMariage stable, partage de gâteau, et comment éviter les regretsDonnées incertaines, robustesse et algorithmes stochastiquesCombinatoire des graphes et voyageur de commercePhysique statistique et algorithmiqueDualité, programmation linéaire, méthodes gloutonneset algorithmes en-ligneConvergence de méthodes itératives et recherche localeFlux de données, analyses de traffic, et problèmes de données massives