Atelier Ariane et le minotaure ou comment parcourir un graphe

L’atelier est animé par Luc BOUGÉ, professeur d’informatique et chargé de mission pour la promotion de l’enseignement de la discipline informatique, CNRS IRISA, ENS Rennes.

Résumé

La théorie des graphes est un domaine particulièrement fructueux à l’interface entre la science mathématique et la science informatique. Nous nous intéresserons dans cet atelier au problème du parcours de graphe. Nous verrons qu’il existe différents algorithmes qui dérivent en fait d’un même schéma commun instancié par des structures de données différentes. Nous étudierons les propriétés de ces algorithmes, leur coût et leurs applications. Nous verrons en particulier comment Thésée peut utiliser son fil pour explorer l’ensemble du labyrinthe et la taille de fil qu’il faut alors prévoir… et comment vous pouvez explorer toutes les stations du métro lillois de manière efficace.

Documents

Voici quelques références utiles :

• La page Minotaure du site Mythologica.fr

• Illustrations et animations © David Pichardie, ENS Rennes
  • illustrations(PDF, 2 Mo)
  • parcours récursif en profondeur animé (PDF, 2 Mo)
  • parcours en largeur animé (PDF, 2 Mo)

• « Algorithms » livre en ligne de Robert Sedgewick and Kevin Wayne dans sa 4e édition.
  • Le chapitre sur les graphes
  • Le site compagnon propose des ressources : synopsis en ligne, implémentations en Java, data de test, exercices et solutions, visualisations dynamiques, slides, feuille e route de programmation … et notamment un MOOC en 2 parties (voir Online Course).

Sans oublier la conférence donnée le matin de l’atelier : Science mathématique et science informatique : un couple d’avenir !