Archive 2022
RequirementsAlgorithmique M1
Program requirementsCC+examen
Weekly hours 2 h CM , 2 h TD
Years 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.

Contents

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

Bibliography

  • 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.