Idées d’apprentissage actif
La recherche dichotomique illustre parfaitement la puissance de l'algorithmique. En passant d'une recherche séquentielle à une stratégie de 'diviser pour régner', les élèves découvrent comment réduire drastiquement le temps de traitement sur des données triées. C'est l'occasion de manipuler la fonction logarithme de manière concrète, en observant qu'on peut trouver un élément parmi un million en seulement vingt étapes.
Activité 01
Un élève choisit un nombre entre 1 et 1000. La classe doit le deviner en utilisant la stratégie dichotomique. On note le nombre de tentatives pour valider l'efficacité logarithmique.
Pourquoi le tableau doit-il être trié pour utiliser la dichotomie ?
Activité 02
Les élèves reçoivent trois versions d'un code de recherche dichotomique contenant des erreurs subtiles (indices, conditions). Ils doivent les identifier et les corriger en équipe.
Comment le nombre d'étapes évolue-t-il avec la taille du tableau ?
Activité 03
Les élèves discutent en binôme : est-il rentable de trier un tableau juste pour y faire une seule recherche ? Ils doivent lister les conditions où la dichotomie devient avantageuse.
Comment prouver la terminaison avec un variant de boucle ?
Quelques notes pour enseigner cette unité
Attention à ces idées reçues
Oublier que le tableau doit être impérativement trié.
Si le tableau n'est pas trié, la dichotomie peut éliminer la moitié contenant l'élément. Faire tester l'algorithme sur une liste non triée montre immédiatement pourquoi le résultat est imprévisible.
Se tromper dans la mise à jour des bornes (milieu + 1 ou milieu - 1).
Les élèves oublient souvent d'exclure l'élément central déjà testé. Dessiner l'évolution des bornes sur un axe gradué lors d'une séance de peer-teaching aide à visualiser pourquoi le +1/-1 est nécessaire pour éviter les boucles infinies.
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
Algorithmes de tri
Étudier et implémenter les algorithmes de tri par insertion et par sélection. Analyser leur complexité quadratique et prouver leur terminaison.
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