Institut de Recherche sur l’Enseignement des Mathématiques de Lille

Accueil > Activités > Journées Académiques > Journées académiques 2017 > Atelier Ariane et le minotaure ou comment parcourir un graphe

Atelier Ariane et le minotaure ou comment parcourir un graphe

jeudi 16 février 2017, par Emmanuel Ostenne

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 :

  • « 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 !

Un message, un commentaire ?

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?