Cours G17 Partie 2

Cours Graphes et ApplicationsPartie II – « Graphes Aléatoires »Alexandre Aussemaaussem@univ-lyon1.frThème de recherche : Conception de Modèles pour l’Aide à la DécisionPRISMaUniversité Lyon 11Plan du cours• Les Graphes et l’Optimisation Combinatoire• Les Graphes comme modèles de représentation de connaissances incertaines.• Les Modèles Graphiques pour représenter des distributions de probabilités• L’inférence dans les Réseaux Bayésiens pour le diagnostic des systèmes complexes.• L’apprentissage des Réseaux Bayésiens• Applications2La Théorie des Graphes• Formalisme puissant pour modéliser les systèmes :• Noeuds = entités du système, e.g. machines, routeurs, services, pages Web, pixels, • Arcs = contraintes, liens, communications, interactions• Support à la résolution des nombreux problèmes d’Optimisation Combinatoire– Plus courts chemins, coloration, flots de valeur maximum, couplage maximum, coupes de capacité minimum, affectation etc.• Applications “classiques”– Transports, télécom, réseaux, image, études de pannes, • Applications non usuelles : modélisation dans un univers incertain • Noeuds = variables aléatoires ou états possibles• Arcs = dépendances probabilistes ou transitions aléatoires 3La Théorie des Graphes• La majorité des problèmes de reconnaissance en Optimisation Combinatoire sont dits NP-Complets• NP-Complet : classe d’équivalence des problèmes NP selon la relation transitive « transformation polynomiale »• NP : ...