Téléchargement des ressources
Les collègues simplement intéressés par des ressources directement utilisables téléchargeront en fin d’article le fichier LesAnnivDyn qui contient les figures et les scripts correspondant aux onglets AnnivIntro, Dyn1, Dyn2 et Dyn3. L’utilisation est simple : on lance la figure CaRMetal puis, sur cette figure, le script du même nom.
Rappel pour animer le point M : on se place sur l’outil animation (3° icone de la palette Edition) et on montre successivement (trois clics) : le point M (qu’on veut animer) le cercle (lieu du point) et à nouveau M (pour lancer l’animation).Note après la publication de la version 3.5
Cet article a été écrit en février 2010. Depuis avril 2010 et la version 3.5, les scripts peuvent être inclus dans la figure.
Les deux figures principales, avec scripts intégrée dans le nouveau format de classeurs de CaRMetal sont disponible à cette page qui contient plus de 50 scripts dans cinq classeurs à télécharger.
L’objectif de cet article est de présenter une technique somme toute élémentaire, et de l’appliquer à la simulation bien classique des coïncidences des anniversaires. Le résultat obtenu illustre une nouvelle fois que des outils nouveaux permettent de revisiter nos classiques en leur apportant une dimension plus dynamique.
Pour présenter cette méthode, nous avons choisi de la décontextualiser, avec une mise en oeuvre dans un registre éloigné de nos problématiques scolaires. Ce sera la question des 8 reines sur un échiquier. Puis nous reviendrons au problème des coïncidences des anniversaires. Cette approche permet de bien distinguer les différentes techniques utilisées dans les scripts des onglets Dyn1 et Dyn2.
L’article est structuré ainsi
Les 8 Reines : Le script reprend un algorithme récursif disponible sur le Web, puis on détaille la technique d’affichage
Anniv Intro : Revient sur le thème, propose un script possible, utilisable en classe, qui peut être un projet de script en formation des enseignants.
Anniv DynPartielle : Présente la technique utilisée avec les 8 reines, directement appliquée à la situation. Puis on voit que ce n’est qu’une première étape.
Anniv Dyn1 : Modification du script pour obtenir une simulation de statistiques dynamiques sur cette situation, avec la fluctuation des échantillonnages.
Anniv Dyn2 : Ajout d’une modification des effectifs au curseur.
Anniv Dyn3 : Modification du script précédent pour visualiser la convergence des tirages vers les valeurs théoriques.
Les 8 reines
Le placement de 8 reines sur un échiquier de telle façon que chacune ne soit en prise avec aucune des autres est un classique de programmation. C’est selon le contexte, un exercice sur la récursivité, un exercice sur la gestion des contraintes, et généralement les deux.
On sait que ce problème a « traditionnellement » 92 solutions.
Traditionnellement signifiant ici qu’on se place dans une approche informatique : on fait balayer à la première reine la première colonne et on cherche toutes les positions possibles pour les reines sur les autres colonnes. Travaillant ainsi, mathématiquement plusieurs solutions sont isométriques ce qui fait qu’au final il n’y a que 12 solutions isométriquement différentes (wikipedia).
L’objectif de cet onglet est surtout de mettre en place une fonction JavaScript pour afficher, dans CaRMetal, avec 8 points représentant les 8 reines, les 92 solutions à l’aide d’un curseur allant de 1 à 92.
Quelques mots sur l’algorithme
Nous passerons un peu vite sur la description de l’algorithme de recherche des solutions. Des centaines de pages Web rendent compte de cet exercice, donnons seulement les grandes lignes utilisées.
Puisqu’il n’y a qu’une reine par ligne, on se limite généralement à noter les solutions dans un tableau à une seule dimension. Dans le script suivant JeuEch[i]=j signifie que la reine de la colonne j est en ligne i.
On peut utiliser une fonction pour tester si une position est correcte comme celle-ci :

