WikiLuc

Guest connection: login: Guest, password: anonymous

User Tools

Site Tools


agreg:cours:graphes

Agrégation 2014: Graphes

f.hypotheses.org_wp-content_blogs.dir_809_files_2013_03_ccommecomplet.jpg

Luc Bougé 2014/07/07 08:06

Plan du cours

Samedi 28 juin: Luc Bougé, PR ENS Rennes, IRISA

Introduction générale (Contact)

  • Quelques notions de base
  • Questions algorithmiques sur les graphes
  • Exemple 1: Parcours de graphes (DSF, BFS)
  • Exemple 2: Recherche de plus courts chemins (Dijkstra, Floyd)

Mercredi 2 juillet: François Laroussinie, PR Paris 7, LIAFA

siliconwadi.fr_files_2012_09_avraham-trahtman-graph-theory.jpg

Les grands algorithmes sur les graphes: plein d'exemples (Contact)

  • Plus courts chemins
    • À partir d'un noeud (Dijkstra)
    • Entre tous les couples de nœuds (Floyd-Warshall)
  • Arbres couvrants minimaux
    • Méthode de Prim
    • Méthode de Kruskal

Samedi 5 juillet: Olivier Serre, CR CNRS, LIAFA

Graphes et complexité: les graphes comme échelle de référence (Contact)

  • Calculabilité et complexité
  • Le problème Accessibilité
  • PTIME et réductions polynomiales
  • Le problème 2-SAT se réduit au problème Accessibilité
  • NPTIME, NP-complétude, NP-difficulté
  • Le problème 3-SAT est NP-complet et il se réduit au problème Ensemble indépendant
  • Temps vs espace: le problème Accessibilité est dans SPACE(log^2(n)).

Lundi 7 juillet: Anne Bouillard, MCF ENS Paris, LIENS

Introduction aux graphes aléatoires (Contact)

  • Graphes Erdös-Rényi: définition et premières propriétés
  • Graphes Erdös-Rényi: comportement asymptotique
  • Graphes petit-monde

Mardi 8 juillet: Laurent Théry, CR INRIA Sophia-Antipolis

Quelques exemples d'interaction entre graphes et algèbre (Contact)

  • Isomorphisme de graphes
  • Graphe de Cayley
  • Coloriage de graphe
  • Graphe planaire, formule d'Euler
  • Théorème des 5 couleurs, puis des 4 couleurs

Bibliographie

La recherche aujourd'hui, quelques exemples

5e Journée thématique EGC: Fouille de grands graphes, en association avec la 5e conférence sur les Modèles et l’Analyse des Réseaux: Approches Mathématiques et Informatique (MARAMI)

Visualisation de données à très grande échelle, en particulier de graphes: Tulip, développé au LaBRI, Bordeaux. Voir en particulier la bibliothèque d'images.

How do map providers (such as Google or Yahoo! Maps) suggest directions? This question has been an active area of research in the last years. The main idea is to do a preprocessing on the graph once, to speed up all following queries. With this additional information itineraries can be computed very fast. Still, Dijkstra's Algorithm is the basis for all optimisations. […] With modifications along those lines, you can do even cross-country routing in a very reasonable timeframe.

Les grandes références

Introduction To Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, MIT Press, 3e édition, 2009.

mitpress.mit.edu_sites_default_files_imagecache_booklist_node_9780262533058.jpg

C'est le livre de référence pour tous les algorithmes dans ce domaine. Il a pris la succession de la célèbre série de livres de Kunth, The art of programming qui date des années 1980. (Nota: c'est à l'occasion de la publication du tome 2 que Knuth a mis au point le programme TeX.) Notez l'évolution des titres, particulièrement révélatrice. Voir en particulier la section Graph Algorithms:

  • Elementary Graph Algorithms
  • Minimum Spanning Trees
  • Single-Source Shortest Paths
  • All-Pairs Shortest Paths
  • Maximum Flow

La grande référence historique en France de la théorie des graphes est Théorie des graphes et ses applications, Claude Berge, Dunod, 1958. Claude Berge est décédé en 2002. En plus d'être un grand mathématicien, c'est d'un des fondateurs de l'Oulipo. Un homme étonnant!

Le domaine a pris un grand essor avec le livre Graphes et algorithmes, Michel Gondran, Michel Minoux, 4e édition, 2009. Ce livre s'intéresse notamment aux applications de la théorie des graphes à la gestion et l'optimisation du réseau électrique EDF.

Algorithms + Data Structures = Programs

Les algorithmes de graphes se prêtent à de très jolis exercices d'implémentation. Voir par exemple la collection des livres Algorithms de Robert Sedgewick et Kevin Wayne, 4e édition, 2011. Ils proposent des exemples particulièrement élégants et pédagogiques dans une série de langages: C, C++, Java, etc. Un bel exercice de Literate Programming. Voir en particulier le volume 4 Graphs. Noter qu'il existe un cours en ligne à partir de ce livre.

You can take our free Coursera MOOCs. They include a full set of lecture videos and assessments. Algorithms, Part I covers Chapters 1 through 3; Algorithms, Part II covers Chapters 4 through 6.

Algorithmique des graphes

Voir le cours d'algorithmique de L3 de François Laroussinie

  • Arbres binaires de recherche (algorithmes de base + analyse de complexité dans le pire cas et en moyenne)
  • Arbres binaires de recherche équilibrés
  • Introduction aux graphes; parcours en largeur; parcours en profondeur; recherche d'extension linéaire
  • Composantes fortement connexes (algorithme de Tarjan)
  • Arbres couvrants minimaux
  • Plus courts chemins

Le cours est accompagné des présentations et des TD avec leurs corrections. Une mine pour vos cours d'informatique! Vous y trouverez aussi des programmes écrits en Python reprenant les algorithmes vus en cours.

Attention! L'objectif est de fournir une implémentation simple des algorithmes en utilisant les facilités de Python afin de permettre aux étudiants de “jouer” avec les algorithmes, de les faire tourner, de les modifier, etc. En particulier, les complexités des algorithmes ne sont pas toujours respectées. Voir le plan du cours ci-dessous.

  • Parcours en largeur
  • Parcours en profondeur et l'algorithme de recherche d'extension linéaire
  • Algorithme de Tarjan
  • Algorithme de Prim pour les arbres couvrants minimaux
  • Algorithme de Dijkstra pour les plus courts chemins (avec poids non négatifs)

Graphes et complexité

Le livre Complexité algorithmique de Sylvain Perifel, LIAFA, est librement (et légalement!) téléchargeable! Une mine pour vos cours d'informatique, à diffuser à vos élèves. Voir le plan du livre ci-dessous.

static.fnac-static.com_multimedia_images_fr_nr_6c_6f_57_5730156_1540-1.jpg

  1. Le modèle de calcul
  2. Considérations de base sur le temps
  3. NP-complétude
  4. Considérations de base sur l’espace
  5. Uniformité et non-uniformité
  6. Algorithmes probabilistes
  7. Oracles et limites de la diagonalisation
  8. La hiérarchie polynomiale
  9. Comptage
  10. Protocoles interactifs
  11. Bornes inférieures non uniformes
  12. Dérandomisation et bornes inférieures

Graphes aléatoires

assets.cambridge.org_97805217_34431_cover_9780521734431.jpg

Graphes et algèbre

Un très bon point d'entrée est le cours d'Olivier Fouquet, un matheux d'Orsay: Théorie des graphes: une brève introduction (avec un biais algébrique assumé). Il est libremement téléchargeable, avec de nombreux exercices.

agreg/cours/graphes.txt · Last modified: 2017/04/05 17:06 (external edit)