Idées d’apprentissage actif
L'étude des algorithmes de tri (insertion et sélection) est un moment clé pour comprendre l'efficacité informatique et la rigueur de la preuve. Ces algorithmes, bien que moins performants que les tris modernes, sont parfaits pour enseigner la manipulation d'index et les structures de boucles imbriquées. Les élèves découvrent que pour organiser des données, il existe plusieurs stratégies avec des logiques différentes.
Activité 01
La moitié de la classe applique le tri par sélection sur un jeu de cartes, l'autre le tri par insertion. Ils comptent le nombre de comparaisons et de déplacements pour comparer l'efficacité réelle.
Comment fonctionne le tri par sélection ?
Activité 02
Un élève doit expliquer l'algorithme du tri par insertion à un camarade en utilisant uniquement des gestes et des objets, sans montrer le code.
Quelle est la différence de principe avec le tri par insertion ?
Activité 03
Atelier 1 : tracer l'exécution sur papier. Atelier 2 : identifier le variant de boucle pour la terminaison. Atelier 3 : coder l'algorithme en Python.
Comment démontrer qu'un algorithme de tri se termine toujours ?
Quelques notes pour enseigner cette unité
Attention à ces idées reçues
Confondre le tri par sélection et le tri par insertion.
Le tri par sélection cherche le plus petit élément pour le placer au début, tandis que le tri par insertion prend l'élément suivant pour le 'glisser' à sa place. Utiliser des animations visuelles aide à distinguer ces deux mouvements.
Penser que le tri par sélection est plus rapide car il fait moins d'échanges.
Bien qu'il fasse moins d'échanges, il fait autant de comparaisons. Il faut montrer que les deux tris ont une complexité quadratique O(n²) pour que les élèves comprennent qu'ils sont équivalents sur de grands volumes.
Méthodes utilisées dans ce dossier
Parcours séquentiel et recherche
Écrire des algorithmes pour parcourir un tableau à la recherche d'un élément, d'un extremum ou pour calculer une moyenne.
8 methodologies
Recherche dichotomique
Mettre en œuvre l'algorithme de recherche dichotomique dans un tableau trié. Comparer son efficacité logarithmique avec la recherche séquentielle.
8 methodologies
Algorithmes gloutons
Résoudre des problèmes d'optimisation à l'aide d'algorithmes gloutons, en s'appuyant sur l'exemple classique du problème du rendu de monnaie.
8 methodologies