Scolarité M2 (sauf MIC, MIDS)
- Mme Chatoux
- bureau 5055
- 01 57 27 93 06
- Mme Prudlo
- bureau 5055
- 01 57 27 93 06
Algorithmique avancée
6 ECTS, semestre 2, 12 semaines
| Prérequis | Algorithmique M1 |
| Validation | CC+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.