InfoSansOrdi

Cette page reprend un calendrier de l'Avent au sujet de l'informatique débranchée que j'ai fait sur Mastodon en décembre 2022. J'ai édité les textes en les reprenant sur cette page pour faire moins télégraphique et ajouter des images.

Jour 1

C'est parti pour un calendrier de l'Avent de #InfoSansOrdi, l'informatique débranchée. Il s'agit d'activités pour explorer des concepts d'informatique avec les mains, sans ordinateur. On expérimente, réfléchi, découvre de vrais concepts d'informatique, avec des bouts de carton, des cartes à jouer ou de la ficelle.

Ceux qui ont démocratisé l'approche il a 15 ans ont une très bonne introduction au concept.

Jour 2

Première activité #InfoSansOrdi facile: le jeu de Nim. On a une pile d'allumettes, deux joueurs qui prennent à tour de rôle 1, 2 ou 3 allumettes. Celui qui prend la dernière a gagné.

L'intérêt est qu'il y a une stratégie gagnante, ce qui permet d'expliquer la notion d'algorithme en CE2. @MarieKremer3 a une super page sur cette activité. Les élèves de l'ENS Rennes on préparé des fiches de préparation et autres ressources pour un usage en classe.

Bien adapté aux fêtes de la science car le jeu est connu. On embraye facilement sur l'explication "c'est de l'info parce que" sur l'intérêt des algorithmes: l'ordi est un tas de fils idiot, et on a besoin d'une "stratégie gagnante" pour lui faire faire ce qu'on veut.

Jour 3

Après Nim, le crépier psychorigide marche bien (démo vidéo). Cette activité est typique de l'informatique débranchée, où l'on réfléchi avec les mains.

Il y a deux principaux intérêts pédagogiques. Tout d'abord, tout le monde réinvente l'algorithme, ce qui change de la dissection d'algorithmes morts avec Euclide.

Ensuite, on peut réaliser une belle montée en abstraction avec les élèves. Après la phase où chacun joue et manipule, on joue sans les mains : l'un tient les crêpes et l'autre donne des consignes, ce qui le force à formaliser. Phase 3: sans les yeux, i.e. on donne les consignes sans voir la pile (en posant des question). Un arbitre sert de facilitateur si c'est un peu difficile. Phase 4 : une programmeuse commande plusieurs robots sans les voir et doit donc encore monter en abstraction.

Car oui, #InfoSansOrdi est inclusif : geeker à la maison avec papa n'aide pas, c'est la porte sur l'informatique ouverte à tout le monde.

Autres avantages: le matériel est facile à fabriquer et bon marché, et il n'y a pas d'interférence de l'ordinateur dans le discours. On peut se concentrer sur les concepts, sans erreur de syntaxe ni bling bling clignotant.

Jour 4

Une autre activité d'algorithmes: Le baseball multicolore. 5 bases de couleurs différentes, 9 pions (2 par couleur + un pion seul). Répartition aléatoire des pions, qu'ill faut ranger avec des contraintes sur les déplacements.

Trouver un algorithme n'est plus aussi simple alors on en propose un avec la réflexion suivante : ce qui est difficile pour l'ordinateur, c'est qu'il y a quatre possibilités à chaque étape. Il ne sait pas choisir seul. Fixons un sens pour tourner, il reste deux possibilités. Entre les deux, on prend la couleur qui a le plus de route à faire. Et hop, on a un algorithme qu'on peut tester en direct.

Sauf que ... cet algorithme est faux : dans certaines situations initiales, l'algorithme tourne à l'infini (inversez deux pions d'une situation triée pour voir). C'est l'occasion de parler de preuve de programmes, où il faut la correction (OK ici) ET terminaison (pas garantie ici).

Truc d'animatrice pour être (probablement) dans un cas où l'algo marche malgré tout et assurer un effet de surprise pour la suite : pas de pions déjà dans sa maison, et jamais deux pions identiques ensemble. Je sais que ce truc fonctionne car j'ai calculé tous les cas, comme un bourrin d'informaticien :)

Le schéma suivant (version zoomable) représente le graphe de toutes les situations du jeu pour 4 couleurs. Chaque petit rond est une situation donnée, et elle est reliée par une flèche allant vers la situation qu'on obtient en appliquant cet algorithme. En haut de la figure, on a un arbre, avec la situation triée tout en haut de l'arbre. L'algorithme marche dans tous ces cas. En dessous, certaines situations sont déconnectées de l'arbre et forment un cycle infini.

