| Complexité, Algorithmes Randomisés et Approchés (COMPLEX, 4I900) - 2018/2019 |
Dans cette UE, nous nous intéresserons aux ressources de calcul (essentiellement, le 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 avec une quantité raisonnable de
ressources (problèmes dont la complexité est une fonction polynomiale de
la taille du problème), des problèmes dits "difficiles", qui sont hors de
portée des ordinateurs existants. 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 "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 randomisés, 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 ?
Ce cours introduira des techniques d'algorithmes
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. Ces techniques seront illustrées en TD et en TME-projet sur un éventail de
problèmes concrets relevant des diverses spécialités du master.