Inroduction influence des parametres Problemes algorithmes parametres Complexite parametree et approximation

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

Inroduction - influence des parametres Problemes, algorithmes parametres Complexite parametree et approximation Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345) Christophe PAUL (CNRS - LIRMM) November 4, 2008 Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)

complexite parametree

inroduction - influence des parametres problemes

parametre specifique au probleme

algorithmes parametres

fixed-parameter algorithms

croissance exponentielle du temps de calcul

Voir

Publié par

pefav

Nombre de lectures

Langue

Français

Fellows Complexité paramétrée

Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
Introduction a la complexite parametree (1)
(Complexite avancee - UMIN 345)
Christophe PAUL
(CNRS - LIRMM)
November 4, 2008
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
Bibliographie
Parameterized Complexity, R. Downey and M. Fellows, 1999.
Invitation to Fixed-Parameter Algorithms, R. Niedermeier,
2006.
Parameterized Complexity Theory, J. Flum and M. Grohe,
2006.
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
1 Inroduction - in uence des parametres
2 Problemes, algorithmes parametres
3 Complexite parametree et approximation
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)\L’idee fondamentale est de restreindre l’explosion combinatoire,
semble-t-il inevitable, qui est responsable de la croissance
exponentielle du temps de calcul, a un parametre speci que au
probleme. . . "
R. Niedermeier
Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
\Mesurer la complexite seulement en fonction de la taille de la
donnee signi e ignorer tout information structurelle sur l’instance
donnee. . . "
J. Flum and M. Grohe
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
\Mesurer la complexite seulement en fonction de la taille de la
donnee signi e ignorer tout information structurelle sur l’instance
donnee. . . "
J. Flum and M. Grohe
\L’idee fondamentale est de restreindre l’explosion combinatoire,
semble-t-il inevitable, qui est responsable de la croissance
exponentielle du temps de calcul, a un parametre speci que au
probleme. . . "
R. Niedermeier
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)2 nombre de variables : n = nombre de variables
nIl y a 2 a ectations possibles
nSi on se restreint a 3-sat, la complexite tombe a O(1; 49 )
3 nombre de clauses : m = nombre de clauses
mOn obtient une complexite en O(1; 24 )
4 longueur de la formule : l = nombre total de litteraux
lOn obtient une complexite en O(1; 08 )
5 structure de la formule : parametres bases par exemple sur
la structure du graphe de dependances. . .
Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
L’exemple de sat
Mesure de la complexite en fonction de di erents parametres:
1 taille des clauses : k = nombre max. de litteraux par clause
k = 2: sat2 P
k > 3: sat2 NP-complet
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)