Le vendeur de crèpe : une initiation aux algorithmes

Objectif : On trouve la solution au problème, puis on l’exprime étape par étape, de manière rigoureuse, en calculant le nombre d’étapes nécessaires.

Ce problème de tri assez simple nous permet d’introduire la notion de formalisation d’algorithme. En effet, un algorithme n’est utile que si on peut l’expliquer à un ordinateur. Le but de l’exercice est donc de trouver la solution au problème, puis de l’exprimer étape par étape, de manière rigoureuse. Au passage, c’est aussi l’occasion d’introduire la notion de performance en calculant le nombre d’étapes nécessaires à résoudre un problème de taille N.

Le contenu sous toutes ces formes
Ce contenu se présente sous la forme de petit logiciel et d’activité débranchée décrite par un texte et une vidéo. Il permet

de manipuler des crêpes — et à travers elles des abstractions numériques — afin d’apprendre à concevoir une démarche systématique et efficace pour résoudre un problème. Ici, le problème consiste à mettre dans un ordre croissant une pile de crêpes de différentes tailles (en désordre) en retournant uniquement les crêpes avec une spatule. Le tout est de déterminer quelles opérations faire effectuer à une machine pour obtenir ce résultat en un nombre minimum de coups.

Voir la vidéo (cliquer sur l’image)

Ce grain logiciel peut-être combiné avec l’article « genèse d’un algorithme » du site Interstices qui explique comment, à partir de cette expérience, les élèves apprennent à formuler le problème afin de pouvoir écrire un programme qui résolve cette question de façon automatique quel que soit le nombre de crêpes dans la pile. Un algorithme qui est utilisé, au-delà de ce jeu, pour résoudre des problèmes de routage dans des réseaux de processeurs qui calculent en parallèle.

Références:

Documentation : https://github.com/downloads/jcb/CSIRL/crepier.pdf (voir aussi le manuel complet)
Pour fabriquer vous-même un kit, voici des plans de découpe pour la fabrication des crêpes : https://github.com/jcb/CSIRL/tree/master/supports/crepier

On peut utiliser des ressources complémentaires.

Élément de la boite d’activités débranchées de NyBi.cc, réalisé avec le support de Cap’maths.o

Le tutoriel en vidéo de Marie Duflot : Comprendre l’informatique en jouant au jeu du crépier