par Patrice Debrabant
Dans cet article, on va tracer différentes fractales : le flocon de von Koch, des arbres et les fractals de Sierpiński. On va montrer que chacune d’elles peut être tracée de différentes méthodes :
- des méthode non récursives (stochastique ou par générateur) ;
- une méthode par L-systèmes (généralisés) ;
- des méthodes récursives :
- par fonctions récursives ;
- par clonage et programmation à la naissance ;
- par clonage et programmation événementielle.
Pour ces fractales (qui se ressemblent) ces méthodes sont en quelque sorte interchangeables.
Toutes les méthodes sont présentées en langage Scratch. Certaines peuvent être transposées sans difficulté dans un autre langage de programmation associé à une tortue (Python, DGPad, GéoTortue, etc).
Pour les méthodes utilisant le clonage pour mettre en œuvre la récursivité, trouver une forme d’équivalent en Python du programme Scratch est un défi pour les professeurs de lycée (et/ou les lecteurs) férus de Python.
Certaines fractales sont définies par un processus qui s’applique à des surfaces. On verra deux méthodes pour les implémenter avec Scratch :
– par estampillage ;
– par clonage.
On verra enfin comment les méthodes peuvent être appliquées pour tracer la courbe en pointe de flèche de Sierpiński.
Tracé du pentagone de Sierpiński (défini par surfaces) par clonage
lien
Le programme présenté ci-dessus est écrit en langage Scratch, mais destiné à TurboWarp en mode clones infinis.
Dans le cadre d’un studio Scratch (comme c’est le cas ici) , le nombre de clones est limité à 300.
Plan
- Introduction
- I. La courbe de Von Koch
- II. Arbres
- III. Fractals de Sierpiński
- IV. La courbe en pointe de flèche de Sierpiński
- V. Compléments
Introduction
Quand le logiciel Scratch (même s’il n’était pas nommé explicitement, du moins au début) est apparu officiellement dans les programmes, la pertinence pédagogique des fonctionnalités les plus étonnantes du logiciel comme les clones ou la communication par messages a fait débat : pour certains observateurs, c’était une initiation bienvenue à des paradigmes de programmation avancée comme la Programmation Orientée Objet, pour d’autres c’était une hérésie par manque de rigueur.
En pratique, ces fonctionnalités sont très rarement étudiées. Elles peuvent épisodiquement êtres utilisées dans un projet de jeu, tout au plus.
Lors du passage au lycée, Scratch est totalement (dans les faits sinon dans les déclarations) abandonné au profit de Python. Les fonctionnalités de Scratch que l’on vient d’évoquer n’ont pas été étudiées. Elles ne sont pas non plus réinvesties.
Dans cet article, on va défendre l’idée que ces fonctionnalités ont un véritable intérêt, qui témoigne de la qualité pédagogique remarquable du logiciel Scratch. Non seulement ces fonctionnalités constituent une initiation à des paradigmes de programmation avancés, mais elles en expriment une implémentation particulière originale et cohérente.
Comme annoncé dans le titre, dans cet article on va tracer des fractales. L’objectif est de présenter des méthodes générales qui puissent s’appliquer à chacune.
La méthode la plus classique consiste à utiliser une fonction récursive, en utilisant le confort de la syntaxe que permet un langage de programmation. Cette méthode a des avantages incontestables, mais elle n’a pas que des avantages. En particulier, on peut considérer qu’elle délègue la difficulté au langage de programmation lui-même, qui agit comme une boîte noire. Et elle est difficile à comprendre pour des élèves de collège (et de lycée).
Pour la méthode par L-système, on présentera une généralisation des L-systèmes qui sera précisée le moment venu.
L’article est organisé par fractale plutôt que par méthode. On va commencer par une présentation des différentes méthodes appliquées au tracé de la courbe de Von Koch.
On enchainera par les arbres et les fractals de Sierpiński.
Pour les fractales définies par des manipulations sur des surfaces, on commencera par proposer des méthodes « au trait » (des frontières) avant de présenter des méthodes « dessinant » des surfaces.
Tous les programmes joints sont à ouvrir avec TurboWarp, qui est une variante de Scratch proposant des options (nombre de clones infini) et des extensions (la palette Texte) dont on aura besoin pour certains programmes. Penser à activer l’option clones infinis si nécessaire.
I. La courbe de Von Koch
La courbe de Von Koch se trace facilement en utilisant un L-système. C’est l’occasion de présenter de quoi il s’agit.
Pour avoir un aperçu clair et concis des L-systèmes, on pourra consulter cette page.
Contrairement à une grammaire formelle où une seule variable est remplacée à chaque étape, dans un L-système toutes les variables sont substituées à chaque étape. (Il n’y a pas d’arbre de dérivation d’une chaîne de caractères, mais une suite de dérivation.)
1) L-système
Chaîne de départ : F
Règle : F → F-F++F-F
On pourrait tracer la courbe de von Koch de cette façon :
On va généraliser le concept de L-système en acceptant :
- de partir d’un mot (et pas seulement d’une lettre correspondant à Avancer) ;
- d’interpréter une lettre par un programme de géométrie de la tortue (et pas seulement une instruction) ;
- un caractère particulier k interprété de façon différente (voir triangle de Sierpiński).
Ici, si on part du mot AGAGAG on pourra tracer le flocon de Von Koch.
On peut proposer le programme suivant :
2) L-système stochastique
Cette partie (à déplier) est facultative et peut être jugée non pertinente.
Au risque de paraître ridicule, on va proposer une version volontairement non récursive de ce tracé par L-système.
On va ajouter la lettre B à l’alphabet pour signifier un déplacement sans laisser de trace.
Au lieu de l’unique règle de dérivation, on va en proposer cinq :
B → BBB
A → ADBGBDB
A → BDAGBDB
A → BDBGADB
A → BDBGBDA
Les quatre dernières sont en concurrence.
Pour programmer cette méthode, on va créer une liste branche pour stocker les différents choix possibles quand on applique une dérivation. branche contiendra des nombres entiers entre 1 et 4.
Le processus de tracé n’est pas récursif (même si le programme utilise un L-système qui est par essence récursif).
3) Méthode récursive : clonage et programmation à la naissance
Méthode :
On crée un clone.
Si le niveau maximal n’est pas dépassé chaque clone crée quatre nouveaux clones : un à chaque début de tronçon. Si le niveau max est atteint, le clone trace un trait.
Attention, il faut créer des variables locales pour le niveau courant et pour la longueur. Dans Scratch, il faut choisir l’option « pour ce sprite seulement » lors de la création de la variable.
4) Méthode récursive : fonction récursive
La fonction récursive, à chaque niveau de récursion, déplace la tortue pour qu’elle se retrouve à la même position et dans la même orientation que le bloc qu’elle remplace (ici un bloc avancer).
II. Arbres
Les arbres, c’est le domaine naturel des L-systèmes, qui ont été initialement conçus par le biologiste Aristid Lindenmayer pour modéliser le processus de développement organique des végétaux.
1) L-système
Considérons d’abord un exemple :
Chaîne de départ : F
Règles :
E → EE
F → E+[F]—[F]+E[F]
E correspond à un demi-déplacement.
Sur le schéma ci-dessus, les segments verts désigne les éléments de réplication.
On peut programmer ce L-système de la façon suivante :
2) Méthode récursive : clonage et programmation événementielle
On peut tracer le même arbre avec des clones. On va choisir cette fois une programmation événementielle pour les clones.
On peut considérer que cette méthode est plus simple à appliquer que celle par L-système.
L’événement « pousse ! » peut être omis.
Remarque : le bloc « envoyer à tous et attendre » bloque l’exécution du script dans lequel il se trouve tant que le script des blocs « quand je reçois message » correspondants n’est pas entièrement exécuté. Cela permet donc d’attendre que tous les scripts de réception du message soient terminés.
3) Méthode récursive : clonage et programmation à la naissance
Le sinon... peut être omis.
4) Méthode récursive : fonction récursive
III. Fractals de Sierpiński
Un peu d’histoire :
Sierpiński est un mathématicien polonais. Il a présenté les objets (qui porteront son nom et seront plus généralement appelés fractales) en 1915.
Le principe des fractals [1] de Sierpiński est le suivant : on part d’un objet qui contient des réductions de lui-même qui ne se chevauchent pas. A chaque étape, on évide la partie de l’objet qui ne fait pas partie des réductions. Et on recommence sur chaque réduction de l’objet. Le fractal est l’objet limite.
Pour le fractal pentagonal [2], on obtient les étapes suivantes :
Les figures de ce gif ont été obtenues avec CaRMetal.
Scratch ne permettant pas de colorier l’intérieur d’un polygone. Mais dans le cas particulier des fractales autosimilaires (avec un motif qui se répète strictement), on peut trouver des parades et on va en présenter deux : l’estampillage et le clonage.
A) Triangle de Sierpiński
On va commencer avec le triangle de Sierpiński avec en tête l’idée de la généraliser aux autres fractals de Sierpiński. La figure sera d’abord tracée au trait pour plus de simplicité.
La méthode intuitive que l’on va exposer ci-dessous présente des petits défauts de logique que l’on va relever plus tard puis corriger.
1) Méthode non récursive stochastique
Le hasard fait bien les choses.
Par commodité, on va utiliser les listes.
Dans le triangle de Sierpiński à l’étape n, chaque petit triangle peut être repéré par une liste de n nombres entiers entre 1 et 3.
Etape 1 :
Etape 2 :
Etape 3 :
On va construire un programme qui à partir d’une liste fixée de nombres entiers entre 1 et 3 trace le triangle correspondant à cette liste.
Pour tracer la figure, on pourra énumérer toutes les valeurs possibles de la liste.
La flèche indique la position et l’orientation initiale du lutin. On part d’une longueur de côté donnée, que l’on stocke dans une variable longueur.
A chaque étape :
Si on lit un 1, on ne bouge pas le lutin.
Si on lit un 2, on déplace le lutin en position 2.
Si on lit un 3, on déplace le lutin en position 3.
Dans les trois cas, on divise la longueur par 2.
On recommence jusqu’à atteindre la fin de la liste.
Quand on a atteint la fin de liste, on trace le triangle (de côté la valeur de la variable longueur).
Dans l’exemple ci-dessus on a pris l’exemple de tracé du triangle (3,2,1). On a tracé les triangles de petit niveau (indice) pour mettre en évidence le repérage.
Le programme suivant permet de tracer le triangle de de Sierpiński par méthode non récursive stochastique.
Cette méthode a un défaut de logique : le repérage des triangles ne respecte pas réellement le point de vue de la tortue. En vue d’une généralisation, il est important de le corriger.
Il est plus « logique » que la position d’un petit triangle soit dans un repérage relatif où le triangle (a,b,c) est le triangle en position c en partant de la position et de l’orientation de (a,b).
On obtient les versions améliorées des deux programmes précédents.
Tracé d’un triangle à partir de son code :
2) Méthode non récursive par générateur
La méthode de derrière le fagot
Comme on l’a vu plus haut, chaque pentagone correspond à une branche de la racine à une feuille d’un arbre.
On va implémenter un fagot avec toutes ces branches, et parcourir toutes les branches de ce fagot à l’aide d’un « générateur ».
Pour implémenter ce fagot, on va utiliser une liste.
Imaginons par exemple que l’on veuille construire un fagot pour le niveau 4.
Le fagot est l’ensemble $(a,b,c,d)$ avec $0 \leq a,b,c,d \leq 4$
Pour parcourir le fagot, on pourrait imaginer différentes stratégies.
On a choisi de programmer un petit sous-programme (un générateur) qui permet de passer d’une branche à la suivante suivant un ordre lexicographique.
On partira de (0,0,0,0), puis on augmentera le premier indice différent de 4, et on remettra à 0 tous les indices qui précèdent.
(0,0,0,0) → (1,0,0,0) → (4,0,0,0) → (0,1,0,0) → … (4,4,0,0) → (0,0,1,0) → …
Voici une implémentation possible de ce sous-programme (bloc) :
Pour que le processus de construction soit plus « continu » on va imaginer que l’élément 1 de cette liste branche est une feuille de l’arbre.
On peut alors proposer ce programme principal :
Remarque Python (à déplier)
Le module itertools de Python permet de faire un produit cartésien de générateurs.
En faisant un produit cartésien de générateurs range(), on peut obtenir un générateur du fagot.
On remarque que ce générateur n’itère pas de la même façon que celui que l’on a programmé plus haut. Il faudrait modifier légèrement le programme (pour l’utiliser avec le même rendu).
Pour obtenir le produit d’un nombre variable de générateurs range(), on pourrait faire de la métaprogrammation et utiliser la fonction exec(). Mais cette méthode ne serait pas recommandée.
Annexe : tracé avec des surfaces
Pour tracer le triangle de Sierpiński selon sa définition théorique (par évidement), il faut le faire avec des triangles remplis. On va proposer deux méthodes :
- en estampillant le lutin ;
- en clonant le lutin.
Dans les deux cas, on va utiliser un lutin ayant un costume de triangle. Ce lutin sera créé à partir d’une image de triangle au format vectoriel (en .svg).
Il existe deux types d’images :
- Les images au format bitmap (par exemple en .png ou en .jpg) sont des images « matricielles » (définies point par point). La qualité de ces images baisse quand on diminue et surtout quand on augmente leurs dimensions.
- Les images au format vectoriel (par exemple en .svg) sont des images définies par des équations mathématiques. La qualité de ces images ne subit pas de perte quand on diminue ou quand on augmente leurs dimensions.
Reprenons notre programme au trait.
Le plus grand triangle a un côté égal à 380 px.
On va créer un costume de lutin à partir d’une image de triangle ayant les mêmes dimensions.
Cette image est en p-j (triangleS.svg).
 |
