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