Le crêpier psychorigide
Les
documents disponibles sur cette page ainsi que le contenu de la page
sont mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International 
Notions abordées :
Les concepts informatiques mis en avant par cette
activité sont les algorithmes, l'instruction conditionnelle
(pour la variante avec les couleurs des faces), la boucle et même
la complexité pour les extensions.
Si les participants le font
en groupe (ce qui est conseillé), on apprend
également à argumenter, puis à verbaliser son raisonnement.
Public :
Il n'y a pas de compétence particulière
nécessaire, mais une telle activité est d'autant
plus valorisante pour le participant qu'il a trouvé la
réponse (presque) seul. Pour ne pas se retrouver en
échec elle demande donc une certaine capacité
d'abstraction.
Du coup il peut être une bonne idée pour des plus jeunes de
tester d'abord le jeu de Nim pour qu'ils se familiarisent avec la
démarche de recherche d'algorithme, puis s'ils sont
relativement à l'aise de passer au crêpier.
Cette activité a été testée devant un public varié en fête de la science, fin de primaire (CM1), collège et lycée.
Matériel :
Au moins cinq objets empilables de même forme et de
taille croissante avec deux faces différentes (par
exemple une de couleur l'autre non).
Un modèle de
crêpes rectangulaires servant pous plusieurs activités est
téléchargeable sur la page de Martin Quinson (voir
liens).
Vous pouvez également réaliser votre version "faite maison" artisanale
(cf. photo).
Principe :
L'activité consiste à trier une pile de crêpes
par taille, et ce en respectant quelques contraintes pour leur
manipulation. Il est interdit de sortir une crêpe du
milieu de la pile, ou de poser une partie du tas sur la
table. La seule action autorisée est de prendre
les x crêpes du haut de la pile
(où x est le nombre qu'on veut), de retourner
cette petite pile de crêpes et de la reposer sur les
autres crêpes restées sur la table. On peut donc ne
retourner que la crêpe du haut, ou tout le tas, mais pas
juste la crêpe du milieu du tas.
Encore une fois on laisse la part belle à la
manipulation, et la mise en oeuvre se fait en plusieurs
étapes :
- les participants manipulent, sans aucun besoin d'expliquer leurs actions,
- il faut ensuite expliquer à une autre personne (qui essaie d'être aussi bête qu'un robot) comment trier, sans toucher soi-même les crêpes,
- il faut enfin formaliser ces idées pour pouvoir, sans voir les crêpes, dire au robot comment les trier.
On aborde ainsi les notions de test (instruction conditionnelle), de répétition (boucle) voire même de récursivité et de complexité suivant les variantes testées.
Extensions :
- Commencer par trier par taille, puis imposer que chaque crêpe montre une face précise vers le haut (la face colorée par exemple).
- Faire exécuter le même algorithme en même temps par plusieurs robots pour vérifier qu'il fonctionne dans plusieurs cas bien choisis (déjà trié, tout à l'envers,...).
- Parler de complexité (=du nombre de retournements nécessaires pour trier la pile, en fonction du nombre de crêpes).
- L'une des étapes de l'algorithme est de trouver la plus grande crêpe (parmi toutes ou parmi un sous-ensemble). Si le robot ne savait pas le faire tout seul, quel algorithme pourrait-on inventer pour lui expliquer comment la trouver ? De quelles instructions aurait-on besoin pour cet algorithme ?
Liens :
- Encore une fois la page de Martin Quinson, avec la description des activités, un petit livret facile à mettre en forme avec une description rapide des activités, et un support à imprimer en couleurs pour avoir le matériel pour jouer à Nim au crêpier et au baseball multicolore.
- il y a aussi une fiche sur Pixees,
- un article plus poussé sur le site d'Interstices,
- et une vidéo Inria où je présente l'activité.
- Si on veut voir des algorithmes plus efficaces, il existe un article d'un certain William H Gates (plus connu sous le prénom de Bill) et de Christos Papadimitriou de 1979 intitulé "Bounds for sorting by prefix reversal" soit en français "Bornes pour le tri par retournement de préfixe". Il montre en fonction du nombre n de crêpes le nombre de retournements nécessaires en particulier qu'il n'existe pas d'algorithme qui fasse mieux, pour toutes les piles de crêpes de taille n, que (17n)/16 mais qu'on peut le faire en (5n+5)/3, soit mieux que les 2n obtenus avec la méthode ci-dessus. Au moment où j'écris ceci l'article est disponible ici.
Photos :
Quelques exemples de manipulations.
