tous. UE conseillée pour les parcours ACR, ADOC, IICW.
Pré-Requis
Notions de base en compléxité et analyse d'algorithmes (ULIN501).
Controle connaissances
3
Description de l'UE :
Semestre
Code
Intitulé
Cours
TD
TP
TER
S3
UMINR333
Complexité avancée
15h
-
-
Detail du programme
Objectifs : Contenu :
Objectif
La complexité algorithmique est née dans les années 70 avec le théorème de Cook-Levin et le succès de la notion de NP-complétude.
Après le développement un peu anarchique dans les années 80-90 de nouvelles classes de complexité, il semblerait que l'on
revienne à l'étude des questions fondamentales et que les succès s'accumulent.
L'étude des algorithmes probabilistes a permis l'obention de résutlats négatifs sur l'approximation de problèmes NP-complet
(le théorème PCP). Un algorithme polynomial a été proposé pour tester si un nombre est premier (2001). Il n'est pas exclu
que l'on arrive à démontrer prochainement que l'intersection de NP et co-NP soit égale à P, et pourquoi pas P=NP ?
Cettte théorie est cruciale pour tous ceux qui concoivent des algorithmes, car elle fixe les bornes de notre possible.
Plan
1. Rappels sur la théorie de la complexité
2. Complexite paramétrée
3. Algorithmes probabilistes (le théorème PCP)
4. Sur quelques preuves non-constructives de l'existence d'algorithmes polynomiaux (travaux de Seymour et Robertson)
5. Bilan sur les conjectures actuelles et conséquences dans les applications (crytpographie)
