--- title: Outils de visualisation de graphes, mise en forme de l'article GEP lang: fr-FR tags: graphes, GEP --- [TOC] --- # 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/ ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd3b4.png) Ce site crée par Frédéric Zinelli est disponible sur gitlab. Il propose de nombreuses fonctionnalités : - de nombreuses modélisations de graphes en python qui permettent de revoir les structures de dictionnaires et de de list de list ; - différents algorithmes (sauf parcours en largeur et en profondeur) sur les graphes avec des explications pas à pas et en français; - création de graphes personnalisés afin de pouvoir corriger un exercice précis ou de tester différentes situations. 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/ ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd3b2.png) Ce site en français permet de : - créer des graphes personnalisés, les importer et les exporter mais avec un formalisme différent de celui de python; - faire tourner le parcours en largeur ou en profondeur sur un graphe personnalisé afin de pouvoir corriger un exercice précis ou de tester différentes situations; - faire tourner de nombreux autres algorithmes dont notamment l'algorithme de Dijkstra. 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](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd369.png) 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](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd368.png) puis sous forme de liste d'adjacence avec un dictionnaire de list (capture de gauche) ou une list de list (capture de droite). ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd36e.png) 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 - Plus-values pédagogiques (enseignants / élèves) - Investissement plus important de la part des élèves car l’interactivité dynamise l’explication. - Développement de l’autonomie, de la réflexion et de la créativité des élèves. - Traitement de notions potentiellement difficiles avec un autre angle d’approche ce qui facilite leur appropriation. - Les freins - L’activité nécessite des ressources spécifiques, telles que du matériel, une connexion internet et un accès aux différentes plateformes en ligne. - Prise en main d'un nouvel outil numérique qui est partiellement en anglais : certains élèves peuvent être intimidés par la prise en main d'un nouvel outil et se montrer réticents. - Autonomisation : certains élèves manquent d'autonomie et préférant des méthodes d’enseignement plus traditionnelles, ils expriment parfois une certaine réserve face à une approche plus expérimentale et participative. - Taille de la classe : l’activité peut être plus difficile à gérer dans de grandes classes où le nombre d’élèves est élevé. Il peut être plus complexe d’assurer un suivi individuel ainsi que la participation active de tous les élèves. ### 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. ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd37e.png) 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). ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd380.png) Ensuite on choisit l'algorithme du parcours en largeur parmi les différents algorithmes : ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd381.png) 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. ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd383.png) À 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 - Plus-values pédagogiques (enseignants / élèves) - Intérêt accru de la part des élèves car l’interactivité dynamise l’explication ; - Développement de l’autonomie, de la réflexion et de la créativité des élèves qui peuvent inventer des exemples ; - Visualisation de l’exécution pas à pas des algorithmes qui améliore leur compréhension. - Les freins - L’activité nécessite des ressources spécifiques, telles que du matériel, une connexion internet et un accès aux différentes plateformes en ligne. - Prise en main d'un nouvel outil numérique : certains élèves peuvent être intimidés par la prise en main d'un nouvel outil et se montrer réticents. - Autonomisation : certains élèves manquent d'autonomie et préférant des méthodes d’enseignement plus traditionnelles, ils expriment parfois une certaine réserve face à une approche plus expérimentale et participative. - Taille de la classe : l’activité peut être plus difficile à gérer dans de grandes classes où le nombre d’élèves est élevé. Il peut être plus complexe d’assurer un suivi individuel ainsi que la participation active de tous les élèves. ### 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 : ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd3ac.png) 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 : ![](https://minio.apps.education.fr/codimd-prod/uploads/aec5f2305faeb817399d87c1d.png) On peut aussi cliquer sur "rapport complet" pour avoir les résultats intermédiaires qui ont permis d'avoir la solution : ![](https://minio.apps.education.fr/codimd-prod/uploads/2ff181ab1c07c339365dfd3a8.png) 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 - Plus-values pédagogiques (enseignants / élèves) - Investissement plus important de la part des élèves car l’interactivité dynamise l’explication. - Développement de l’autonomie, de la réflexion et de la créativité des élèves. - Visualisation de l’exécution pas à pas des algorithmes qui améliore leur compréhension. - Les freins - L’activité nécessite des ressources spécifiques, telles que du matériel, une connexion internet et un accès aux différentes plateformes en ligne. - Prise en main d'un nouvel outil numérique : certains élèves peuvent être intimidés par la prise en main d'un nouvel outil et se montrer réticents. - Autonomisation : certains élèves manquent d'autonomie et préférant des méthodes d’enseignement plus traditionnelles, ils expriment parfois une certaine réserve face à une approche plus expérimentale et participative. - Taille de la classe : l’activité peut être plus difficile à gérer dans de grandes classes où le nombre d’élèves est élevé. Il peut être plus complexe d’assurer un suivi individuel ainsi que la participation active de tous les élèves.