Certains petits ronds sont cerclés de noir car ils respectent le critère de prestidigitatrice "personne à la maison; pas deux de la même couleur dans la même base" et d'autres sont cerclés de rouge car ils ne respectent pas ce critère. On constate que tous les ronds cerclés de noirs trouvent dans l'arbre qui converge vers la solution et aucun dans la partie qui boucle à l'infini. C'est la "preuve" que la prestidigitation proposée fonctionne bien dans ce cas. Si vous avez 7 couleurs ou plus, la règle n'est plus infaillible, mais on garde de grande chance que cela fonctionne encore.

Nim, crépier et baseball forment une belle séquence sur les algorithmes, souvent joués dans cet ordre. On l'a testé avec des participants de 9 à 99 ans (élèves, profs de maths, ou à la fête de la science avec le "moyen public" qui y vient), sur une heure ou plusieurs séances. Le matériel plein de couleurs (mais accessible aux daltoniens) pour les 3 activités est facile à coller sur du carton plume avant découpe. Il y a un livret du participant, celui de l'animatrice, des vidéos démo, etc. Tout est sur cette page. C'est sous licence CC-BY-SA pour que vous vous en serviez. Un grand merci à J.C Bach pour sa complicité pendant qu'on inventait ces activités.

Benjamin Wack a fait un simulateur en ligne, pratique pour faire des démos sur le videoprojecteur. C'est tellement utile que le groupe Maths à modeler de Lyon a fait un autre simulateur de cette activité.

Jour 5

