Les algorithmes La theorie de la complexite: un peu d'histoire La classe P La classe NP

Les algorithmes La th´eorie de la complexit´e: un peu d’histoire La classe P La classe NP
Complexit´e avanc´ee - UMIN 345
Th´eorie de la NP-Compl´etude (1)
Christophe PAUL
September 21, 2007
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)Les algorithmes La th´eorie de la complexit´e: un peu d’histoire La classe P La classe NP
Bibliographie
A Guide to the Theory of NP-Completenes, M.R. Garey and
D.S. Johnson
Computational Complexity, C. Papadimitriou.
Parameterized Complexity, R. Downey and M. Fellows.
Invitation to Fixed-Parameter Algorithms, R. Niedermeier.
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)Les algorithmes La th´eorie de la complexit´e: un peu d’histoire La classe P La classe NP
1 Les algorithmes
Un exemple
Quelles garanties ?
2 La th´eorie de la complexit´e: un peu d’histoire
3 La classe P
Les r´eductions polynomiales
Les certificats polynomiaux
4 La classe NP
Quelques r´eductions
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaUnclaexemsse PpleLaQu clelasseles gaNPranties ?
Algorithme [tir´e de Wikipedia]
Un algorithme est un moyen pr´esenter la r´esolution par calcul
d’un probl`eme. C’est un ´enonc´e dans un langage bien d´efini d’une
suite d’op´erations permettant de r´esoudre par calcul un probl`eme.
Le mot vient du nom du math´ematicien Al Khuwarizmi, qui, au
IXe si`ecle ´ecrivit le premier ouvrage syst´ematique sur la solution
des ´equations lin´eaires et quadratiques
L’algorithme le plus c´el`ebre est celui qui se trouve dans le livre 7
des El´ements d’Euclide. Il permet de trouver le plus grand
diviseur commun, ou PGCD, de deux nombres.
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)Exemple
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaUnclaexemsse PpleLaQu clelasseles gaNPranties ?
Un tri bizarre...[Chv`atal]
Donn´ees: σ une permutation de [1,n]
0 0R´esultat: une permutation σ telle que σ (1) = 1
tant que σ(1) = 1 faire
Renverser l’ordre des σ(1) premiers ´el´ements
fin
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)6Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaUnclaexemsse PpleLaQu clelasseles gaNPranties ?
Un tri bizarre...[Chv`atal]
Donn´ees: σ une permutation de [1,n]
0 0R´esultat: une permutation σ telle que σ (1) = 1
tant que σ(1) = 1 faire
Renverser l’ordre des σ(1) premiers ´el´ements
fin
Exemple
5 1 6 4 2 3
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)6Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaUnclaexemsse PpleLaQu clelasseles gaNPranties ?
Un tri bizarre...[Chv`atal]
Donn´ees: σ une permutation de [1,n]
0 0R´esultat: une permutation σ telle que σ (1) = 1
tant que σ(1) = 1 faire
Renverser l’ordre des σ(1) premiers ´el´ements
fin
Exemple
5 1 6 4 2 3
2 4 6 1 5 3
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)6Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaUnclaexemsse PpleLaQu clelasseles gaNPranties ?
Un tri bizarre...[Chv`atal]
Donn´ees: σ une permutation de [1,n]
0 0R´esultat: une permutation σ telle que σ (1) = 1
tant que σ(1) = 1 faire
Renverser l’ordre des σ(1) premiers ´el´ements
fin
Exemple
5 1 6 4 2 3
2 4 6 1 5 3
4 2 6 1 5 3
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)6Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaUnclaexemsse PpleLaQu clelasseles gaNPranties ?
Un tri bizarre...[Chv`atal]
Donn´ees: σ une permutation de [1,n]
0 0R´esultat: une permutation σ telle que σ (1) = 1
tant que σ(1) = 1 faire
Renverser l’ordre des σ(1) premiers ´el´ements
fin
Exemple
5 1 6 4 2 3
2 4 6 1 5 3
4 2 6 1 5 3
1 6 2 4 5 3
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)6en temps polynomial, on obtient une 2-approximation du
nombre d’´etapes.
Les algorithmes La th´eorie de la complexit´e: un peu d’histoire LaUnclaexemsse PpleLaQu clelasseles gaNPranties ?
Un tri bizarre...[Chv`atal]
Donn´ees: σ une permutation de [1,n]
0 0R´esultat: une permutation σ telle que σ (1) = 1
tant que σ(1) = 1 faire
Renverser l’ordre des σ(1) premiers ´el´ements
fin
Ce que l’on sait :
nil termine en un nombre fini d’´etapes (possiblement O(2 ))
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)6