Ressource
Sélection, scolaire, cycle 4 . Activité débranchée . Ateliers . Lycée . Professeurs du secondaire . Article ou présentation . activité débranchéeInformatique 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.
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
![pile de crèpe logicielle](https://gitlab.inria.fr/mecsci/grains/crepes/snapshots/120px.png)
Voir la vidéo (cliquer sur l’image)
![](https://iww.inria.fr/mecsci/grains-videos3.0/icons/crepier-Inria_H264_1024x576_5Mbit.png)
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:
- http://inriamecsci.github.io/#!/grains/crepes
- http://www.inria.fr/mecsci?l=unplug
- http://interstices.info/algo-crepes
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.
Des joueurs de couleur se déplacent pour rejoindre la base de leur couleur en tournant autour du terrain.
Voir la vidéo:
![](https://iww.inria.fr/mecsci/grains-videos3.0/icons/briquesss-Inria_H264_800x450_1Mbit.png)
Documentation : https://github.com/downloads/jcb/CSIRL/baseball.pdf (voir aussi le manuel complet)
Dernière modification : mai 2023.