L’intérêt - théorique ici car l’exécution est très rapide - d’utiliser des booléens est dans leur traitement paresseux : si le premier est vrai le reste n’est pas évalué, de même pour le second.
Ensuite on rempli un tableau à deux dimensions LesSol[92,8] qui pour chaque solution contient les numéros de ligne des reines pour cette solution :

À ce sujet mentionnons une éventuelle difficulté de JavaScript qui a un traitement de la définition des tableaux à double entrée assez éloignée des autres langages - pour l’allocation de la mémoire en particulier - et qui le rend assez inaccessible aux élèves sauf à donner la procédure suivante, générique : on doit déclarer des tableaux de tableaux de colonnes (ou de lignes).

Placer les 92 solutions dans 8 points
La seule raison de cet onglet est la présentation du procédé CarScript qui permet de placer les 92 solutions sur les 8 points qui vont représenter les 8 reines, afin de pouvoir balayer toutes les solutions à l’aide d’un curseur allant de 1 à 92 comme dans la copie d’écran suivante :

Cela signifie que le script se lance sur une figure spécifique - téléchargeable en fin d’article - qui contient un curseur. Le principe est de construire des points dont les coordonnées sont des combinaisons linéaires de booléens de type (n==k) pour k allant de 1 à 92. En fait, même si ce n’est pas indispensable ici, mais parce que ce le sera dans la suite de l’article, plutôt que d’agir directement sur les points, on a choisi d’affecter à 8 expressions de CaRMetal, TR0 à TR7, les ordonnées des points des reines (les abscisses sont fonction des colonnes). Ainsi le script donne ses valeurs aux expressions de CaRMetal, la construction des points reste interne à la partie géométrique du logiciel.
La fonction de transfert du tableau à deux dimensions LesSol[92,8] aux 8 expressions TRx est la suivante :

