Home Of Science - Le monde de la science et de la technologie

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. La NP-complétude est ensuite abordée du point de vue pratique de la conception de réductions polynomiales à l'aide de problèmes fondamentaux (SAT, clique, couvertures, sac à dos, voyageur de commerce, chemins hamiltoniens, programmation entière, etc). On envisagera ensuite plusieurs approches 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.

Sommaire :

Partie 1 - Algorithmes

1. Algorithmes gloutons et matroides
2. Plus cours chemins, programmation dynamique
3. Flots et couplages
4. Programmation linéaire

Partie 2 - complexité

1. Préambule
2. NP-Complétude
3. Traiter la NP-Complétude
4. Méthodes probabilistes

Partie 3 - Applications

1. Algorithmes pour la biologie moléculaire
2. Algorithmes pour la physique statistique

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 INF431 ou un cours d'algorithmique de niveau équivalent est utile.