Ce cours porte sur des techniques avancées dans la conception et l'analyse des algorithmes. Le cours commence par un parcours rapide de quelques notions fondamentales telles que la programmation linéaire ou la NP-complétude et les réductions polynomiales. Au delà de l'analyse de pire cas, on envisage plusieurs approches possibles de l'analyse d'algorithmes, d'une part au travers des notions de complexités: pire-cas, en moyenne, amortie, lissée, ou paramétrique, et d'autre part au travers de mesures de qualités de sortie: optimalité, facteur d'approximation pour l'optimisation, de compétitivité pour l'algorithmique on-line. Le cours abordera entre autres les notions de potentiel, de noyau issu de prétraitement, de largeur arborescente, d'algorithme primal-dual, SAT solvers.
Modalités d'évaluation : Examen sur table à l'issue du cours.
Langue du cours : English unless all students prefer french.
Ressources pédagogiques : Les ressources sont la page moodle mais une ancienne page permet de se faire une idée du style du cours.
Credits ECTS : 4
