Informatique au collège, les activités débranchées.

Déconstruire l’informatique pour mieux la comprendre.

Des activités ludiques, pour introduire la notion d’algorithme, un kit complet (mallette pédagogique, vidéos de démonstration) offre quatre activités pour expliquer les notions de stratégie gagnante, de récursivité ou bien encore d’heuristique.

Il est très facile de rassembler les quelques objets (pions, etc…) pour chaque activité, voir de demander aux jeunes de fabriquer/monter les objets pour s’approprier les contenus de manière concrète.

Voir le manuel complet et le source de la documentation.

Une collaboration avec Makerspace nancéen avec le support de Cap’maths.

Le jeu de Nim comme algorithme

Jeu de Nim

On commence par découvrir les règles du jeu, puis la question de chercher à gagner se pose, et on découvre alors une solution répétitive qui fonctionne mécaniquement.

objectif : introduire la notion d’algorithme comme stratégie gagnante pour résoudre un problème
règle du jeu : deux joueurs ramassent tour à tour 1, 2 ou 3 allumettes sur une table. Celui qui prend la dernière à gagné. A travers ce jeu bien connu, nous introduisons la notion d’algorithme comme stratégie gagnante pour résoudre un problème

Pour aller plus loin :

Stratégie magiques au pays de NIM
Comprendre l’informatique en jouant au jeu de Nim : le tutoriel en vidéo de Marie Duflot
Le jeu de NIM (une autre vidéo)
Jeu de NIM (orientée IA): vidéo Pause ta science
Eléments de la boite d’activités débranchées de NyBi.cc, réalisé avec le support deCap’maths avec cette vidéo

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

Circuit le plus court (ou voyageur de commerce)

Objectif : Ce problème permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Résumé : Comment trouver le circuit le plus court ? Ce problème d’optimisation aux applications innombrables nous permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Déroulé de l’activité : Sur une planche à clous, on fait passer un fil une fois et une seule par chaque clou avant de revenir au point de départ. Comment trouver le circuit le plus court possible ? Ce problème d’optimisation aux applications innombrables nous permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Il faut bien distinguer ce problème dit du voyageur de commerce dont la complexité explose avec la taille du problème et celle du plus court chemin dont la complexité augmente de manière seulement polynomiale.

La vidéo Pause ta science
Jouer en ligne (une applet en Scrach grâce à fmasseglia)
Une démonstration logicielle (une applet en Scrach grâce à fmasseglia)
On y montre l’explosion combinatoire, pour faire prendre conscience des milliards d’années de calculs qui rendent impossible de connaître LE meilleur passage de la ficelle, on peut vraiment voir les chemins très clairement pour 4 ou 5 points, puis cela devient «intractable».
Documentation : https://github.com/downloads/jcb/CSIRL/tsp.pdf (voir aussi le manuel complet)

Pour fabriquer vous-même un kit, voici quelques fichiers qui pourront vous aider https://github.com/InfoSansOrdi/planches-a-clous

En savoir plus :

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.

Le baseball multicouleur comme algorithme

Cette activité introduit la notion de correction d’algorithme, et les moyens utilisés par les chercheurs en informatique pour la prouver.
Il existe diverses méthodes pour résoudre le problème, mais comment être sûr qu’une méthode donnée est correcte ?
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.