Créer un nouveau lutin à partir de cette image.
Passer dans l’onglet costumes et déplacer le costume pour qu’il s’ajuste avec le grand triangle (attention : le nouveau lutin créé doit être en (-210,-160) ).
Copier-coller le script du lutin Beetle dans celui du lutin triangleS.
A partir de là, on va pouvoir appliquer chacune des deux méthodes.
1. Méthode par estampillage
Si on utilise ce lutin, au lieu du bloc triangleGauche (à la fin du script principal, l’autre bloc triangleGauche n’est pas utile), on pourra utiliser le bloc estampiller. Mais il faut veiller à avoir diminué la taille du lutin.
Créer une variable pourcentTaille.
Initialiser cette variable à 100 %.
Dans la boucle, à chaque fois que l’on augmente de 1 le niveau, quand on change la longueur et l’indice on divisera aussi par 2 la variable pourcentTaille.
Avant d’estampiller, on met la taille à pourcentTaille % de la taille initiale.
On obtient un petit triangle plein à la bonne position.
Il n’y a plus qu’à finir (tracer tous les petits triangles).
2. Méthode par clonage
Cela fait basculer à des méthodes récursives par clonage.
On va présenter deux méthodes.
a) une méthode utilisant un programme à la naissance et des variables locales ;
b) une méthode utilisant un échange de messages (la programmation événementielle).
Remarque : ces méthodes utilisent des particularités de Scratch. Appliquer ces méthodes (ou leur esprit) en Python serait nettement plus difficile.
3) Méthode récursive par clonage et programmation à la naissance
L’idée est de créer un clone du lutin pour chaque petit triangle. A chaque nouveau niveau, chaque clone donne naissance à 3 clones. Et on obtient directement (!) tous les triangles.
On va commencer par déplacer le lutin comme précédemment, puis on va le cloner à chacune des trois positions (1, 2 et 3) décrites plus haut.
Ensuite, pour chaque clone on fera... la même chose.
Les variables longueur, indice (ou niveau) et pourcentTaille doivent cette fois être propres à chaque lutin, autrement dit locales.
On crée donc trois variables qui vont jouer le même rôle que les variables précédentes du même nom (qui étaient globales), mais « pour ce sprite (lutin) uniquement » .
Le programme va commencer à peu près ainsi :
Mais avec les positions « améliorées » 1, 2, 3 les blocs « aller de 1 à 2 » et « aller de 2 à 3 » sont identiques.
Par ailleurs il y a du code répété.
Après quelques retouches on peut proposer le programme suivant.
Remarque : au niveau 5, on atteint le nombre limite de clones dans Scratch (300 clones maximum).
On n’aurait pas le problème si on travaillait avec TurboWarp avec l’option clones infinis activée.
Dans une variante de ce programme, chaque clone pourrait se suicider une fois sa mission accomplie (plutôt que se cacher).
4) Méthode récursive par clonage et programmation par messages
Le bloc événementiel « quand je reçois le message... » permet de faire d’un lutin un agent dormant.
Quand le lutin reçoit le message, il exécute le script correspondant.
Le bloc « envoyer un message à tous et attendre » bloque l’exécution du script dans lequel il se trouve tant que le script des blocs « quand je reçois message... » correspondants n’est pas entièrement exécuté. Cela permet donc d’attendre que tous les scripts du réception de message soient terminés.
Le principe du programme sera le suivant :
Le lutin principale joue le rôle de chef d’orchestre.
A chaque changement de niveau il envoie un message de clonage en bonne position à tous les lutins (y compris à lui-même !), puis (quand c’est fait) un message de réduction et d’affichage si le niveau final est atteint.
Quand le lutin reçoit le message de clonage en bonne position, il crée les deux clones en bonne position et revient à sa position initiale avant de recevoir le deuxième message.
5) L-système
Chaîne de départ : T (comme triangle)
Règles :
T → TAGTAGTAG
A → AA
6) Méthode récursive : fonction récursive
Le sinon de la fonction récursive pourrait être enlevé dans cette version au trait. On obtiendrait ce script raccourci. :
B) Pentagone de Sierpiński
Le triangle de Sierpinski peut se généraliser au pentagone.
Contrairement à ce que l’on pourrait imaginer, la figure ci-dessus a été tracée « au trait ».
Remarque : un autre avantage de TurboWarp est de pouvoir modifier la taille de la fenêtre graphique. Cela permet de tracer des figures de plus grandes dimensions.
On considère qu’à l’étape 0, on a un seul pentagone, à l’étape 1 on a 5 pentagones, etc.
Il faut préalablement déterminer le rapport d’agrandissement/réduction.
Considérons le schéma suivant :
On peut démontrer que le rapport de réduction est $\dfrac{1}{2(1+cos(72°))}= \dfrac{1}{\phi^2}$, où $\phi$ est le nombre d’or.
Méthode générale :
A l’étape 0, on construit un seul pentagone « main gauche » (on est en géométrie de la tortue). L’étape suivante consiste à remplacer cette construction par la construction de cinq pentagones « main gauche » positionnés selon le schéma ci-dessous (comme pour le triangle).
Et ainsi de suite.
On peut écrire des programmes analogues à ceux du triangle.
1) Méthode non récursive stochastique
Remarque : calcul de probabilités
A l’étape 2, on a 25 pentagones à construire. Chaque pentagone correspond à une branche de la racine à une feuille de cet arbre :
Pour construire les 25 pentagones, on peut construire un de ces pentagones au hasard. Puis recommencer jusqu’à obtenir les 25 pentagones.
Si on reproduit $n$ fois cette construction aléatoire, la probabilité de ne pas obtenir un pentagone particulier est $(\dfrac{24}{25})^n$.
La probabilité qu’il manque un pentagone est donc $25 \times (\dfrac{24}{25})^n$.
Pour que cette probabilité soit inférieure à $p$, il faut que $n$ vérifie
$25 \times (\dfrac{24}{25})^n < p$
En passant au logarithme, on obtient $n >\dfrac{ln(p) - ln(25)}{ln(\dfrac{24}{25})}$
Pour $p=\dfrac{1}{2}$, on obtient $n \geq 96$.
Pour $p=\dfrac{1}{10}$, on obtient $n \geq 153$.
On peut généraliser ces calculs.
2) Méthode non récursive par générateur
3) Méthode récursive par clonage et programmation à la naissance
 |
