Calcul d'itinéraire et algorithmes

L'étude du calcul d'itinéraire et des algorithmes comme Dijkstra gagne à être abordée par l'activité concrète. Les élèves manipulent des concepts abstraits (graphes, poids, optimisation) plus facilement quand ils voient leur utilité immédiate dans un jeu de plateau ou une programmation. Cette approche transforme une notion théorique en expérience sensorielle et collaborative, ce qui renforce la mémoire et la compréhension profonde.

• Seconde
• SNT : Culture et Citoyenneté Numérique
• 3 activités
• 30 min–45 min

Objectifs d’apprentissage

1. Comparer la complexité des algorithmes de recherche de chemin le plus court pour différents types de graphes routiers.
2. Expliquer le fonctionnement de l'algorithme de Dijkstra pour trouver le chemin le plus court dans un graphe pondéré.
3. Analyser l'impact des données de trafic en temps réel sur le calcul d'un itinéraire optimal.
4. Concevoir une représentation simplifiée d'un réseau routier sous forme de graphe pour résoudre un problème d'itinéraire.
5. Évaluer la pertinence de différents critères (distance, temps) pour définir le 'meilleur' itinéraire.

Carte conceptuelle

⏱ 40 min·Binômes

Jeu de plateau : Le plus court chemin

Les élèves reçoivent un plateau représentant un réseau routier simplifié avec des poids sur chaque arête (temps ou distance). En binôme, ils cherchent manuellement le chemin le plus court entre deux villes, puis comparent leur solution avec celle obtenue en appliquant l'algorithme de Dijkstra pas à pas.

Préparation et détails

Comment un GPS recalcule-t-il instantanément un itinéraire optimal en cas d'obstacle ou de changement de parcours ?

Conseil de facilitation: Pour le jeu de plateau, circulez entre les groupes pour poser des questions ciblées comme 'Pourquoi avez-vous choisi cette route en premier ?' afin de les faire verbaliser leur stratégie algorithmique.

Setup: Tables avec de grandes feuilles ou espace mural

Materials: Étiquettes de concepts ou post-its, Papier grand format (A3 ou raisin), Marqueurs, Exemple de carte conceptuelle

• Comprendre
• Analyser
• Créer
• Conscience de soi
• Autogestion

Galerie marchande

⏱ 30 min·Petits groupes

Galerie marchande: Les critères d'optimisation

Chaque groupe affiche un poster présentant un itinéraire optimisé selon un critère différent (temps, distance, péages, émissions CO2). Les élèves circulent, annotent les posters avec des post-it et votent pour le critère le plus pertinent selon différents scénarios proposés.

Préparation et détails

Quels algorithmes permettent de trouver le meilleur chemin parmi des milliards de combinaisons possibles dans un réseau routier ?

Conseil de facilitation: Lors de la gallery walk, demandez aux élèves d'annoter les critères d'optimisation affichés avec des exemples concrets de leurs propres trajets pour ancrer la discussion dans leur réalité.

Setup: Espace mural dégagé ou tables disposées en périphérie de la salle

Materials: Papier grand format ou panneaux d'affichage, Feutres et marqueurs, Post-it pour les retours critiques

• Comprendre
• Appliquer
• Analyser
• Créer
• Compétences relationnelles
• Conscience sociale

Carte conceptuelle

⏱ 45 min·Binômes

Programmation guidée : Dijkstra en Python

Les élèves implémentent pas à pas l'algorithme de Dijkstra sur un graphe de 10 nœuds. L'enseignant fournit la structure de données et les élèves complètent la boucle principale. Ils testent ensuite leur code sur le réseau du plateau de jeu pour vérifier la cohérence avec leur résultat manuel.

Préparation et détails

Comment les données de trafic en temps réel modifient-elles les prédictions de durée de trajet ?

Conseil de facilitation: Pendant la programmation guidée, faites tester chaque ligne de code par les élèves en direct pour éviter les erreurs de syntaxe qui masquent les incompréhensions algorithmiques.

Setup: Tables avec de grandes feuilles ou espace mural

Materials: Étiquettes de concepts ou post-its, Papier grand format (A3 ou raisin), Marqueurs, Exemple de carte conceptuelle

• Comprendre
• Analyser
• Créer
• Conscience de soi
• Autogestion

Enseigner ce sujet

Commencez par ancrer le sujet dans le vécu des élèves en leur demandant de partager leurs expériences avec les GPS. Évitez de présenter Dijkstra comme une recette à suivre : privilégiez une approche par résolution de problème où les élèves découvrent l'algorithme en le vivant. Utilisez des métaphores comme 'l'algorithme est un explorateur qui élimine les chemins sans issue' pour rendre l'abstraction plus tangible. Terminez toujours par une mise en perspective : 'Pourquoi les GPS mettent-ils parfois 10 secondes à calculer un itinéraire alors qu'ils ont des milliards de chemins à tester ?' pour ouvrir sur l'efficacité algorithmique.

