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

pages

Français

Documents

Écrit par
Christophe Paul

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

Français

Les algorithmes La theorie de la complexite: un peu d'histoire La classe P La classe NP Complexite avancee - UMIN 345 Theorie de la NP-Completude (1) Christophe PAUL September 21, 2007 Christophe PAUL Complexite avancee - UMIN 345 Theorie de la NP-Completude (1)

complexite avancee - umin

systematique sur la solution des equations lineaires

classe np

theorie de la complexite

theorie de la np-completude

Voir

Publié par

pefav

Nombre de lectures

Langue

Français

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 certiﬁcats 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´eﬁni 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
ﬁn
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
ﬁn
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
ﬁn
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
ﬁn
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
ﬁn
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
ﬁn
Ce que l’on sait :
nil termine en un nombre ﬁni d’´etapes (possiblement O(2 ))
Christophe PAUL Complexit´e avanc´ee - UMIN 345 Th´eorie de la NP-Compl´etude (1)6