Claire Mathieu

Collège de France

Informatique et sciences numériques (2017-2018) partenariat Inria

Algorithmes

Les courTs du Collège de France

La 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ées

Mariage stable, partage de gâteau, et comment éviter les regrets

Données incertaines, robustesse et algorithmes stochastiques

Combinatoire des graphes et voyageur de commerce

Physique statistique et algorithmique

Dualité, programmation linéaire, méthodes gloutonnes

et algorithmes en-ligne

Convergence de méthodes itératives et recherche locale

Flux de données, analyses de traffic, et problèmes de données massives

Claire Mathieu

Collège de France

Informatique et sciences numériques (2017-2018) partenariat Inria

Algorithmes

Bibliographie

Les numéros de pages font référence aux diapositives utilisées pour le cours.

p. 4-13 et p. 22

Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"

Sections 13.1 et 13.2

Accéder au site

p. 7-13

Bush V., "As We May Think", juillet 1945

Accéder au site

p. 15-20

Easley-Kleinberg, Section 18.7

p. 23-29

Kanade 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), 2016

Accéder au PDF

p. 30-39

Avin 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), 2015

Accéder au PDF

p. 41

Easley-Kleinberg, Section 16.2

Claire Mathieu

Collège de France

Informatique et sciences numériques (2017-2018) partenariat Inria

Algorithmes

Bibliographie

Les numéros de pages font référence aux diapositives utilisées pour le cours.

p. 4-13 et p. 22

Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"

Sections 13.1 et 13.2

Accéder au site

p. 7-13

Bush V., "As We May Think", juillet 1945

Accéder au site

p. 15-20

Easley-Kleinberg, Section 18.7

p. 23-29

Kanade 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), 2016

Accéder au PDF

p. 30-39

Avin 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), 2015

Accéder au PDF

p. 41

Easley-Kleinberg, Section 16.2

Claire Mathieu

Collège de France

Informatique et sciences numériques (2017-2018) partenariat Inria

Algorithmes

Bibliographie

Les numéros de pages font référence aux diapositives utilisées pour le cours.

p. 4-13 et p. 22

Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"

Sections 13.1 et 13.2

Accéder au site

p. 7-13

Bush V., "As We May Think", juillet 1945

Accéder au site

p. 15-20

Easley-Kleinberg, Section 18.7

p. 23-29

Kanade 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), 2016

Accéder au PDF

p. 30-39

Avin 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), 2015

Accéder au PDF

p. 41

Easley-Kleinberg, Section 16.2

Claire Mathieu

Collège de France

Informatique et sciences numériques (2017-2018) partenariat Inria

Algorithmes

Bibliographie

Les numéros de pages font référence aux diapositives utilisées pour le cours.

p. 4-13 et p. 22

Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"

Sections 13.1 et 13.2

Accéder au site

p. 7-13

Bush V., "As We May Think", juillet 1945

Accéder au site

p. 15-20

Easley-Kleinberg, Section 18.7

p. 23-29

Kanade 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), 2016

Accéder au PDF

p. 30-39

Avin 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), 2015

Accéder au PDF

p. 41

Easley-Kleinberg, Section 16.2

Claire Mathieu

Collège de France

Informatique et sciences numériques (2017-2018) partenariat Inria

Algorithmes

Bibliographie

Les numéros de pages font référence aux diapositives utilisées pour le cours.

p. 4-13 et p. 22

Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"

Sections 13.1 et 13.2

Accéder au site

p. 7-13

Bush V., "As We May Think", juillet 1945

Accéder au site

p. 15-20

Easley-Kleinberg, Section 18.7

p. 23-29

Kanade 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), 2016

Accéder au PDF

p. 30-39

Avin 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), 2015

Accéder au PDF

p. 41

Easley-Kleinberg, Section 16.2

Claire Mathieu

Collège de France

Informatique et sciences numériques (2017-2018) partenariat Inria

Algorithmes

Bibliographie

Les numéros de pages font référence aux diapositives utilisées pour le cours.

p. 4-13 et p. 22

Easley D. et Kleinberg J., "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"

Sections 13.1 et 13.2

Accéder au site

p. 7-13

Bush V., "As We May Think", juillet 1945

Accéder au site

p. 15-20

Easley-Kleinberg, Section 18.7

p. 23-29

Kanade 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), 2016

Accéder au PDF

p. 30-39

Avin 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), 2015

Accéder au PDF

p. 41

Easley-Kleinberg, Section 16.2