À quoi s’attendre

Les élèves doivent être capables d'expliquer pourquoi le chemin le plus court n'est pas toujours le plus rapide, de décrire les étapes de l'algorithme de Dijkstra à l'oral ou à l'écrit, et d'identifier les critères d'optimisation pertinents pour différents contextes (voiture, vélo, piéton). Une réussite se voit quand ils relient ces concepts à leur expérience quotidienne avec les GPS.

Attention à ces idées reçues

Idée reçue courante

During le jeu de plateau 'Le plus court chemin', certains élèves pourraient croire que la route la plus courte en distance est automatiquement la meilleure.

Ce qu'il faut enseigner à la place

Pendant le jeu, arrêtez le chronomètre après chaque tour pour demander : 'Si cette route est la plus courte mais qu'elle passe par un centre-ville avec des feux tous les 200 mètres, est-ce vraiment le meilleur choix ? Utilisez l'enseigne 'trafic' sur le plateau pour ajuster votre stratégie.'

Idée reçue courante

During la programmation guidée 'Dijkstra en Python', des élèves pourraient imaginer que l'ordinateur teste toutes les combinaisons possibles de chemins.

Ce qu'il faut enseigner à la place

Pendant la séance de code, affichez un graphe de 4 nœuds au tableau et demandez aux élèves de compter à la main le nombre de chemins possibles. Ensuite, lancez le code avec ce même graphe et observez que l'algorithme s'arrête bien avant d'avoir tout testé, en expliquant pourquoi cette méthode est plus efficace.

Idée reçue courante

During la Galerie marchande 'Les critères d'optimisation', des élèves pourraient penser qu'un seul algorithme convient à tous les types de trajets.

Ce qu'il faut enseigner à la place

Pendant la gallery walk, présentez un itinéraire de 200 km en voiture et un autre de 5 km à vélo. Demandez aux groupes d'identifier les critères prioritaires pour chaque cas et de proposer un algorithme adapté, en comparant leurs propositions avec les algorithmes réels utilisés par les GPS.

Idées d'évaluation

Vérification rapide

Après l'activité 'Le jeu de plateau : Le plus court chemin', présentez un graphe routier simple (4-5 villes) et demandez aux élèves de tracer à la main les étapes de l'algorithme de Dijkstra pour trouver le chemin le plus court entre deux villes. Collectez leurs feuilles pour vérifier la bonne application des étapes.

Question de discussion

Pendant la Galerie marchande 'Les critères d'optimisation', organisez un débat en fin de séance en posant la question : 'Si vous deviez concevoir un GPS pour des vélos, quels seraient les critères les plus importants pour définir le 'meilleur' itinéraire, et comment cela changerait-il l'algorithme par rapport à une voiture ?' Notez les critères émergents au tableau pour évaluer leur capacité à adapter les concepts aux différents contextes.

Billet de sortie

Après la programmation guidée 'Dijkstra en Python', demandez aux élèves d'écrire sur un post-it : 1) Le nom de l'algorithme étudié. 2) Une phrase expliquant pourquoi les données de trafic en temps réel sont cruciales pour un GPS. 3) Un exemple concret où le chemin le plus court n'est pas forcément le plus rapide. Ramassez les post-its pour évaluer leur compréhension des liens entre théorie et application.

Extensions et étayage

• Challenge : Proposez aux élèves de modifier le code Python pour intégrer un critère de sécurité (éviter les routes à fort trafic) et justifient leur choix en comparant deux versions de l'itinéraire.
• Scaffolding : Pour les élèves en difficulté, fournissez un graphe routier avec des poids déjà calculés et demandez-leur de réorganiser les étapes de Dijkstra dans l'ordre correct.
• Deeper exploration : Invitez les élèves à rechercher comment fonctionne l'algorithme A* et à le comparer avec Dijkstra, en expliquant les avantages de chaque approche pour un GPS urbain.

Vocabulaire clé

Graphe	Structure mathématique composée de sommets (ou nœuds) reliés par des arêtes. Dans notre cas, les villes sont des sommets et les routes sont des arêtes.
Algorithme de Dijkstra	Algorithme qui trouve le chemin le plus court entre un sommet de départ et tous les autres sommets d'un graphe dont les poids des arêtes sont non négatifs.
Poids d'une arête	Valeur associée à une arête dans un graphe, représentant par exemple la distance ou le temps de trajet entre deux sommets.
Nœud	Point dans un graphe, représentant par exemple une intersection ou une ville. Également appelé sommet.
Heuristique	Technique de résolution de problèmes qui utilise une approche pratique, souvent plus rapide mais pas garantie d'être optimale, comme l'algorithme A*.