Semestre 8 – Option – Algorithmique avancée

Objectifs

Unité de l’algorithmique de haut niveau.

Présentation de méthodes algorithmiques pour résoudre problèmes NP-difficiles : algorithmes exacts et exponentiels et algorithmes à paramètre fixé.

Étude des méthodes, outils et objets des « algorithm engineering » (algorithmique experimentelle).

Prérequis

Unité de l’algorithmique (niveau L3) et Algorithmique et complexité (M1 – Semestre 7).

Contenu pédagogique de l’UE

  • Problèmes NP-complets. Comment construire un algorithme pour résoudre un problème difficile ?
  • Algorithmes à paramètre fixé : méthodes de construction et analyse, branching, kernelisation, noyau, complexité paramétrisée.
  • Algorithmes exacts et exponentiels : méthodes de construction et analyse, branching, programmation dynamique, inclusion-exclusion.
  • Algorithm engineering : introduction, application : algorithmes de plus court chemin, algorithmes flot.