Pour l'UE ISEC , c'est ici.

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

Dans cette UE, nous nous intéresserons aux ressources de calcul (temps, espace mémoire, ...) 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, ou même des ordinateurs à venir (problèmes exponentiels). 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, etc. 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 de diverses spécialités du master.

Equipe pédagogique

Semainier indicatif

Ressources

Quelques références