//img.uscri.be/pth/f29c9fda5e1edaca7cadbff590ccceb4d12c3d92
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Les ans du LIPN Analyse d'algorithmesNP et approximation

De
108 pages
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 plus Voir moins

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 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