Idées d’apprentissage actif
Les algorithmes sur les graphes sont au cœur des technologies de navigation et de recommandation. En Terminale NSI, les élèves apprennent à explorer ces structures via les parcours en largeur (BFS) et en profondeur (DFS). Ils découvrent comment ces méthodes permettent de répondre à des questions fondamentales : existe-t-il un chemin entre deux points ? Le graphe contient-il des cycles ?
Activité 01
La salle de classe est transformée en graphe. Un élève doit trouver la sortie en utilisant strictement un algorithme de parcours en profondeur, en marquant les 'sommets' déjà visités avec des jetons.
Quelle est la différence entre un parcours en largeur et en profondeur ?
Activité 02
Les groupes reçoivent des graphes de dépendances de tâches. Ils doivent appliquer manuellement un parcours pour identifier s'il y a un blocage (cycle) qui empêche de terminer le projet.
Comment détecter un cycle dans un graphe ?
Activité 03
On présente un problème de recherche du chemin le plus court (non pondéré). Les élèves débattent en binômes pour savoir quel parcours est le plus efficace et pourquoi.
Comment trouver un chemin entre deux sommets ?
Quelques notes pour enseigner cette unité
Attention à ces idées reçues
Oublier de marquer les sommets déjà visités.
Cela mène à une boucle infinie si le graphe contient un cycle. Faire vivre cette boucle infinie à un élève lors d'une simulation physique rend l'importance du marquage inoubliable.
Confondre la structure de données utilisée pour BFS et DFS.
BFS utilise une file (FIFO) et DFS une pile (LIFO). Faire manipuler ces deux structures côte à côte pour un même graphe permet de voir immédiatement la différence dans l'ordre de découverte des sommets.
Méthodes utilisées dans ce dossier
Algorithmes sur les arbres
Parcours d'arbres (préfixe, infixe, suffixe, en largeur). Recherche, insertion et suppression dans un arbre binaire de recherche.
8 methodologies
Méthode "Diviser pour régner"
Principe de la méthode diviser pour régner. Application au tri fusion et analyse de la complexité algorithmique.
8 methodologies
Programmation dynamique
Introduction à la programmation dynamique pour l'optimisation. Résolution de problèmes classiques comme le rendu de monnaie ou l'alignement de séquences.
8 methodologies