Séances algorithmiques

De Nybi.cc
Révision de 17 novembre 2011 à 21:03 par Mquinson (discussion | contributions) (Ajout d'un lien vers les crèpes sur interstices (merci Isabelle debled))

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
  • Voir aussi : http://interstices.info/jcms/n_52318/genese-dun-algorithme?hlText=cr%C3%A8pes (mais c'est vachement moins IRL)

=> 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)

Debrief :

  • travail du rogrammeur = se faire obéir par des tas de fils. Méthode = apprendre des algorithmes abstraits qu'ils appliquer aux problèmes qu'ils rencontrent. le principe de la décomposition en sous-problèmes plus simples = grand classique souvent gagnant.
  • qualité d'un algorithme = performance et correction.
  • métier de certains chercheurs en informatique = inventer de nouveaux algorithmes, étudier la correction des algorithmes et leurs performances

Activité: plus court chemin

Matériel: une planche avec des trous bien verticaux dedans, des clous du même diamètre qu'on rentre dans chaque trou (la pointe en bas); une corde blanche et un marqueur.

Déroulement:

  • Étape 1: le participant a 1mn pour comprendre la consigne et faire faire un chemin à sa ficelle qui passe par toutes les vis une fois unique, et qui boucle.
  • Étape 2: on refait sans limite de temps. Sur la ficelle sont marquée les différentes longueurs record. Si le participant fait plus court, on fait un trait au marqueur sur la longueur obtenue.
    • La discussion après l'étape 2 est qu'en beaucoup plus de temps, on a trouvé une solution marginalement meilleure.
    • On peut aussi évoquer à quoi ressemblerait l'algo exact et sa complexité, mais c'est pas central pour l'activité. D'autant qu'il est tellement con qu'il n'est pas facile de convaincre qu'il n'en existe pas de meilleur. On peut déplier les différents algos tentants et faux connus si on a peur de s'ennuyer (http://www.loria.fr/~quinson/Teaching/TOP/TOP-handout.pdf pages 120-123). Mais bon, c'est probablement déroutant pour les participants de se trouver face à face avec un problème ouvert...
    • En fait la discussion est plutot sur les heuristiques, avec un message de la forme "trouver la solution optimale est parfois très dur, alors qu'on peut trouver un truc pas trop con très vite -- ce n'est plus un algo mais une heuristique".
    • Une fois qu'en est là, il est tentant de parler des problèmes où il faut déployer les heuristiques car on ne connait pas d'algo efficace. Pour ça, les problèmes NP sont quand même de supers candidats. Pour rappel, NP veut dire "Non-deterministic Polynomial", et c'est une classe de problèmes où on ne connait pas d'algorithme polynomial pour trouver des solutions, mais vérifier qu'une solution est correcte prend un temps polynomial. C'est le cas du voyageur de commerce, le problème dont on s'inspire ici : quand la question est "est-ce qu'il existe un chemin de longueur N ou moins?" et si on me propose un chemin donné, je peux bien vérifier en temps polynomial si sa longueur totale respecte les contraintes données.
    • Et une fois que t'as réussi à faire entrevoir ceci à un néophyte, ce serait malice de ne pas parler du problème phare de l'informatique: P=NP. Le problème à 1M$, qui protège ta carte bleue. La question est de savoir si P = NP ou pas. Autrement dit, s'il existe un algo polynomial pour les problèmes NP. Pour l'instant, personne n'en a trouvé, mais personne n'a réussi à démontrer qu'il n'en existe pas, non plus.
    • On a alors envie de parler de NP-completude, mais c'est un peu difficile. L'idée est que les informaticiens classifient les problèmes qu'ils n'arrivent pas à résoudre selon la difficulté de les résoudre. C'est un peu tordu car on réfléchi à ce qu'on gagnerait à savoir faire des trucs impossibles pour l'instant, mais bon. On regarde si on saurait résoudre un problème impossible avec la solution d'un autre problème impossible. C'est comme si on se posait des questions comme "et si je savais voler, est ce que je pourrais résoudre de la famine dans le monde? Par ailleurs, si je savais résoudre la famine dans le monde, est ce que je saurais voler?". Certains chercheurs en informatique sont payés pour répondre à ce genre de question, avec juste un peu d'enrobage mathématique pour éviter les questions embarassantes des passants :)
    • On peut passer par l'introduction des problèmes NP-difficiles. On peut voir leurs solutions comme des outils sur-puissants, qui seraient capable de résoudre tous les problèmes NP si on savait construire ces solutions. Ce sont donc des problèmes plus durs que tous les NP, d'une certaine façon.
    • Fait amusant, certains de ces outils sur-puissants sont eux-même des problèmes NP, c'est à dire qu'on pourrait les construire en utilisant un problème NP-difficile. On dit qu'ils sont NP-complets. Ils sont donc à la fois NP (on ne sait pas les résoudre en temps polynomial, mais on sait reconnaitre qu'une solution est la bonne ou non en temps polynomial) et NP-difficile (si on savait les résoudre, on saurait résoudre tous les problèmes NP). Le schéma en haut de http://en.wikipedia.org/wiki/NP-complete est pas mal pour aider à se repérer.
    • Si la question d'un exemple de problème NP-difficile qui ne soit pas NP (et pour lequel on ait pas de variante NP), on peut citer le jeu d'échec, puisque trouver une stratégie gagnante est un problème reconnu exponentiel. Il y a même une classe de complexité pour cela: EXPTIME.
    • Pour revenir au problème des clous,
      • la question "trouver le plus court chemin" est NP-difficile et pas NP. Quand on me donne une solution, je peux pas vérifier simplement si c'est la plus courte.
      • La question "est ce qu'il existe une solution de longueur inférieure à k" est NP car on ne connait pas d'algo polynomial pour répondre, mais quand on me propose une solution, je peux vérifier sa longueur facilement. Et par ailleurs, on a fait toutes les réductions qui vont bien pour montrer que ce problème est NP-complet (le schéma de http://en.wikipedia.org/wiki/NP-complete#NP-complete_problems est bien)