Les ans du LIPN Analyse d'algorithmesNP et approximation

108

pages

Français

Documents

Écrit par
Sophie Toulouse

Publié par
profil-urra-2012

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

108

pages

Français

Ebook

Lire un extrait

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

Publié par

profil-urra-2012

Nombre de lectures

Langue

Français

Les 20 ans du LIPN Analyse d'algorithmesNP et approximation pour le meilleur et pour le pire OCAD Sophie Toulouse LIPN, UMR 7030 Les 20 ans du LIPN – p. 1/25

problèmes difficiles d'optimisation combinatoire

algorithmes efficaces

plan introduction

univ-paris13

résolution effective

Voir

Publié par

profil-urra-2012

Nombre de lectures

Langue

Français

Toulouse

Les 20 ans du LIPN
Analyse d’algorithmesNP et approximation
pour le meilleur et pour le pire
OCAD
Sophie Toulouse
sophie.toulouse@lipn.univ-paris13.fr
LIPN, UMR 7030
Les 20 ans du LIPN – p. 1/25Plan
Introduction
•
Problèmes difﬁciles d’optimisation combinatoire
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difﬁciles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difﬁciles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Déﬁnition de nouveaux outils d’analyse
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difﬁciles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Déﬁnition de nouveaux outils d’analyse
Résolution effective
•
Algorithmes efﬁcaces (solution, bornes)
•
Intégration à des schémas de résolution exacte (pilotage)
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difﬁciles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Déﬁnition de nouveaux outils d’analyse
Résolution effective
•
Algorithmes efﬁcaces (solution, bornes)
•
Intégration à des schémas de résolution exacte (pilotage)
Conclusion
Les 20 ans du LIPN – p. 2/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
Les 20 ans du LIPN – p. 3/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
•
NP : déciders∈S polynomial, calculerf(s) polynomial
Les 20 ans du LIPN – p. 3/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
•
NP : déciders∈S polynomial, calculerf(s) polynomial
∗ ∗
•
Optimisation : on cherches telle quef(s ) est optimale surS
Les 20 ans du LIPN – p. 3/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
•
NP : déciders∈S polynomial, calculerf(s) polynomial
∗ ∗
•
Optimisation : on cherches telle quef(s ) est optimale surS
Problèmes
Les 20 ans du LIPN – p. 3/25