Ressource
stage MathC2+ . Activité débranchée . Article ou présentation . Vidéo . 2016, 12 Décembre . Bonne feuille . algorithme distribué de Borůvka . MathC2+Et si on construisait un réseau électrique ? Une histoire de graphes et algorithmes.
Présenter, expliquer et jouer avec les graphes et les algorithmes : Dorian Mazauric, partage avec nous.
Dorian, pourquoi cette action autour des graphes et algorithmes ?
« Ces notions sont centrales en informatique et sont très importantes pour un grand nombre d’applications concernant les réseaux de télécommunication (réseau sans fil, réseau optique, réseau du Web), les réseaux électriques, les réseaux routiers, en biologie (structurale) et pour résoudre un grand nombre de problèmes en général. L’objectif est de présenter des problèmes de graphes et des algorithmes sous la forme la plus simple et la plus ludique possible. »
Une publication « Graphes et Algorithmes – Jeux grandeur nature » présente des activités qui peuvent se décliner dans trois espaces : l’espace d’une feuille de papier, l’espace d’un plateau de jeu et l’espace grandeur nature (par exemple avec des cerceaux et des lattes en plastique). Et pour compléter un jeu de slides de médiation scientifique pour comprendre les graphes et les algorithmes de manière ludique
Un aperçu en image avec une activité mise en place par Dorian Mazauric dans le cadre du stage MathC2+ à Inria Sophia Antipolis – Méditerranée (2016).
Dorian, expliquez nous cette activité
« Le but est de construire un réseau électrique qui relie toutes les villes et dont le coût de construction soit le plus petit possible. Un graphe est utilisé pour représenter le réseau. Chaque ville est représentée par un sommet (un cerceau) et les arêtes sont les lignes électriques qu’il est possible de construire (les lattes en plastique). Chacune de ces lignes a un coût : par exemple en milliers d’euros.
En termes de graphes, construire un réseau électrique optimal revient à calculer un arbre couvrant de poids minimal. Pour résoudre ce problème, les élèves utilisent l’algorithme distribué de Borůvka. »
Crédits image Dorian Mazauric.
