Objectifs pédagogiques :
Résolution de problème concret
Questionnement autour des solutions : existence, unicité, construction, complexité
Raisonnements algorithmiques et logiques
A la fin de sa journée, un crêpier dispose d'une pile désordonnée de crêpes. Le crêpier étant un peu psycho-rigide, il décide de ranger sa pile de crêpes, de la plus grande (en bas) à la plus petite (en haut).
Pour cette tâche, le crêpier peut faire une seule action : glisser sa spatule entre deux crêpes et retourner le haut de la pile.
Des planchettes en bois représenteront les crêpes.
Pour bien comprendre le problème posé, la première étape consiste, assez naturellement, à « jouer avec » et à chercher, en tâtonnant, des solutions dans les cas simples.
On laisse donc les élèves manipuler les crêpes et essayer de trouver de façon systématique, à chaque étape, la crêpe en dessous de laquelle il faut placer la spatule, de façon à arriver, en un nombre fini d'instructions, à remettre la pile dans l'ordre.
S'ils bloquent, on peut les conseiller. Par exemple : « essaye d'abord de mettre la grande crêpe en bas », ou bien « où doit se trouver la grande crêpe pour pouvoir l'amener en bas ? » ou ensuite: « où doit-on placer la spatule pour retourner judicieusement la pile ? »
Remédiation
Le groupe essaie maintenant d'écrire une séquence d'instructions qui constituera l'algorithme à appliquer pour résoudre le problème.
Un algorithme pourrait être :
1. amener la plus grande crêpe en haut de la pile
2. retourner toute la pile - la crêpe est rangée
3. recommencer en ignorant les crêpes rangées
Complément :
On peut aller plus loin en évaluant la performance d'un algorithme ( suivant le niveau des élèves) :
Demandez de calculer le nombre de coups nécessaires pour ranger la pile de crêpes.
Le nombre de coups dépendant de l'état initial, faites-les généraliser en trouvant le nombre de coups maximal pour ranger une crêpe, puis n crêpes.
• Pour le problème du crêpier : pour ranger une crêpe, il faut entre 0 coup (la crêpe est déjà rangée) et 2 coups (amener en haut, amener à sa place) ;
• pour n crêpes (cas général), il faut entre 0 coup (meilleure situation) et 2 n coups (pire situation). La performance de l'algorithme dépend donc beaucoup de l'état initial, mais on s'intéresse surtout aux cas intermédiaires, qui sont les plus probables.
• Ici, n est une variable qui exprime la taille du problème. La performance d'un algorithme est notée comme une fonction de la taille du problème nommée O. Pour le crêpier, on peut donc écrire O(2n)
On complique la tâche en imaginant que chaque crêpe a deux faces différentes : l'une est brûlée, l'autre non.
Le crêpier veut trier ses crêpes en ayant systématiquement la face brûlée en dessous.
Refaire les quatre étapes avec cette nouvelle règle du jeu.
L'algorithme est alors du type :
1. amener la plus grande crêpe en haut de la pile
2. mettre la face brûlée vers le haut
3. retourner toute la pile - la crêpe est rangée
4. recommencer en ignorant les crêpes rangées
Sa performance est alors en O(3n)
Rappel :
Retrouvez cette activité en vidéo :