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 uns des paradigmes principaux de l'algorithmique, notamment flots et couplages et programmation linéaire. Il revient ensuite rapidement sur la NP-complétude et notamment sur l'importance des 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. Ce sera l'occasion de présenter entre autres les notions de potentiel, de noyau, de largeur arborescente.
Modalités d'évaluation : Examen sur table à l'issue du cours.
Langue du cours : Français
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
-
Niveau requis : Les prérequis minimaux sont quelques éléments d'algorithmique (manipulations de tableaux, listes, arbres; tris et parcours fondamentaux) et de complexité des algorithmes (bornes supérieures et inférieures à la complexité dans le pire cas pour les tris), et une bonne familiarité avec l'outil mathématique (preuve par induction, etc).
Avoir suivi INF423, INF431 ou des cours d'informatique de niveau équivalent est utile.
This course covers advanced techniques of algorithm design and analysis. The course begins with a quick of some major of algorithmic, including flows and and linear programming. It then quickly reviews NP-complete and in particular on the importance of polynomial reductions. Beyond worst case analysis, we several possible approaches of algorithmic analysis, on the one hand throught complexity notions: worst case, in average, amortized, smoothed or parametric; and on the other throught measures of exit qualities: optimality, approximation factor for optimization, competitivity for online algorithmic. It will be an opportunity to present notions of potential, core, treewidth, among other.
Evaluation modalities: sitting exams at the end of the course
Course language: French
Training ressources: they are on the moodle page but an old page gives you an idea of the style of the course
ECTS credits: 4
- Teaching coordinator: Hummes Flores Bernardo
- Teaching coordinator: Schaeffer Gilles