Archive 2022
PrérequisAlgorithmique M1
ValidationCC+examen
Horaires hebdomadaires 2 h CM , 2 h TD
Années M1 Mathématiques et Informatique M1 Mathématiques et Informatique M1 MIC

Syllabus

L'algorithmique des données massives, des flots, de la cryptologie utilisent la randomisation (les tirages aléatoires), et l'approximation pour traîter des problèmes qui sans cela seraient difficiles. Ce cours est approche systématique de ces méthodes et des méthodes de traitement distribuées.

Sommaire

  • Algorithmes randomisés
  • Algorithmes d'approximation
  • Algorithmes en ligne (online)
  • Algorithmes PRAM (parallèle)
  • Algorithmes distribués
  • Générations aléatoires et structures

Bibliographie

  • Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge university press.
  • Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge university press.
  • Mitzenmacher, M., & Upfal, E. (2017). Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press.