Après les algorithmes, l'activité des blasons est super pour aborder la notion de langage. On demande à un participant de dicter une figure aux autres, qui la dessinent sans la voir. Normalement, ça se passe mal: les dessins ne sont pas très ressemblants et les participants se disputent un peu, avant de comprendre qu'il faut un vocabulaire commun. Ensuite, des figures de plus en plus compliquées permettent d'expliquer en conclusion qu'un bon langage informatique est expressif et non-ambigu (activité co-inventée par Solène Mirliaz, la co-major de l'agrégation d'informatique 2022 lors de son L3 à l'ENS Rennes).

Jour 6

Autre concept d'informatique à explorer sans ordinateur : l'information.

Les marmottes au sommeil léger est une activité bien documentée et souvent testée, par @MarieKremer3. Derrière une histoire de placement des marmottes dans l'arbre du terrier pour mettre celles qui se relèvent beaucoup la nuit + proches de la sortie, on explore la compression de données. En fait, on fait redécouvrir aux participants un algo proche de celui des .zip

Les élèves de Rennes ont fait des fiches de préparation.

Jour 7

Une autre activité sur le concept d'information, avec un enrobage magique.

Avec des cartes blanches d'un coté et noires de l'autre, on fait un motif 5x5, que l'animatrice étend en 6x6 "pour compliquer un peu". Ensuite, les participants retourne une carte en secret, que l'animatrice "devine". C'est qu'elle a fait un code correcteur avec les cartes ajoutées, comme on protège les données envoyées sur le réseau contre les erreurs de transmission (cf. la super page de ClassCode).

Quelques liens : la page de Marie l'informagicienne, celle de l'IREM de Clermont avec des fiches élèves et profs, et enfin, la page des néo-zélandais de CSunplug eux-mêmes. Il existe aussi un simulateur pour faire les démos en ligne.

Jour 8

Une dernière activité sur la notion d'information : l'encodage d'image bitmap (ce qui complète les images vectorielles des blasons).

C'est encore des figures téléphonées: on décrit une image que l'autre dessine, mais cette fois on décrit la grille des pixels. Encore une activité très riche avec plusieurs algorithmes (bmp ou png), la possibilité de jouer à 2 ou de faire une grande fresque en groupe, etc.

Les ressources disponibles sont préparées par les mêmes qu'hier : les gens de l'IREM Clermont, qui ont beaucoup enrichi cette activité, la prolixe MarieDK, le canal historique de CSunplug et le projet 1, 2, 3... Codez! de la fondation La main à la pâte.

Jour 9

J'en vois certains dans le fond de la salle marmonner que l'#InfoSansOrdi c'est tout juste bon à l'amusement pendant la fête de la science, avec les zolis aspects ludiques de l'informatique.

Donc aujourd'hui 9 décembre, on parle du M99, l'ordinateur en papier qui montre le fonctionnement du processeur, la mémoire, les registres, la pile et tout ça. Ça n'est pas très marrant, mais c'est affreusement efficace pour expliquer l'archi au début d'un cours de C. Voyez ma feuille de TD (il faudrait que j'en fasse une activité moins repoussante, un jour. La blague a ses limites).

Merci à Philippe Marquet pour son aide ! Personnellement, je crois que je n'avais pas vraiment compris comment fonctionne le processeur avant qu'on invente cette activité ensemble.

Jour 10

On peut parler Matériel (le quatrième concept fondamental d'informatique avec les algorithmes, les langages et l'information), sans être aussi aride que le M99 d'hier.

@MarieKremer3 a une activité sympa sur le routage du réseau, mais sa version demande beaucoup de matériel. Alors quand on joue cette activité en classe, on l'adapte (cf. aussi la fiche de prép): Des fils de scoubidous pour l'interconnexion, des petits papiers pour les messages en transit et l'ardoise pour savoir qui on est. On joue dans chaque îlot, puis on interconnecte les îlots entre eux. Cette activité est saisissante avec un groupe classe fort : quand les élèves ont l'habitude de travailler ensemble, cette activité permet à tout le monde se mettre en action pour faire bourdonner la classe, et tout le groupe travaille à réinventer le protocole RIP. J'adore.

Il arrive que les participants trichent un peu pendant les séances, comme sur la photo de droite. Ces deux élèves ne sont pas sensées s'échanger des messages car il n'y a pas de fil de scoubidou entre elles. Mais ce n'est pas grave, au contraire. La force de l'informatique débranchée, c'est justement de permettre aux participants d'expérimenter avec les concepts de l'informatique sans être empêchés par le coté psychorigide de l'ordinateur, les problèmes de connectique arbitraires ou les erreurs de syntaxe idiotes.

Jour 11

Au delà des quatre concepts Algorithmes, Langages, Information et Matériel, on veut naturellement parler programmation quand on parle d'informatique. @MarieKremer3, encore elle, a une belle activité faisable dès la grande section.

Un participant se place dans un monde quadrillé, dessiné sur un grand drap. Un autre lit une fiche-programme pour le diriger. Puis on utilise une fiche qui ne marche pas (le trajet proposé rate le pont et se prend la rivière), ce qui est l'occasion de pour parler de bug informatique avec les participants. Ensuite, on invente ses propres fiches pour résoudre les défis proposés (photo volée à Marie).

Les néo-zélandais ont aussi beaucoup de ressources sur ce genre d'activité.

Jour 12

Qui dit programmation dit langage de programmation. CargoBot est une bonne activité pour ça: on programme un bras élévateur avec un langage fait de flèches pour déplacer des charges et faire des motifs. Malika et Pascal de l'IREM de Clermont (encore eux) ont rédigé beaucoup de matériel sur cette activité, tandis que Benjamin a fait un simulateur avec pleins de niveaux à jouer en ligne. Les élèves de l'ENS Rennes ont fait quelques fiches de prep, sans doute inspirées de celles de l'IREM de Clermont.

Pour rebrancher, poursuivre sur ordinateur après une activité débranchée, le crêpier psychorigide et le baseball multicolore sont dans la PLM, mais l'outil a mal vieilli. Il faudrait que je m'en occupe, un jour :(

Jour 13

Après les concepts fondamentaux et la programmation, on a aussi envie de parler un peu théorie.

On commence avec les graphes. Parmi toutes les activités sur ce thème, le problème de l'arbre recouvrant minimal est toujours efficace. La ville embourbée faisait partie du pack historique de CSunplug. Cette activité a été étendue par Dorian Mazauric de Galejade, qui font énormément sur l'algorithmique des graphes. Les élèves de l'ENS Rennes ont aussi produit quelques ressources autour de cette activité.

Un jour, j'aimerais bien avoir plusieurs instances de ville embourbée afin de pouvoir rejouer la même activité une fois que les participants ont compris le principe. Cela pourrait permettre d'explorer plusieurs algorithmes faux avec les contre-exemples bien pensés. Il y a peut-être matière pour une activité de recherche type "Maths en Jeans" sur plusieurs jours. J'avais fait ça avec une stagiaire de 3ieme venue visiter le labo, afin qu'elle ait elle aussi son problème de recherche à explorer comme tout le monde, et ça s'était bien passé. J'aurais dû noter les instances de graphes que je lui avait donné pour la guider dans sa recherche d'algorithme.

Jour 14

Aujourd'hui, on explore les langages formels avec des automates à états finis.

Dans l'île au trésor de CSunplug, on va d'île en île en fonction de transitions A ou B, et on cherche à faire une carte du monde, mais les notions formelles sont finalement assez peu détaillées. Comme souvent, les copains de l'IREM de Clermont ont fait de belles choses autour du parcours d'automates et des langages. Ces activités sont souvent reprises par les élèves de l'ENS Rennes (ici et là), qui doivent animer des activités débranchées en CM1/CM2/6ieme/5ieme pendant leur année de L3.

Jour 15

Pour explorer les automates, j'adore le flexagone. C'est un objet mathémagique: plat en 2D mais à 3, 4, 6 ou 7 faces. On fait apparaître les faces cachées en le pliant, un peu comme une cocotte en papier. C'est beau car il y a plusieurs manipulations possibles à chaque étape, chacune faisant sortir une face différente. Il est difficile de savoir comment atteindre une couleur donnée sans dessiner le plan. Quand je l'ai donné à mon gamin, il s'est vite retrouver à dessiner un automate sans le savoir.

Je crois avoir découvert cet objet avec les super vidéos de Vi Hart, qui fait de la très bonne vulgarisation mathématique. Les collègues de TeachingComputing@London ont une activité sur le flexagone et ses variantes. Pour des explications en français, on peut aller du coté de chez ElJjdx. Sinon, les collègues de la MMI de Lyon (maison des mathématiques et de l'informatique) ont fait un joli matériel à découper.

Comme il est quasi impossible que le recto et le verso lors d'une impression corresponde exactement après découpe, le matériel proposé par ces différents auteurs demandent de coller deux faces, ce qui fait une sur-épaisseur pas très pratique. J'ai sur un coin de mon disque un prototype de mire, avec une cible au recto et une grille au verso. On regarde la position de la cible sur la grille par transparence pour découvrir le décalage à donner au document pour compenser celui infligé à l'impression. Cela permet de faire des documents adaptés à une imprimante donnée pour faire des recto-versos parfaits. Il faudrait que je finisse ce truc, un jour.

Jour 16

Aujourd'hui c'est complexité. Comme je n'aurais pas le temps de tout dire avant la fin du mois, voici deux activités d'un coup.

La première nous vient de l'IREM de Grenoble: Alice déménage, et elle cherche comment ranger ses cartons dans sa camionnette. On a des pièces de puzzle rectangulaires de tailles différentes, et on cherche à les ranger de façon compacte sur un quadrillage blanc. C'est l'occasion de découvrir le problème classique du bin-packing, et ses implications en ordonnancement ou ailleurs.

Pour les carrés de MacMahon de la seconde activité, on n'a que le matériel à découper, rien n'est rédigé à part la présente page (c'est donc une activité originale). On a 24 pièces carrées formées de triangles colorés (les lettres au centre sont là pour retrouver les 24 pièces quand on a mélangé paquets, et les ronds noirs et blancs n'interviennent pas au début). Le but du puzzle est de faire un grand rectangle 6x4 en faisant correspondre des faces de même couleur. Quand les participants y arrivent, on ajoute la contrainte que chaque bord doit être d'une couleur unie. Ou encore que le puzzle doit être torique : le bord du bas doit être compatible avec le bord du haut, celui de droite avec celui de gauche. On peut aussi ajouter la contrainte qu'une face avec un rond doit correspondre à une face sans rond. On garde la contrainte que la couleur doit correspondre, et on ajoute celle sur les petits ronds.

Quand résoudre à la main devient lassant, on peut demander aux participants d'inventer un algorithme pour résoudre le puzzle automatiquement, ce qui permet de parler de la méthode par backtracking, où l'on teste toutes les possibilités jusqu'à être coincé. Il y a un économiseur d'écran nommé Polyonominoes qui résout un puzzle un peu différent de cette façon. C'est très très lent parce qu'il faut tester un nombre exponentiel de possibilités. Par exemple, l'instance du puzzle signé du matériel à découper, il n'y a que 60 dispositions qui respectent les contraintes du puzzle signé torique sur plus de 10³⁶ possibilités. Et ce calcul tient compte des symétries, qui font plus de solution (puisque c'est torique) mais beaucoup plus de possibilités...

Cela devient vraiment intéressant si on se demande quelle est la variante la plus dure. La version de base (nommée "puzzle carré" en maths), ou celle avec la contrainte supplémentaire des ronds (qu'on appelle "puzzle signé" en maths) ? Et comment on le prouve ? Ah, là on va parler de complexité algorithmique!

Il faut savoir que les informaticiens sont des gens bizarres : Quand un humain normal trouve un problème qu'il ne sait pas résoudre, il arrête et fait autre chose. Quand un informaticien trouve un problème qu'il ne sait pas résoudre en temps raisonnable, il se demande si c'est plus dur ou plus facile qu'un autre problème qu'il ne sait pas résoudre. Par exemple : est-ce plus facile de voler dans le ciel comme superman, ou de résoudre le problème de la faim dans le monde? Bah je sais pas, je sais faire ni l'un ni l'autre, hein. Bon, c'est vrai mais on va réfléchir par réduction : imagine que superman existe vraiment, qu'il débarque sur terre en sachant voler à la vitesse de la lumière sans se fatiguer (je ne sais pas comment il fait). On pourrait lui demander de prendre la nourriture des zones de surproduction où elle est gâchée pour l'emmener là où des gens meurent de faim. Et hop! Plus de problème. OK. Maintenant l'inverse. Imaginons que Mahatma Gandhi revienne sur terre et résolve le problème de la faim dans le monde (je ne sais pas comment). Est-ce que ça va permettre à l'un.e d'entre nous d'aller faire le guignol dans l'espace devant les caméras à la vitesse de la lumière ? Non, je ne vois pas trop comment, et je peux donc conclure que le problème de voler comme superman est au moins aussi compliqué (voire plus* compliqué) que le problème de la faim dans le monde. Je l'ai démontré sans savoir résoudre aucun des deux problèmes.

Quel est le rapport avec mes puzzles carrés et signés, vous demandez ? Et bien cet article montre que ces deux problèmes sont exactement aussi complexes l'un que l'autre en utilisant des réductions de complexité comme dans l'histoire de Superman vs. Gandhi. On montre que si on sait résoudre l'un, on sait résoudre l'autre. Par exemple, si la fée Morgan sait te dire comment résoudre l'instance du puzzle signé de ton choix, tu peux l'utiliser pour résoudre le puzzle non signé de ton choix, en inventant les pièces qui t'arrangent.

Tu veux résoudre un problème avec la pièce à gauche? Donne les pièces de droite à Morgan pour qu'elle résolve ce puzzle signé (w, x, y et z sont des nouvelles couleurs que tu inventes pour utiliser ses talents de fée). Fais la manip pour chaque pièce de gauche que tu as dans ton problème, et quand Morgan aura résolu le problème avec la foultitude de pièces de droite, il ne sera pas dur d'en déduire une solution pour tes pièces de gauche. C'est vrai que ça fait beaucoup de couleurs, mais ça reste plus rapide que le backtracking si Morgan sait vraiment résoudre son problème rapidement comme elle prétend.

Encore plus fort: l'article montre qu'on peut réduire le problème des polynominoes (celui de l'économiseur d'écran) vers le puzzle carré comme ci-dessus. Les couleurs à l'intérieur du polynomino qu'on invente (à droite) sont toutes uniques, et le symbole % représente une couleur unie pour les bordures. Si Morgan sait effectivement résoudre le puzzle signé, alors je sais résoudre le problème des polynominoes: j'encode chaque polynomino de mon défi en un puzzle carré avec beaucoup de couleur, puis j'encode ce nouveau défi comme un puzzle signé avec encore plus de couleurs. Mais comme Morgan sait résoudre ça facilement, hop, ça me donne une solution à mon problème de départ.

L'article termine la boucle avec les puzzles habituels (ceux avec des formes arrondies qui s'emboîtent). Ces puzzles peuvent encoder n'importe quel défi de puzzle signé, et on sait encoder un puzzle normal sous forme d'un défi de polynominoes. La boucle est bouclée. Si Morgan, Merlin ou Superman savent résoudre efficacement n'importe lequel de ces problèmes, alors on sait résoudre tous les autres. Ils forment une classe d'équivalence nommée NP-complet. Le bin-packing de la première activité est également dans cette classe d'équivalence, avec beaucoup d'autres problèmes célèbres comme le voyageur de commerce ou 3-SAT. Si quelqu'un trouve comment résoudre n'importe lequel de ces problèmes, il peut trouver votre code de carte bancaire et déchiffrer la plupart des messages chiffrés actuels et passés. Il aurait résolu le problème "P = NP". Mais à priori c'est mal parti: le consensus entre informaticiens est que l'on n'arrivera jamais à résoudre ces problèmes efficacement, sauf si on fini par fabriquer un ordinateur quantique fonctionnel. Ce qui, à mon avis, n'arrivera jamais (mais là on n'est pas tous d'accord entre collègues sur ce point).

Si vous avez aimé les carrés de Mac Mahon, vous pouvez tenter les tuiles de Wang qui généralisent le concept. Chercher des pavages de tuiles de Wang est un classique dans un cours niveau M2 de complexité (cf chapitre 3). Mais je n'y comprend rien, perso.

Jour 17

Aujourd'hui, on termine le tour de la théorie enseignée à l'université avec deux activités d'un coup. Après, ça suffit, on aura pas le temps de parler de tout. Demain, on va plus loin que le programme de l'agregrégation.

Pour commencer, l'activité des Caméléons explore la logique propositionnelle. Au travers d'une histoire de caméléons colorés qui descendent un arbre de nid en nid, on parle portes logiques, valuation de formules, et tables de vérité. Cette activité a été inventée par Pablo Espana-Gutierrez (le co-major de l'agrégation d'informatique 2022) pendant sa scolarité chez nous.

Si vous préférez faire une partie de la marelle de Turing de la MMI-Lyon, elle est disponible en ligne.

Jour 18

Aujourd'hui, on passe doucement hors-programme avec les réseaux de tri : Chaque participant a un numéro, et l'objectif est de les trier. Pour cela, les numéros se comparent deux à deux dans l'ordre donné par les dessins au sol. Il faut 5 étapes de comparaisons parallèles pour trier 6 numéros, et surtout beaucoup de coordination entre les participants.

L'algorithmique massivement parallèle (voire systolique) n'est plus à la mode sur les ordinateurs modernes (du moins pas dans cette forme là), mais l'activité reste incroyablement efficace pour impliquer tout un grand groupe dans une activité algorithmique. @MarieKremer3 met le feu aux fêtes de la science avec cette activité. Sa page donne des ressources, et elle a aussi une autre page sur un autre tri systolique. CSunplug propose plusieurs activités sur les réseaux de tri, tout comme Galejade. On trouve même des résultats issue de la recherche récente sur les posters de Galejade: Il existe un réseau de tri à 60 trieurs pour trier 16 éléments, et on sait depuis 2017 qu'il est optimal.

Jour 19

Aujourd'hui on explore l'informatique parallèle dans une autre activité impliquant tout le groupe. C'est un puzzle humain, où chaque personne est une pièce du puzzle. Le groupe propose puis expérimente des algorithmes pour se coordonner et refaire le puzzle (chaos bruyant, algorithme centralisé, token/bâton de parole, multi-token, etc).

Cette activité a gagné le premier prix de la médiation de la Société Informatique de France en 2018. Ce concours a lieu chaque année depuis. Les élèves de Rennes ont fait des fiches de prep et des scripts pour générer des plateaux de jeu.

Jour 20

Aujourd'hui, on parle calcul parallèle avec l'activité de la Grande Muraille d'Égypte, par Emmanuelle Saillard d'Inria Bordeaux.

Deux maçons posent des briques de couleurs différentes, pour refaire un motif donné. On ne peut placer une brique que si sa voisine de gauche et les deux du dessous sont déjà posées. L'objectif est d'alterner les couleurs : on prend une pénalité chaque fois qu'un maçon ne peut poser de brique de sa couleur.

Les contraintes et le motif à refaire sont similaires aux dépendances de données entre les calculs quand on fait de l'ordonnancement multi-coeurs, où l'objectif est de placer correctement les calculs à faire pour s'assurer que tous les coeurs ont du travail à chaque étape.

Jour 21

Aujourd'hui on parle IA et apprentissage par renforcement, avec une extension du jeu de Nim vu au jour 2. Cette fois-ci, on jour contre une machine qui apprend de ses erreurs. En plus du matériel classique de Nim, on a besoin de gobelets contenant des jetons colorés. Par exemple quand c'est à la machine de jouer et qu'il reste 12 allumettes sur la table, on tire un jeton au hasard dans le gobelet n°12. La couleur du jeton donne la décision de la machine: Si le jeton est bleu, elle prend 3 allumettes sur la table. Si le jeton est jaune, elle prend deux allumettes. Si le jeton est rouge, elle prend une seule allumette.

À chaque fois qu'on tire un jeton, on le pose à coté du gobelet le temps de la partie. En cas de victoire, la machine double les jetons tirés les gobelets correspondants (par exemple si on a gagné en tirant un jeton bleu du gobelet 7, on remet deux jetons bleus dans ce gobelet). En cas de défaite, les jetons joués sont retirés du jeu. La machine va donc apprendre la stratégie gagnante par renforcement.

En pratique, on utilise rarement cette variante du jeu de Nim, car la machine a besoin d'une centaine de parties jouées en moyenne pour converger vers la stratégie gagnante. Les collègues de la MMI utilisent la variante à 8 allumettes et deux couleurs seulement (on ne peut donc prendre que une ou deux allumettes à chaque tour) comme sur leur photo ci-dessus, car elle converge bien plus vite. Je trouve cependant cette variante un peu trop facile, et il arrive que les participants appliquent instinctivement la stratégie sans arriver à l'exprimer, et sans voir l'intérêt de rédiger un algorithme pour jouer. J'aimerais trouver une variante du jeu pour laquelle l'apprentissage par renforcement converge rapidement, tout en restant un peu dure pour les humains. Il faudrait peut-être essayer de faire varier le nombre d'allumettes qu'on a le droit de prendre. Par exemple: "si le nombre total d'allumettes est pair, j'ai le droit de prendre 1, 2 ou 3 allumettes, mais s'il est impair je ne peux prendre que 1 ou 2 allumettes". Un jour peut-être.

Quelques sites contenant des ressources pour cette activité: Page de la MMI; page de Marie Duflot-Kremer; pages des élèves de Rennes.

Jour 22

Aujourd'hui, on parle model checking et vérification formelle. Les activités proposées sont un peu plus difficiles que d'autres, peut-être réservées à des participants à partir de la fin du collège. Il faut dire que les notions explorées ne sont vues à l'université que dans certains cours optionnels et avancés de M2.

Dans le Château Pas Très Fort de Marie Duflot-Kremer, on explore un château représenté par un graphe, et on teste des formules de logique temporelle sur ce chateau comme "Je peux me balader dans uniquement des pièces avec des torches" ou "Je vais forcément me balader dans uniquement des pièces avec des torches", ou autre. C'est l'occasion de découvrir les quantificateurs logiques ("Pour tous les chemins", "Il existe un chemin", et la négation) ainsi que ceux de la logique temporelle ("Toujours", "un jour", "jusqu'à", "à la prochaine étape"). Les propositions atomiques reprennent le mobilier du château: "coffre", "lampe", "fenêtre", etc. L'activité permet de s'approprier les notions sans s'attacher à la forme du glyphe qu'on utilise pour écrire ces quantificateurs.

Trois élèves de Rennes ont commencé une activité similaire où il faut trouver l'île sur laquelle le pirate a caché son trésor: c'est celle qui vérifie la formule temporelle donnée. On donne aux participants un journal de bord où le pirate décrit le chemin qu'il a fait sur l'île avant de cacher son trésor, ainsi que plusieurs cartes d'îles. Par exemple, les participants peuvent savoir qu'il ne s'agit pas de l'île du Singe car il raconte être passé par le volcan à pied sec après avoir débarqué près de la caverne, alors qu'on doit traverser une rivière pour atteindre le volcan sur cette île. Cette activité me semble prometteuse et riche : on peut faire une étape de modélisation préalable où l'on donne une description textuelle de chaque île, ou sauter cette étape pour se concentrer sur la vérification en donnant directement les cartes des différentes îles. Il reste un peu de travail avant de jouer l'activité en vrai, puisque ces cartes ne sont encore pas dessinées et imprimables. Un jour peut-être :)

Jour 23

Aujourd'hui, on parle IA, classification et apprentissage supervisé.

L'équipe Moex d'Inria a un jeu complet et bien fait sur la classification de données, et les défis qui se posent quand on veut classifier des objets mais qu'on ne sait pas quel critère prendre.

La MMI propose plusieurs activités complémentaires sur comment l'IA "apprend" une classification par apprentissage supervisé. Dans la première activité, il faut deviner (inférer) une règle de décision d'après différentes images, et le résultat que la règle cherchée donne sur chaque image. On teste ensuite la règle que l'on propose sur de nouvelles images ne faisant pas partie de l'ensemble d'entraînement. C'est l'occasion de parler de sur-apprentissage. Une deuxième activité montre comment ce genre de règles sont utilisées par un petit réseau de neurones qui fait la différence entre les chiffres de 0 à 9 écrits à la main. L'exemple est intéressant car on peut tourner le réseau à la main, ou presque.

Des élèves de rennes ont commencé une activité (sans la terminer) où l'on classifie des champignons selon plusieurs critères. Il faudrait finir ça, un jour.

Jour 24

Je vous propose de finir ce calendrier de l'Avent en beauté avec un Escape Game complet inventé par des étudiantes de MarieDK. Il couvre beaucoup de sujets, dont certains pas présentés ici comme la cryptographie et les bases de données. Oups. C'est qu'il existe bien plus d'activités que je n'ai eu le temps de présenter dans ce calendrier de l'Avent. Voici quelques liens supplémentaires.

  • InfoSansOrdi est le nom d'un collectif informel ayant reçu le soutien moral de plusieurs institutions comme la SIF ou la cellule médiation d'Inria au travers du site de Pixees (qui compte une section dédiée sur son site). Toute personne intéressée est bienvenue pour discuter et participer. Nous organisons deux journées par an où nous nous retrouvons (souvent à la MMI à Lyon) pour nous présenter les activités inventées entre temps, et pour discuter d'autres projets en lien. Nous avons ainsi réalisé un hors-série du magazine Tangente pour présenter l'InfoSansOrdi aux enseignants.
  • L'informatique débranchée a été popularisée par les néo-zélandais de CS Unplugged dans un article de 2009 à la conférence ACM de l'enseignement de l'informatique. Le livre qu'ils avaient sorti à cette occasion a été traduit en français. Leur site web contient d'autres activités qu'ils ont proposé depuis. Tout n'est pas traduit en français, mais vous pouvez aider en allant sur le site Crowdin. Notez qu'un livre français proposait dès 1987 d'enseigner l'informatique sans ordinateur. Il faut croire que le monde d'alors n'était pas prêt pour cela.
  • La page de MarieDK propose énormément d'activités prêtes à l'emploi. J'en ai présenté quelques unes ici, mais il vous en reste encore plusieurs à découvrir en direct sur le site.
  • L'IREM (institut de recherche en enseignement des mathématiques) de Clermont-Ferrand propose plusieurs activités. On retrouve pour chacune le matériel pour l'élève, la fiche enseignante, et le livret de l'animateur pour aller plus loin. Très bien ficelé. D'autres IREM proposent des activités, comme à Grenoble ou Lyon, mais j'ai présenté plus haut les activités que je connais, et je ne retrouve pas la belle page reprenant tout. Je ne suis pas très doué pour naviguer sur les sites institutionnels faits en WordPress ou équivalent.
  • Le site de Galejade présente beaucoup d'activités sur les graphes, mais pas que.
  • La fondation de La main à la pâte a fait un livre sur l'enseignement de l'informatique en classe en cycles 1, 2, 3 et 4. Ils proposent des séquences cohérentes, avec des séances débranchées, des séances branchées en scratch et des séances robotique. C'est un beau projet mené de main de maître par des pro de la médiation, ça se sent.
  • Pablo Espana-Gutierrez propose plusieurs activités sur sa page, en plus de celle des caméléons logiques que j'ai présenté plus haut.
  • OpenClassRoom héberge les ressources du projet Class'Code. Cette page propose par exemple des activités et des explications détaillées sur la notion d'information.
  • TeachingComputing in London propose des ressources variées (en anglais) pour enseigner l'informatique de l'école primaire au lycée. Ils ont même fait un petit magazine à publication régulière.
  • Cet article scientifique présente la démarche, ses avantages et quelques activités.
  • L'IREM de Lyon propose 199 défis mathématiques à manipuler, dont beaucoup seraient probablement réutilisable en InfoSansOrdi. Mais il n'y a aucune activité d'informatique associée, et c'est donc plus une source d'inspiration pour informaticien.nes souhaitant inventer une activité que pour enseignant cherchant quelque chose prêt à l'emploi.
  • Et pour finir, voici quelques activités en cours, commencées par les élèves de l'ENS Rennes pendant leur module de M2 où ils doivent inventer une telle activité, mais pas forcément terminées et en tout cas jamais testées en conditions réelles. Elles ne sont pas terminées, mais peut-être y trouverez-vous de l'inspiration ?
  • Ces activités ont été faits par des collègues sur leur domaine de recherche, et elles vallent le détour!
    • QuiProCo, par Tristan Allard. On parle de privacy sur internet et de comment l'assurer par confidentialité différentielle.

Voilà, j'espère que cette page vous donnera envie de tester certaines activités, voire de les améliorer ou de créer vos propres activités. On a hâte de vous voir présenter vos créations à la prochaine journée de la MMI !