Séances algorithmiques

De Nybi.cc
Aller à : navigation, rechercher

WORK IN PROGRESS

Activité : 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 d'un ordinateur :

  • 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é : expliquer pourquoi est-ce qu'un algorithme est important en informatique (rappel : les algorithmes datent de bien avant l'informatique)

=> algorithme : situation initiale, modification, situation cible

Le travail de l'informaticien n'est pas de résoudre les problèmes, mais de comprendre suffisamment pour l'expliquer à un "crétin fini". Travail de l'informaticien = travail de fénéant : l'informaticien est capable de réfléchir longtemps pour ne plus réfléchir après.


Activité : le crêpier psycho-rigide

Matériel : des planchettes en bois de tailles et de couleurs différentes (faces reconnaissables), éventuellement une pelle à tarte pour retourner les planchettes

Déroulement :

  • présentation de la situation
    • le crêpier a fait des crêpes
    • elles ne sont malheureusement pas bien rangées ! petites et grandes sont mélangées, et on voit la face un peu brûlée de certaines crêpes !
    • inacceptable !
    • on décide de l'aider à les ranger
    • problème : il n'a qu'une seule assiette et sa pelle à tarte
  • présentation des coups autorisés :
    • on prend une ou plusieurs crêpes en haut de la pile et on retourne le tout d'un coup
    • attention vous ne serez pas toujours là pour aider le crêpier. Il n es'agit pas de trier ses crêpes mais de lui montrer comment trier ses crêpes
  • faire tester à quelqu'un
    • "tentez de résoudre ce problème intuitivement, on réfléchira après"
    • si la personne bloque, lui donner un conseil : "une bonne première étape est de se débrouiller pour mettre la grande en bas"
    • si ça ne passe pas, aider ("où est-ce que la grande devrait être pour pouvoir la mettre en bas") et donner le conseil pour l'étape suivante (guide pas-à-pas)
    • faire verbaliser l'algorithme au cobaye

=> L'algorithme est quelque chose de suffisamment simple pour pouvoir l'expliquer à un imbécile (référence à l'activité précédente)


Activité : Baseball multicolore

Matériel : 6 ensembles de Lego de couleurs différentes, chaque ensemble est composé de 3 pièces : une de 4 (la maison) et deux de 2 (les bonhommes)

Déroulement :

  • Situation initiale - disposition
    • on dépose les maisons aux 4 coins du terrain
    • on retire un bonhomme quelconque du jeu
    • on mélange les bonhommes et on place 2 bonhommes au hasard sur chaque maison (sauf une). On essaiera de ne pas mettre directement les bonhommes sur leurs maisons
  • Objectif : tous les bonhommes veulent rentrer à la maison (celle de leur couleur)
  • Coups autorisés :
    • un seul bonhomme peut bouger à la fois
    • il ne peut pas y avoir plus de 2 bonhommes par maison
    • un bonhomme ne peut se déplacer que vers l'une des deux maisons voisines de celle où il est
    • Note : les joueurs font moins de fautes de jeu en n'utilisant qu'une seule main et un seul doigt
  • on demande d'abord aux spectateurs de faire rentrer les bonhommes intuitivement
  • on demande aux spectateurs d'expliquer comment ils ont fait => 2 cas :
    • ils y arrivent et on ajoute des couleurs
    • ça bloque et il faut les aider : on pose une pièce avec une flèche qui indique un sens de rotation, une nouvelle couleur et on propose un algoritme (qui se révèlera faux)
      • sens donné par la pièce
      • à chaque étape, la maison de destination est imposée (celle où il y a trou, donc il faut choisir quel bonhomme bouger)
      • on se fixe comme règle : faire bouger le bonhomme le plus loin
      • on réitère
    • on leur fait faire tourner l'algorithme
    • ça converge (très souvent) vers la situation finale
    • "c'est bien : c'est simple, c'est assez rapide, c'est élégant... mais faux !". On prend une situation convergente, et on inverse deux pions non adjacents. Et maintenant ?
    • on constate que ça ne converge plus, car il faudrait qu'une pièce double l'autre. Impossible !
    • donc ce n'est pas un bon algorithme : on a l'impression qu'il fonctionne, mais on arrive à trouver des contre-exemples
    • c'est là qu'on comprend l'intérêt des chercheurs en informatiques : trouver l'algorithme et prouver que l'algorithme est correct (comment ? avec des maths. attention, c'est compliqué)
    • on va chercher le bon algorithme. On change la disposition du plateau : on dispose les pions en ligne et on peut même ajouter d'autres couleurs. On respecte bien toujours les règles, on s'est même interdit de faire quelque chose d'autorisé par les règles. Note : pour la suite c'est mieux que la couleur à un seul bonhomme se situe à une extrémité.
      • on se fixe des objectifs intermédiaires comme lors de l'activité du crêpier psycho-rigide : on veut amener les pions de la couleur de l'extrémité
      • mécanisme : [schemas ou photos ou video]
      • on peut se poser la question de performance : c'est lors des choix que l'on peut amélioreor les performances. Soit on fait au hasard, soit on choisit de déplacer le pion le plus éloigné
      • on fait tourner l'algorithme jusqu'à ce que le participant soit convaincu qu'il fonctionne
    • question de la correction de cet algorithme :
      • et si c'était encore un algorithme incorrect ? Non, c'est un algorithme connu, que l'on apprend au deuxième cours d'algorithmique.
      • analogie informaticien/musicien : le musicien fait ses gammes, l'informaticien apprend par coeur des algorithmes
      • lorsque l'on soumet un problème à un informaticien, il essaie de se raccrocher à des problèmes qu'il connait (ex. du cas du crêpier : est-ce les tours de Hanoï ? Non, l'histoire ressemble mais la résolution est totalement différente)