Idées d’apprentissage actif
Les algorithmes gloutons introduisent les élèves aux problèmes d'optimisation. La stratégie consiste à faire, à chaque étape, le choix qui semble le meilleur sur le moment, sans jamais revenir en arrière. C'est une approche intuitive et souvent efficace, mais qui ne garantit pas toujours la solution optimale globale. L'exemple classique du rendu de monnaie permet d'illustrer parfaitement ce concept.
Activité 01
Les groupes doivent rendre une somme précise avec un système de pièces inhabituel (ex: pièces de 1, 3, 4). Ils découvrent que la méthode gloutonne échoue parfois à donner le minimum de pièces.
Qu'est-ce qu'un choix glouton ?
Activité 02
La classe discute : vaut-il mieux un algorithme très rapide qui donne une bonne solution, ou un algorithme très lent qui donne la meilleure solution ? Utilisation d'exemples comme le GPS.
Un algorithme glouton donne-t-il toujours la solution optimale ?
Activité 03
Les élèves doivent choisir des objets à mettre dans un sac à capacité limitée en maximisant la valeur. Ils comparent leurs stratégies gloutonnes (par poids, par valeur ou par ratio).
Comment implémenter le rendu de monnaie de manière gloutonne ?
Quelques notes pour enseigner cette unité
Attention à ces idées reçues
Croire qu'un algorithme glouton trouve toujours la meilleure solution possible.
C'est le point le plus important. Il faut présenter des contre-exemples (comme le système de monnaie 1, 3, 4 pour rendre 6) où le glouton donne 3 pièces (4+1+1) alors que l'optimal est 2 pièces (3+3).
Penser que 'glouton' signifie que l'algorithme est complexe.
Au contraire, la stratégie gloutonne est souvent très simple à implémenter. Il faut montrer que c'est l'absence de remise en question des choix passés qui définit le caractère glouton.
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
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