Descriptif de l’expérimentation

1. Introduction

Les graphes sont couramment utilisés pour modéliser des structures relationnelles comme par exemple le réseau routier, le réseau électrique, Internet, les réseaux sociaux etc. Sur ces structures, de nombreux problèmes peuvent être étudiés comme la recherche d’un plus court chemin, ou le parcours d’un labyrinthe notamment.

Aussi les graphes et les algorithmes sur les graphes se retrouvent dans de nombreuses thématiques du programme de terminale NSI. Si les élèves ont facilement des intuitions sur l’utilisation des graphes, ils ont en revanche beaucoup de difficultés à les formaliser, notamment à cause de l’abstraction.

Le but de cet article est de présenter deux outils de visualisation de graphes expérimentés en classe afin d’aider les élèves à développer leurs capacités d’abstraction ainsi que leur autonomie. Nous les illustrons avec différentes activités liées aux points-clés du programme et pour chacune d’elle, nous proposons des intentions pédagogiques ainsi qu’un retour d’expérience sur les plus-values et les freins pédagogiques.

2. Description des plateformes

Premier site : https://frederic-zinelli.gitlab.io/algographe/

Ce site crée par Frédéric Zinelli est disponible sur gitlab. Il propose de nombreuses fonctionnalités :

Une fois que le graphe est créé, le site permet de passer d’une représentation à l’autre pour le même graphe. La syntaxe python étant respectée, les élèves ont ainsi un outil pour visualiser le graphe correspondant à un résultat que peut leur rendre un programme qu’ils sont en train de tester par exemple !

Pour une plus ample présentation du site, aller voir la documentation : https://frederic-zinelli.gitlab.io/algographe/docs/

Second site : https://graphonline.top/fr/

Ce site en français permet de :

Remarque : pour les deux sites on peut exporter les graphes et mettre le fichier dans le cahier de texte pour que les élèves puissent reproduire les situations chez eux.

3. Quelques activités pratiques

Activité 1 : Diverses implémentations de graphes

L’objectif de cette activité est de passer d’une représentation de graphe à une autre. Elle a lieu après avoir introduit le vocabulaire sur les graphes et prépare au TP d’implémentations en python de graphes.

Pour commencer nous remobilisons les notions de secondes. On trace la représentation des liens entre des amis sur un réseaux social.

Cela nous a donné le graphe suivant :
graphe1

Les élèves vont ensuite visualiser à l’aide de la première plateforme (https://frederic-zinelli.gitlab.io/algographe/) l’implémentation sous forme de matrice d’adjacence :
Matrice-adjacence

puis sous forme de liste d’adjacence avec un dictionnaire de list (capture de gauche) ou une list de list (capture de droite).

Cela donne l’occasion de comparer les deux représentations et de discuter des avantages et inconvénients de chacune.

À l’issue de cette première approche, les élèves ont dû écrire les différentes représentations de plusieurs graphes et comparer leurs résultats à ceux de la plateforme. Ils ont ainsi pu s’approprier les différentes représentations de graphes (représentation graphique et représentation en python) mais aussi la plateforme.

Intentions pédagogiques

Cette activité permet de travailler le changement de représentation de matrice vers liste d’adjacence et vice versa. L’utilisation de la plateforme permet de réduire e niveau d’abstraction qui est géré par la machine. Elle permet aussi de responsabiliser les élèves dans leur apprentissage en leur permettant de s’exercer, de tester et de vérifier autant que nécessaire en classe mais aussi à la maison.

Retour d’expérience

Activité 2 : Parcours en largeur

L’objectif de cette activité est de s’approprier l’algorithme du parcours en largeur. Elle a lieu après avoir manipulé les graphes implémentés via listes de voisins et matrices d’adjacence. Si les arbres ont été traités avant, on peut réutiliser la notion de parcours en largeur sur les arbres et demander aux élèves de généraliser aux graphes en posant la question : quelle est la grande différences entre les arbres et les graphes ? (la possibilité de cycler).

Après avoir présenté l’algorithme sur un graphe sans cycle puis un graphe avec cycle et donné une implémentation python (les élèves adaptent aux autres représentations par eux-mêmes), on demande aux élèves d’appliquer l’algorithme sur différents graphes et de vérifier la réponse à l’aide de la seconde plateforme (https://graphonline.top/fr/).

Sur ce site, le formalisme est différent mais expliqué en français.

On peut reprendre le graphe de l’activité précédente (capture de gauche), et même déplacer les sommets pour qu’il ressemble à son apparence précédente (capture de droite).

Ensuite on choisit l’algorithme du parcours en largeur parmi les différents algorithmes :

On choisit le sommet de départ et enfin une animation colorée et ludique s’exécute et l’ordre du parcours s’affiche.

À l’issue de cette première approche, les élèves ont dû appliquer le parcours en largeur à plusieurs graphes et comparer leurs résultats à ceux de la plateforme. Ils ont ainsi pu s’approprier le déroulé de l’algorithme.

Remarque : une activité identique peut être faite pour le parcours en profondeur. Elle n’est pas détaillée ici.

Intentions pédagogiques

Cette activité permet de travailler le parcours en largeur. L’utilisation de la plateforme permet de faire tourner l’animation bien plus clairement qu’une explication au tableau. Les élèves peuvent rejouer l’animation sur les exemples vus en classe mais aussi sur d’autres exemples. Cela leur permet non seulement de voir clairement le déroulé de l’algorithme en réduisant les efforts d’analyse et d’abstraction à faire mais aussi de pouvoir tester autant que nécessaire chez eux, ce qui réduit les contraintes de temps et autonomise les élèves.

Retour d’expérience

Activité 3 : plus courts chemins

L’objectif de cette activité est de conclure la séquence sur les graphes en faisant le lien avec les protocoles de routage et en particulier celui utilisé par OSPF : l’algorithme de Dijkstra.
Elle a lieu après l’activité sur les parcours en largeur et en profondeur.

Tout d’abord, on fait le lien entre les graphes représentant des réseaux, qui sont des graphes pondérés et les modélisations que nous avons utilisées. Afin de pouvoir pondérer nos graphes nous devons utiliser les matrices d’adjacence.

On peut prendre l’exemple suivant :

On choisit ensuite l’algorithme de Dijkstra, puis le sommet initial, puis le sommet final. On a alors une animation avec un carré jaune qui se déplace sur le plus court chemin :

On peut aussi cliquer sur “rapport complet” pour avoir les résultats intermédiaires qui ont permis d’avoir la solution :

Après avoir montré aux élèves le fonctionnement du site, les élèves ont dû appliquer l’algorithme de calculs des plus courts chemins sur différents graphes et vérifier la réponse à l’aide du site. Ainsi ils sauront s’entraîner et s’auto-corriger sur des sujets supplémentaires selon leurs besoins lors de leur révisions.

Intentions pédagogiques

Cette activité permet de faire le lien entre la séquence sur les protocoles de routage et celle sur les graphes. L’utilisation de la plateforme permet de responsabiliser les élèves dans leur apprentissage en leur permettant de s’exercer, de tester et de vérifier autant que nécessaire tout en réduisant le niveau d’abstraction qui est géré par la machine.

Retour d’expérience