Complexité, Algorithmes Randomisés et Approchés (COMPLEX)

Mots-clés.

classes de complexité, problèmes NP-difficiles, algorithmes exacts, approchés et randomisés.

Langue d’enseignement.

Français.

Résumé.

Dans cette UE de M1, nous nous intéresserons aux ressources de calcul (essentiellement temps de calcul) nécessaires pour résoudre les problèmes algorithmiques. Nous tâcherons en particulier de distinguer les problèmes dits “faciles”, que l’on peut résoudre en temps “raisonnable” (avec un algorithme dont la complexité est une fonction polynomiale de la taille de l’instance du problème), des problèmes dits “difficiles", dont le temps de calcul croît extrêmement (exponentiellement) vite avec la taille de l’instance à résoudre. Nous introduirons les classes de complexité fondamentales P et NP et nous définirons la NP-complétude. La plupart des problèmes algorithmiques rencontrés en pratique sont NP-difficiles. Nous nous intéresserons alors aux compromis et relations entre différents “modes" de calculs : que se passe-t-il si l’on s’autorise à utiliser des algorithmes probabilistes, si l’on est satisfait de solutions approchées plutôt qu’exactes, si l’on est satisfait d’un algorithme qui marche seulement pour la plupart des entrées possibles, mais pas pour toutes, etc. Ce cours introduira quelques techniques de résolution exacte (branch and bound), d’approximation et de randomisation permettant de contourner la difficulté de résolution des problèmes difficiles, et permettant ainsi leur application en pratique avec des temps de calcul raisonnables (algorithmes de type Las Vegas, Monte Carlo, approximation avec garantie de performance, etc). Ces algorithmes seront illustrés sur un éventail de problèmes concrets relevant de divers parcours du master.

Pré-requis : Bases en algorithmique.

Semainier.

Modalités d’évaluation.

Projet, et deux examens répartis.

Répartition horaire.

 

Équipe pédagogique.

L’équipe pédagogique est constituée de :


Ce document a été traduit de LATEX par HEVEA