But du cours
Fournir aux élèves-ingénieurs les bases de mathématiques indispensables à la résolution de problèmes fréquents dans tous les domaines de l'optimisation en informatique.
Acquis d'apprentissage visés
- Savoir modéliser un problème concret (logistique, réseau, machine learning, etc.) comme un problème d’optimisation (choix de variables, fonction objectif, contraintes) et formuler cette modélisation en un langage mathématique approprié.
- Maîtriser les problématiques d’optimisation discrète / combinatoire : modélisation par programmation linéaire, programmation en nombres entiers, graphes, flots.
- Analyser la complexité algorithmique des problèmes d’optimisation et distinguer les cas faciles vs difficiles (ex : NP-complet, pseudo-polynomial).
Prérequis
Théorie des ensembles et algèbre
Programme
- Modélisation mathématique de problèmes d’optimisation.
- Théories des Graphes.
- Notations de Landau et théorie de la complexité
- Optimisation linéaire (programmation linéaire, PLNE, descente de gradient)
- Programmation dynamique
Modalités d'évaluation
2 Ecrits (1h/1h)
Bibliographie
An Introduction to Linear Programming and Game Theory, Third Edition (2008) - Paul R. Thie, G. E. Keough - Wiley
Supports
Diaporamas de cours + fascicules TD + fascicules de TP disponibles sous Moodle