Les ans du LIPN Analyse d'algorithmesNP et approximation

Sophie Toulouse

Description

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

Sujets

• Toulouse

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 8
• Langue: Français

Extrait

Les 20 ans du LIPN
Analyse d’algorithmesNP et approximation
pour le meilleur et pour le pire
OCAD
Sophie Toulouse
[e-mail]
LIPN, UMR 7030
Les 20 ans du LIPN – p. 1/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Définition de nouveaux outils d’analyse
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Définition de nouveaux outils d’analyse
Résolution effective
•
Algorithmes efficaces (solution, bornes)
•
Intégration à des schémas de résolution exacte (pilotage)
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Définition de nouveaux outils d’analyse
Résolution effective
•
Algorithmes efficaces (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