L’objectif de cette UE est de fournir les outils pour concevoir et analyser la performance des algorithmes pour de problèmes d’optimisation quand les données de l’entrée ne sont pas connues d’avance, mais elles arrivent de façon dynamique au fur et à mesure pendant l’exécution de l’algorithme. Différents modèles online seront présentés ainsi que différentes techniques de conception algorithmique aillant de heuristiques simples aux méthodes utilisant la programmation mathématique.
Prérequis
- Algorithmique & Complexité
- Notions d’optimisation combinatoire
Acquis d’apprentissage
- Connaissance de différents modèles online.
- Algorithmes online avec garanties de performance.
- Méthodologies de conception et analyse d’algorithmes sans connaissance préalable de données d’entrée.
- Étudier la difficulté de conception des garanties de performance pour de problèmes online.
Compétences visées
- Modéliser des problèmes complexes (BCC 5 M1-1)
- Concevoir des algorithmes et évaluer leur complexité (BCC 5 M1-1)
- Proposer des solutions informatiques à des problèmes complexes (BCC 5 M1-1)