Algorithmes de graphes cours MPRI 2007-2008

Pierre Fraigniaud Et Michel Habib [e-mail], [e-mail]

Description

Algorithmes de graphes cours MPRI 2007-2008Algorithmes de graphescours MPRI 2007-2008Pierre Fraigniaud et Michel [e-mail], [e-mail] des rentiers, septembre 2007Algorithmes de graphes cours MPRI 2007-2008Algorithmes de graphescours MPRI 2007-2008Pierre Fraigniaud et Michel [e-mail], [e-mail] des rentiers, septembre 2007Algorithmes de graphes cours MPRI 2007-2008PlanIntroductionQuels algorithmes?Structuration et d´ecompositionPr´esentation du coursProblems and ExercisesGraph RepresentationsAlgorithmes de graphes cours MPRI 2007-2008IntroductionIntroductionQuels algorithmes?Structuration et d´ecompositionPr´esentation du coursProblems and ExercisesGraph RepresentationsAlgorithmes de graphes cours MPRI 2007-2008IntroductionQuestion initialePourquoi ´etudier l’algorithmique de graphes?Algorithmes de graphes cours MPRI 2007-2008IntroductionQuestion initialePourquoi ´etudier l’algorithmique de graphes?Les th´eor`emes de FaginCaract´erisant P et NP en termes de graphes et de logique.Algorithmes de graphes cours MPRI 2007-2008IntroductionQuestion initialePourquoi ´etudier l’algorithmique de graphes?Les th´eor`emes de FaginCaract´erisant P et NP en termes de graphes et de logique.NPThe class of all graph-theoretic properties expressible in existentialsecond-order logic is precisely NP.Algorithmes de graphes cours MPRI ...

Informations

• Publié par: Necher
• Nombre de lectures: 40
• Langue: Français

Extrait

Algorithmes de graphes cours MPRI 2007-2008

Algorithmes de graphes cours MPRI 2007-2008

Pierre Fraigniaud et Michel Habib [e-mail], [e-mail]

Chateau des rentiers, septembre 2007

Algorithmes de graphes cours MPRI 2007-2008

Algorithmes de graphes cours MPRI 2007-2008

Pierre Fraigniaud et Michel Habib [e-mail], [e-mail]

Chateau des rentiers, septembre 2007

Algorithmes de graphes cours MPRI 2007-2008

Plan

Introduction

Quels algorithmes ?

Structurationetde´composition

Presentation du cours ´

Problems and Exercises

Graph Representations

Algorithmes de graphes cours MPRI 2007-2008 Introduction

Introduction

Quels algorithmes ?

Structurationetde´composition

Pr´ ntation d ese u cours

Problems and Exercises

Graph Representations

Algorithmes de graphes cours MPRI

Introduction

Question

initiale

Pourquoi

´etudier

2007-2008

l’algorithmique

de

graphes

?

Algorithmes de graphes cours MPRI 2007-2008

Introduction

Question initiale

Pourquoi´etudierl’algorithmiquedegraphes?

Lesthe´ore`mesdeFagin

Caract´erisantPetNPentermesdegrapheset

de

logique.

Algorithmes de graphes cours MPRI 2007-2008 Introduction

Question initiale

Pourquoi´etudierl’algorithmiquedegraphes?

Lesthe´ore`mesdeFagin Caract´erisantPetNPentermesdegraphesetdelogique.

NP The class of all graph-theoretic properties expressible in existential second-order logic is precisely NP.

onti ursMPRI2raphesco nIrtdocu 00-70280gedsemhtiroglA

P The class of all graph-theoretic properties expressible in Horn existential second-order logic with successor is precisely P.

Question initiale

Pourquoie´tudierl’algorithmiquedegraphes?

Les th´ `mes de Fagin eore Caract´erisantPetNPentermesdegraphesetdelogique.

NP The class of all graph-theoretic properties expressible in existential second-order logic is precisely NP.

Algorithmes de graphes cours MPRI 2007-2008

Introduction

La pratique

Parce qu’il y

a

de

nombreuses

applications

pratiques ! ! !

Algorithmes de graphes cours MPRI 2007-2008

Introduction

L’importancedelamod´elisation

Il est crucial de bien utiliser l’veutre´soudre. que on

toutes

les

informations

du

proble`me

Algorithmes de graphes

Quels algorithmes ?

Quels

◮

cours MPRI 2007-2008

algorithmes

Optimaux

?