Skip to content

Manipulation de graphes, recherche de chemin

Une erreur fréquemment observée chez un enseignant stagiaire est de le voir reproduire un schéma vécu dans ces dernières années d'études : le cours magistral.

Cette stratégie pédagogique nécessite de la part des élèves une certaine maturité et une relation aux savoirs déjà bien établie.

Il est tout à fait possible de mettre en place d'autres stratégies où l'élève est davantage acteur de ses apprentissages : c'est en produisant qu'il progressera et apprendra les notions, les concepts, les méthodes.

L'activité présentée ici est une activité issue d'EDUSCOL.

Il s'agit de déterminer le plus court chemin sur un graphe (en présentant l'algorithme de Dijkstra). Au-delà de l'algorithme, cette activité permet de montrer l'universalité de l'informatique : un même algorithme pour différents champs d'application (plus court chemin entre deux villes, algorithme de routage).

Vous trouverez ici :

Cette activité que l'on peut proposer à des élèves de seconde dans le cadre de la SNT ou en terminale au moment de la séquence sur les algorithmes de routage fait manipuler l'algorithme de Dijkstra par les élèves. Il ne s'agit nullement de le programmer. Cela est beaucoup plus compliqué et nécessite de nombreux pré-requis (représentation des graphes, file...).

L'élève est amené à appliquer l'algorithme de Dijkstra graphiquement sur le graphe. Il dispose pour s'aider de la vidéo mentionnée ci-dessus qu'il peut à loisir mettre en pause.

Sans parler de classe inversée, la stratégie pédagogique est de lui mettre à disposition des documents qu'il peut analyser pour questionner sa pratique. Ces documents sont ensuite mis à sa disposition (moodle par exemple) et il peut les consulter à loisir.

Nous pouvons échanger sur cet exemple dans cette discussion dédiée du forum.