Séances algorithmiques

WORK IN PROGRESS

Qu'est-ce qu'un algorithme ?

=> c'est une stratégie gagnante

Illustration : Jeu de Nim (régles)

Matériel : 16 clous, dont 1 coloré (le clou empoisonné)

Déroulement :

• introduction du jeu de Nim
  • sortie des clous
  • principe : on peut retirer de 1 à 3 clous à la fois
  • le dernier clou est empoisonné
• quelques parties
• constat du gain à coup sûr
• explication : "j'ai un truc", une stratégie gagnante (laisser l'adversaire dans une situation à 1 modulo 4 clous - attention, si variante du clou en or, laisser un multiple de 4)
• trouver une représentation visuelle de la stratégie gagnante : un jeton sur les clous particuliers ? une bande de papier avec la suite de chiffres marqués ?
• idée de la stratégie gagnante (situation initiale, coups autorisés, méthode pour arriver à une situation finale gagnante)

Intérêt en informatique : on peut expliquer une stratégie gagnante, comme en informatique où il faut expliquer à l'ordinateur ce qu'il faut faire.

Introduction des trois caractéristiques :

• rapide
• fidèle ("il fait tout ce qu'on lui demande")
• stupide

(illustration des deux dernières caractéristiques : il s'éteint lorsqu'on lui demande)

Objectif de cette activité : pourquoi est-ce qu'un algorithme est important en informatique ; les algorithmes datent d'avant les mathématiques