URI http://ori.unit-c.fr/uid/unit-ori-wf-1-4335 Cours d´algorithmique des graphes du MPRI fre Dans de nombreux domaines tels que la chimie, la biologie, les réseaux de télécommunications ou encore les réseaux sociaux des modèles à base de graphes sont utilisés quotidiennement en recherche. De même les graphes constituent des outils importants et très utilisés de modélisation en informatique. Pour s'en convaincre il sufit de considérer la place faite aux algorithmes sur les graphes dans les ouvrages classiques d'algorithmique. En effet malgré la simplicité apparente de leur définition, les graphes capturent une large part de la complexité algorithmique. Il est donc très important de bien comprendre la structure des graphes afin d'utiliser des modélisations pertinentes à base de graphes. Ce module a deux objectifs principaux : le premier concerne la compréhension de la complexité structurelle des graphes via des décompositions de graphes et les invariants de graphes associés, tandis que le deuxième est centré sur la conception d'algorithmes "efficaces" sur les graphes et l'étude des outils algorithmiques nécessaires. algorithmique complexité théorie des graphes décomposition modulaire algorithme décomposition modulaire largeur arborescente algorithme LexBFS modélisation fuscia LOMv1.0 linear LOMv1.0 3 LOMFRv1.0 texte LOMv1.0 final LOMv1.0 author BEGIN:VCARD N:Gambette;Philippe FN:Philippe Gambette EMAIL;TYPE=INTERNET:Philippe.Gambette@lirmm.fr ORG:lirmm END:VCARD 2009-01-23 LOMv1.0 author BEGIN:VCARD N:Habib;Michel FN:Michel Habib EMAIL;TYPE=INTERNET:habib@liafa.jussieu.fr ORG:Liafa jussieu END:VCARD 2006-01-23 URI http://ori.unit-c.fr/uid/unit-ori-wf-1-4336 LOMv1.0 validator BEGIN:VCARD VERSION:3.0 N:sduranton;Sylvain Duranton FN:Sylvain Duranton sduranton ORG:Mon université URL:http://www.univ.fr UID:sduranton END:vcard LOMv1.0 creator BEGIN:VCARD VERSION:3.0 N:fuscia;fuscia FN:fuscia fuscia ORG:Mon université URL:http://www.univ.fr UID:fuscia EMAIL;TYPE=INTERNET: END:VCARD LOMv1.0 LOMFRv1.0 SupLOMFRv1.0 fre application/pdf http://philippe.gambette.free.fr/SCOL/Graphes.pdf LOMv1.0 lecture LOMv1.0 learner LOMv1.0 higher education LOMFRv1.0 master SupLOMFRv1.0 bac+5 18 ans et + LOMv1.0 difficult fre LOMFRv1.0 apprendre LOMv1.0 no LOMv1.0 yes Document libre, dans le cadre de la licence Creative Commons (http://creativecommons.org/licenses/by-nd/2.0/fr/) Pas d'utilisation commerciale - Paternité, Pas de modification. LOMv1.0 isbasedon URI http://mpri.master.univ-paris7.fr/C-2-29-1.html Cours d' Algorithmique des graphes dans le cadre du Master Parisien de Recherche en Informatique (MPRI) Ces notes ont été prises à l'occasion des cours d'algorithmique des graphes du Master Parisien de Recherche en Informatique en 2006/2007, donnés par Michel Habib (8 séances de 90 minutes) LOMv1.0 discipline Classification UNIT 1305 Programmation : Algorithmique, langages, conception objet, programmes LOMv1.0 discipline Classification UNIT 1205 Graphes, arbres et simulation discrète LOMv1.0 discipline CDD 22e éd. 518.1 Algorithms LOMv1.0 discipline CDD 22e éd. 511.5 Graph theory