Graphes et algorithmes

SEMAINE DES MATHÉMATIQUES 2019

Graphes et algorithmes : consulter / télécharger cet article au format pdf

Cette séquence a été abordée dans une classe de grande section maternelle. Elle est en lien avec la semaine des mathématiques 2019.

Elle fait suite à l’animation pédagogique organisée par l’IEN Mme Chiardola du Cannet en partenariat avec Inria et class’code (14/11/2018)

Cette approche est basée sur les travaux de Dorian Mazauric, de l’Inria de Sophia Antipolis.

L’apprentissage du codage et de la programmation à l’école permet d’acquérir une culture commune du numérique, exerce la pensée complexe et permet aux élèves de devenir des êtres raisonnés et raisonnables.

Ces activités sont débranchées et permettent d’exercer la pensée informatique :

COLORATION DES SOMMETS

Extrait :

  • Lien avec l’allocation de fréquences dans les réseaux sans fil

Nous expliquons une des applications en lien avec l’allocation de fréquence dans les réseaux de télécommunication sans fil. Dans ce type de réseaux, deux émetteurs trop proches ne peuvent pas émettre sur une fréquence identique. En effet, dans ce cas, il y aurait des interf´erences et certaines communications ne seraient alors plus effectuées correctement. Dans ce contexte, il faut alors attribuer une fréquence différente pour chacun des deux émetteurs. De plus, il n’est pas envisageable d’avoir un nombre de fréquences égal au nombre d’émetteurs. Il faut donc attribuer une fréquence à chaque émetteur en respectant toutes les contraintes d’interférence pour tous les émetteurs du réseau tout en minimisant le nombre de fréquences différentes pour y parvenir. Ce problème est modélisé par un problème de coloration de sommets dans un graphe construit a` partir du réseau. Il y a un sommet par émetteur et il y a une arête entre deux sommets si et seulement si les deux émetteurs correspondants a` ces deux sommets sont trop proches pour utiliser la même fréquence. Le problème revient alors a` donner une couleur à chacun des sommets (deux sommets reliés par une arête ont des couleurs différentes) tout en minimisant le nombre total de couleurs utilisées. Les couleurs représentent dans ce contexte les fréquences. Par exemple, si le réseau correspond `a notre graphe d’écrit précédemment, alors le plus petit nombre de couleurs (fréquences) permettant d’obtenir une solution valide est trois.

Voici le projet en classe de grande section maternelle :

Tout d’abord, les élèves se sont exercés avec des feutres, à relier des points entre eux, en suivant un modèle.
Ensuite, je leur ai présenté le jeu de position dans les graphes : coloration des sommets.

Fiche avec points de couleurs donnée aux élèves
 

 


Solution aux jeux

La règle du jeu :

Le joueur doit positionner ses pions sur les sommets du graphe (une couleur par sommet) de telle sorte que, pour chacune des arêtes du graphe, les couleurs aux extrémités de l’arête soit différente.

 

Notions abordées : Logique, persévérance sur la tâche, algorithme, codage

Chaque élève a sa fiche de suivi et entoure chaque réussite.

Matériel utilisé : bouchons, perles de couleur.