Aller au contenu  Aller au menu Aller à la recherche

accès rapides, services personnalisés

Rechercher

Recherche détaillée

Contact

Jacqueline Collet-Narboni
Responsable administrative

courriel : jacqueline.collet-narboni@upmc.fr

Cette page est la page de garde du site consacré à l' unité d'enseignement « Complexité, Algorithmes Randomisés et Approchés (4I900) »

Ressources annuelles

Responsable de l'UE : Perret, ludovic



Description de l'UE :

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 (algorithmes de type Las Vegas, Monte Carlo, approximation avec garantie de performance, etc). Ces techniques seront illustrées en TD et dans des TME-projets sur un éventail de problèmes concrets relevant de diverses spécialités du master.


Semainier indicatif :

  • Semaine 1 : Modèle d'un ordinateur : les machines de Turing
  • Semaine 2 : Classes de complexité et réductions
  • Semaine 3 : Algorithmes approchés avec garantie de performance
  • Semaine 4 : Méthodes arborescentes
  • Semaine 5 : Algorithmes faiblement exponentiels
  • Semaine 6 : Algorithmes randomisés (I)
  • Semaine 7 : Algorithmes randomisés (II)
  • Semaine 8 : Classes probabilistes
  • Semaine 9 : Protocoles Zero-Knowledge
  • Semaine 10 : Bilan