Première version animée :
Le rendu est un peu étrange…
On peut programmer une animation plus conventionnelle (et meilleure).
4) Méthode récursive par clonage et programmation par messages
Là encore, on peut proposer une version animée.
5) L-systèmes
Pour le triangle, on avait ce L-système :
Chaîne de départ : $T$ (comme triangle)
Règles :
$T → TAGTAGTAG$
$A → AA$
On est amené à généraliser ainsi :
Chaîne de départ : $P$
Règles :
$P → PAGPAGPAGPAGPAGPAG$
$A → kA$
Et il faut alors que la chaîne $k^nA$ soit interprétée par Avancer ($k^n \times$ longueur)
On va donc généraliser le concept de L-système en acceptant :
- de partir d’un mot (et pas seulement d’une lettre correspondant à Avancer) ;
- d’interpréter une lettre par un programme de géométrie de la tortue (et pas seulement une instruction) ;
- un caractère particulier $k$ dont l’interprétation est différée et conjuguée (par multiplication) à la première lettre $A$ à sa droite.
6) Méthode récursive : fonction récursive
IV. La courbe en pointe de flèche de Sierpiński
Le triangle de Sierpiński peut aussi être défini comme limite d’une suite de courbes plutôt que de surfaces. Ces courbes portent le nom de courbe(s) en pointe de flèche de Sierpiński.
Le schéma des positions est le suivant :
On peut appliquer les différentes méthodes :
1) L-système
a) Première idée
Conformément à la méthode que l’on a présentée on peut proposer ce L-système :
Axiome : A
Règles :
B → BB
A → DBABGAGBABD
(B est un déplacement en arrière sans laisser de trace). G et D sont des rotation de 120°.
On peut considérer que cette méthode comporte un défaut : la courbe n’est pas tracée dans le bon ordre (de façon « continue »).
b) Une deuxième lettre pour Avancer
On va ajouter une nouvelle lettre pour le déplacement « main droite ». On va prendre F (pour Forward, qui est la version anglaise d’Avancer).
Axiome : A
Règles :
A → GFDADFG
F → DAGFGAD (version inversée)
On n’a plus besoin de la lettre B. Les rotations sont maintenant d’angle 60°.
Pour implémenter le remplacement des deux lettres on a besoin d’une sorte de fonction replace (de la palette Texte de TurboWarp) mais pouvant prendre en compte plusieurs règles.
On peut implémenter cette fonction en Scratch, ce qui permettra de présenter le fichier sur un studio Scratch.
2) Clonage
a) Méthode 1
On a le même problème que précédemment, même si on ne le voit pas.
Mais on peut le mettre en évidence en insérant quelques pauses dans le programme.
b) Méthode 2
Pour régler ce problème on peut utiliser une variable locale qui va jouer le rôle de drapeau.
Cela permet de cloner le lutin dans un état ou dans un autre.
En mettant les mêmes pauses que précédemment, on obtient cette animation :
C’est mieux (différent), mais ce n’est toujours pas ça…
Pour obtenir l’effet voulu, il faut un peu batailler sur le délai d’affichage de chaque clone.
3) Fonction récursive
La problématique ne change pas.
a) Méthode 1
b) Méthode 2 (avec drapeau)
V. Compléments
On pourrait mettre en œuvre les mêmes méthodes pour tracer la fractale de Pythagore. Cet exercice est laissé au lecteur.