On place donc dans l’expression CaRMetal « TR »+i, la chaîne solTR qui est une combinaison linéaire des booléens (n==k) affectés de la valeur de la i-ième colonne (position de la reine). Un changement d’échelle (6-2-kTR) est nécessaire pour s’adapter au dessin de l’échiquier. Comme dans tout traitement de ce type des chaînes, la dernière valeur est en dehors de la boucle (la seule différence est la fin de la chaîne qui ne se termine plus par +« + ».
Les expressions TR dans le logiciel sont donc de longues chaînes dont voici un petit extrait :

Pour ne pas encombrer l’ouverture de cet article, la figure n’est pas en ligne, elle est téléchargeable. Mais il est plus amusant de lancer le script sur la figure prévue à cet effet : on voit que le plus long dans ce script est l’affichage de l’échiquier, le reste est quasiment instantané.
Micro Bonus arithmétique
Une propriété élémentaire des carrés latins peut s’appliquer aux solutions des 8 reines. Notons i et j les indices de ligne et colonne des emplacements des reines d’une solution, et 8(i-1)+j le numéro de la case de l’échiquier (de 1 à 64) où est la reine (i,j) . Puisqu’il y a une reine par ligne et une par colonne, les 8 reines prennent les 8 valeurs possibles pour i ainsi que pour j. Il en résulte que dans toutes les solutions, la somme des numéros des 8 reines est une constante, la constante magique du carré latin d’ordre 8 : 2x28+36 = 260.
Anniv Intro
Anniversaires - Script introductif
Le corps de cet article reprend le thème des coïncidences des anniversaires du document d’accompagnement des programmes. Ce thème a été abordé le mois dernier sur le site de l’IREM de La Réunion par notre collègue Nordine Bernard Toumache avec une utilisation de la TI 83.
La version que l’on va proposer est inspirée d’un échange sur ce sujet entre l’IREM de Toulouse et celui de La Réunion. Monique Gironce, de l’IREM de Toulouse, est bien connue des utilisateurs de CaRMetal par sa production de tutoriaux avec Wink. Avec le groupe qu’elle anime sur les CarScripts, elle a proposé un premier script qui construit, pour une classe de 30 élèves, jusqu’à 100 échantillons de plusieurs dizaines de classes (on peut choisir 100 échantillons de 100 classes par exemple).
Pour des questions d’échelles, le script se lance sur une figure préconstruite. Un des intérêts de ce script est qu’il peut se lancer plusieurs fois sur la même figure, avec des tailles d’échantillons différents, et donc illustrer non seulement la fluctuation entre les échantillons, mais aussi la précision obtenue selon les effectifs des échantillons.
A des fins pédagogiques, en particulier pour des formations continues, le script est volontairement simple et largement commenté. Il est composé d’une fonction principale :

Deux remarques
On notera le choix d’utiliser le tri de javascript (plus efficace que celui qu’on aurait mis en place). C’est une idée de Alain Busser, bien connu des visiteurs de ce site, avec l’argument qu’il est pratique en classe d’utiliser ces fonctionnalités pré-construites, pour passer plus de temps sur ce que l’on veut enseigner (quartiles etc).
Cette remarque rend compte aussi que ce thème circule entre Toulouse et La Réunion depuis un moment et que chacun a apporté un élément à la production finale.
et du corps du script ...

La visibilité du résultat est plus grande si on trace des segments. D’où une initialisation (lignes 35 à 38) pour avoir le premier point du tracé avant de reprendre le tout dans une boucle pour la construction du segment [ab].
Toujours dans ce contexte de formation continue, on notera une sortie console en même temps que la construction du graphique. Pour une lisibilité optimale à l’écran, on utilise les points I et J construits préalablement, qui sont manipulables pour s’adapter à l’écran, et le nombre d’échantillons.
L’entête du script rappelle la procédure pour changer de couleur à chaque nouveau lancement du script.
Ce qui donne pour un premier lancement du script (100 échantillons de 100 classes chacun) :

On peut conserver le nombre d’échantillons et faire varier leurs effectifs. Voici par exemple en vert des effectifs de 400 classes par échantillon et en rouge des effectifs de seulement 40 classes par échantillon. Il y a matière à expérimentation, exploration et débat sur le sens de ces observations.

Bien entendu on pourrait ensuite ajouter de nombreuses données à l’intérieur du script. Le choix du groupe de travail de l’IREM de Toulouse d’utiliser la sortie console est surtout de montrer cette possibilité aux collègues lors de formations.
Dans les onglets suivants, on se propose de donner une dimension dynamique à ce premier script, d’abord en permettant de choisir le nombre d’élèves par classe au cours du script (en fait la seule originalité de cet article) puis par le maintien d’un tirage régulier toutes les secondes, de permettre d’utiliser effectivement de manière dynamique ce choix du nombre d’élèves par classe pendant l’exécution du script. Le résultat va être une simulation de l’activité avec manipulation directe sur le nombre d’élèves par classe, puis sur les effectifs des échantillons également.
Anniv DynPartielle
Anniversaire dynamique - Première approche
On se propose de se donner la possibilité de choisir le nombre d’élèves par classe. Dans cet exercice transitoire, on se limite à la production d’une seule série de 100 échantillons de 100 classes pour détailler le principe. Dans les onglets suivants on rendra la simulation plus conforme à ce que l’on attend, avec un échantillonnage régulièrement renouvelé.
On choisit des classes de 20 à 36 élèves. Le principe consiste à faire des tirages de 36 élèves et de comptabiliser les coïncidences dans un tableau, à partir de 20 élèves. La fonction Random étant équirépartie, a priori ce choix n’apporte pas de perturbation dans les résultats, les tirages de nombres aléatoires sont simplement pris dans des tranches particulières.
La fonction principale est la suivante (commentée ci-dessous) :

Le tableau coïncide comptabilise sur les 100 lancers, une coïncidence d’anniversaire (la première rencontrée) pour l’élève j avec les élèves précédents [lignes 15 à 21]. Ensuite, à partir de 20 élèves , le tableau s somme les coïncidences [lignes 24 et 25]. Ainsi s[k] est le nombres de coïncidences d’anniversaires pour une classe de k élèves dans ces 100 échantillons. Ce tableau est retourné par la fonction.
Exercice : reprendre l’astuce de Alain Busser, vue à l’onglet précédent, pour traiter les coïncidences plus rapidement.
Ensuite on procède exactement comme dans le traitement des 8 reines, en créant une chaîne de caractère qui va être une des coordonnées booléennes d’un point [lignes 31 à 35].

Le programme principal se termine par l’affichage d’un segment. Pour montrer une autre possibilité de construction de ce segment, on a choisi une écriture plus courte mais théoriquement plus gourmande en temps d’exécution. Pour éviter d’écrire deux fois les lignes 30 à 34, (choix de l’onglet précédent) on utilise un if pour éviter la première itération [lignes 36 à 38 et 40] ce qui ajoute 100 tests conditionnels (instantanés en fait). On peut choisir l’option de l’onglet précédent (en plaçant alors le premier point dans la variable b).
On notera l’affectation directe des points. En effet dans cette figure, les points solutions ne sont construits en fait qu’une fois, et il n’y a pas de rafraîchissement à effectuer : la modification de n s’applique hors du script : il n’est pas nécessaire de passer par l’utilisation des expressions.
Le résultat est encourageant : on peut bien faire varier le nombre d’élèves par classe, et on visualise 100 échantillons de 100 classes dans chaque cas. Mais les tirages ne sont pas réactualisés : quand on fait varier le curseur, on repasse par les mêmes valeurs comme on peut le voir dans la vidéo suivante.
Il faut donc aller plus loin pour avoir une simulation véritablement dynamique. C’est l’objectif du prochain onglet.
Anniv Dyn1
Anniversaires dynamiques - 1. Fluctuation des échantillonnages
On veut cette fois enrichir la figure d’un tirage aléatoire régulier des différents échantillons. Dans la figure suivante on a choisi 20 échantillons (tranches dans le script) de 100 classes de 20 à 36 élèves soit une amplitude de 17. Comme dans l’exemple des reines, la figure initiale est largement préparée pour accueillir le script qui va lui être appliquer : il y a 17 expressions TRx, une par nombre d’élèves par classe, et 20 points Axx pour les 20 échantillons. Les segments sont construits directement dans la figure.
Amélioration possible du script
L’utilisation des expressions TRxx vient du fait qu’au moment où ce script a été réalisé, la fonction Move, pour déplacer un point à l’écran par script, n’acceptait pas les coordonnées utilisant des booléens. Quand cette fonctionnalité sera disponible, la figure serait à reprendre car plus facile à réaliser.
En effet ici nous avons opté par un rafraîchissement interne au moteur géométrique, en définissant les coordonnées à partir des expressions TRx sous la forme :

où M est un point qui tourne sur un cercle. Cet artifice - de d(M) qui indique le mouvement de M dont l’utilisation est détaillée ici - permet de tester s’il se passe quelque chose à l’écran et donc force le rafraîchissement du point dans ce cas, ce que je n’ai pas su réaliser directement dans le script. Il est probablement possible de réaliser quelque chose d’un peu plus simple.
La figure initiale est plus complète que la précédente. Dans la copie d’écran ci-dessous, les points Axx sont initialement sur l’axe des abscisses en vert fluo.

On y a ajouté le calcul de la valeur théorique de la probabilités d’une coïncidence (au moins) en fonction du nombre d’élèves. Cette expression est construite préalablement par l’application du script suivant :

que chacun peut tester sur une figure de base (curseur + expression) en copiant le script suivant (et vérifier en activant les sorties « console texte » mises en commentaires)
Dans l’onglet précédent, on avait choisi de travailler avec une fonction qui calculait sur un seul échantillon de 100 classes. Cette fois on enrichit la fonction pour travailler sur les 20 échantillons à la fois. On utilise donc un tableau à deux dimensions (que l’on initialise avec la fonction déjà vue avec les 8 reines).
Comme il est prévu d’autres utilisations, utilisant plusieurs variables de cette structure de tableau, on a choisi cette fois d’optimiser la mémoire. La variable coincidence de l’onglet précédent était un tableau à 36 variables alors qu’on n’utilisait que les 17 dernières variables seulement. Cette fois on choisit d’utiliser un tableau LeTab[20,17] d’où une indiciation adaptée.
La fonction Echantillon de l’onglet précédent est transformée en GrandEchant qui traite les 20 échantillons à la fois (coincidence est remplacé par LeTab). La fonction ne renvoie pas un tableau, celui-ci est désormais une variable globale.

Remarques :
1. On notera une différence avec l’onglet précédent sur les 20 premiers élèves : dans la ligne 29, on engrange directement toutes les coïncidences avant 20 élèves alors que dans l’onglet précédent, ce n’est pas le cas de la ligne 18 correspondante. Cela se faisait dans la boucle de la ligne 24.
2. Tenant compte de cette modification, là encore on peut choisir d’améliorer le remplissage du tableau par l’utilisation du sort de JavaScript.
Le corps principal du script est intégré dans une boucle qui teste si l’utilisateur clique pour stopper le script. La case à cocher « Continuer » est une variable CaRMetal qui s’appelle « cont ».

La ligne 51 du corps principal correspond à la ligne 25 du script de l’onglet précédent. La technique montrée dans l’onglet des 8 reines ne prend seulement que les cinq lignes 52 à 56.
Puisque l’on est dans une boucle « infinie », il faut réinitialiser le tableau EchDyn avant chaque nouvel usage, ce qui se fait dans les lignes 61 à 63.
Ce script illustre bien l’imbrication que l’on peut produire entre une figure - préparée pour l’application d’un script et les possibilités des Carscripts. Les points Axx attendent, pour s’actualiser, de nouvelles valeurs des expressions TRx données par le script. Les segments sont préalablement construits. Un autre script a été appliqué pour le suivi de la valeur théorique en fonction du curseur n.
Au moment de la mise en ligne de cet article, on ne peut pas lancer un script en ligne dans une figure, d’où cette vidéo (26 s - 2 Mo) qui rend compte du fonctionnement de ce script sur cette figure.
On notera que la fonction GrandEchant prend le paramètre 100 alors que cela pourrait être une variable. Comme on le voit avec le nombre 100 placé en chaîne de caractère dans les lignes 53 et 54, dans cette figure l’effectif des échantillons est constant. On ajoutera un curseur pour l’effectif dans l’onglet suivant.
Anniv Dyn2
Anniversaires dynamiques - 2. Modification des effectifs
La modification à apporter pour mettre l’effectif en paramètre est minime. Mais on a choisi de la présenter séparément, comme enrichissement de la figure précédente et, cognitivement, comme préparation à la figure suivante.
Il faut donc ajouter un curseur d’effectif et transformer un texte en expression (celui qui annonce l’effectif) :

Et la modification du script est minime également :

Il y a l’ajout de la variable ChEff (choix de l’effectif) en ligne 48 qui lit le nouveaucurseur eff de la figure. Puis le remplacement de la constante 100 par ChEff en lignes 55 et 56 et c’est tout. On peut enlever la pause car quand l’effectif est de 200 à 300 les calculs sont suffisament longs pour que ce ne soit pas la peine de ralentir la boucle.
Voici une vidéo (57 s - 4,7 Mo) de ce que produit le script AnnivDyn2IREM sur la figure du même nom (dans le fichier zippé en fin d’article).
L’onglet suivant contient une autre variante pour accumuler les classes dans les échantillons. L’essentiel a été déjà fait dans le script de Dyn1.
Anniv Dyn3
Anniversaires dynamiques - 3. Convergence
On se propose d’accumuler désormais les effectifs des échantillons. La figure est quasiment la même que dans l’onglet Dyn1 (seule une variable supplémentaire apparait)

Le script comporte lui une modification plus profonde, en particulier on distingue l’ajout d’un nouvel effectif (AjoutDyn) de l’effectif en cours (EchDyn des scripts précédents). Il y aura donc deux variables globales de type tableau à deux dimensions :

De même la variable NbreEch est nouvelle, c’est l’effectif de chaque échantillon. Cette variable globale est modifiée - même si ce n’est pas très heureux - dans la fonction GrandEchant : lignes 34 et 35 qui mettent à jour la variable CaRMetal clpt (pour « classes par tranche »).

La suite du corps du script commence par un tirage initial de 100 classes pour chacun des 20 échantillons (« tranches » dans le script). Pour cela, on reprend hors de la boucle Continuer, les lignes 48 à 56 du script de l’onglet Dyn1.
La partie nouvelle du script est la nouvelle boucle Continuer :

On effectue de nouveaux tirages (ici par série de 100 classes mais on peut tester avec 50) qui sont placés dans la variable AjoutDyn. (ligne 65). De par la ligne 27 de GrandEchant, on a déjà dit que jusqu’à 20 on a sommé toutes les coïncidences.
La ligne 68 met à jour, en fonction des nouveaux tirages de AjoutDyn, les valeurs de EchDyn pour le cas n=20 (indice [0]). On place ensuite dans une même boucle (lignes 70 et 71) le calcul final de AjoutDyn (qui reprend la ligne 50 du script de Dyn1) pour les classes de 21 à 36 élèves et la mise à jour de EchDyn qui devient désormais l’effectif global de chaque échantillon. Les lignes 72 à 78 ne sont modifiés que par la variable NbreEch (à la place de 100). Enfin la remise à zéro est bien entendu sur la variable AjoutDyn. Si l’écriture est un peu technique, l’algorithme sous-jacnet reste élémentaire.
Voici ce que donne ce script appliqué à cette figure (disponible dans les fichiers en fin d’article).
La mise en place de cette seconde variable AjoutDyn permettrait bien d’autres variations. On pourrait déjà mettre un curseur pour faire varier les ajouts de 20 à 100 par tranche de 20. Comme à l’onglet précédent, il n’y a que quelques lignes à modifier dans le script précédent. Mais on peut aussi envisager d’autres utilisations comme l’ajout et le retrait de tirages pour conserver un nombre constant et avoir une approche différente de la fluctuation des échantillonnages.
Bilan
Cet article a été construit sur une image mentale trés simple : un curseur qui permettrait de parcourir des positions d’états différents d’une pile dans une calculatrice. La version Carscript consiste à construire des expressions CarMetal afin de transformer chaque point en cette pile qui contient autant d’états que l’on souhaite. La technique présentée ici est probablement améliorable, et le sera certainement avec l’amélioration de quelques fonctionnalités. (par exemple un Move avec paramètres algébriques permettrait de faire des choses plus simples).
Fondamentalement, les scripts n’apportent pas une nouvelle possibilité : ce que l’on vient de faire serait réalisable en applet java ou en flash sans difficulté, presque en recopiant une grande partie du code. Cette remarque interroge alors sur notre relation à l’environnement de travail. Il se peut que le fait de travailler dans un environnement dynamique mobilise davantage l’immagination sur les potentialités dynamiques d’une situation que l’on pouvait penser jusque là plus statique.
Il reste que la réalisation de cette manipulation directe au curseur sur le nombre d’élèves par classe ou les effectifs des échantillons n’a été possible que grâce à la l’interaction étroite entre le javascript et les différentes variables CaRMetal. En géométrie dynamique, ceci est une réelle nouveauté puisqu’il y a interaction entre deux environnements, l’un géométrique, l’autre de programmation. Et nous n’avons pas fini d’explorer les possibilités de cette interaction.
Merci de proposer en commentaire des liens vers vos propres productions de ce type, et/ou les améliorations que vous imaginez ou avez réalisées.
Téléchargement
Vous trouverez les différentes étapes regroupées. Pour l’essentiel il faut lancer la figure et appliquer le script associé (même nom).
Rappel pour animer le point M : on se place sur l’outil animation (3° icone de la palette Edition) et on montre successivement (trois clics) : le point M (qu’on veut animer) le cercle (lieu du point) et à nouveau M (pour lancer l’animation).
Commentaires