Accueil » Publications » Le Bulletin Vert » Dans nos classes » Algorithmique et programmation (...)
  APMEP   Algorithmique et programmation graphique des fractales de Sierpinski

Article du bulletin 497

Adhérer ou faire un don

Angela Gammella-Mathieu [1] & Nicolas Mathieu [2]

Introduction

Depuis leur invention en 1975 par Benoît Mandelbrot, les fractales font l’objet de nombreuses études. Leur utilisation dans l’enseignement présente de nombreux avantages : elle peut se faire à tous les niveaux du collège, du lycée voire de l’université, elle permet comme l’expliquent les auteurs de [LW] de faire des liens entre différentes parties des mathématiques, de donner des exemples concrets d’application des mathématiques dans le monde extérieur, de susciter l’intérêt des élèves par la beauté et la complexité des figures fractales. Ces avantages ont été exploités plusieurs fois dans la littérature comme en témoignent plusieurs articles pédagogiques ([BAFP], [Ga], [GG] par exemple). Dans ce travail, nous avons cherché à les utiliser afin d’enseigner l’algorithmique au lycée. Nous présentons des activités qui allient géométrie et informatique, et qui sont basées sur les fractales de Sierpinski. Ces activités sont en conformité avec les programmes de mathématiques d’autant plus que ces derniers introduisent depuis la réforme de 2009 l’algorithmique dès la classe de seconde. Après avoir présenté et défini les fractales de Sierpinski, nous précisons les prérequis et les modalités des activités proposées. Nous élaborons des algorithmes permettant la construction du triangle de Sierpinski. Nous expliquons et employons la méthode récursive très simple à implémenter et bien adaptée à la géométrie fractale. Nous choisissons de traduire nos algorithmes en Python, mais en réalité les programmes obtenus sont facilement adaptables à tout langage de programmation admettant la récursivité. Enfin, nous finissons par des activités classiques sur un tableur de type Excel conduisant au calcul du périmètre et de l’aire des fractales.

I. Présentation des fractales de Sierpinski

1. Un peu d’histoire

Les fractales sont des objets géométriques complexes qui permettent notamment de désigner des formes qui existent depuis toujours dans la nature (chou romanesco, alvéoles pulmonaires, côtes bretonnes, flocons de neige). Le mot « fractale » a été créé par Benoît Mandelbrot [Ma] à partir de la racine latine « fractus » signifiant à la fois irrégulier et brisé. Suite aux travaux de Mandelbrot et grâce au développement de l’informatique, on a assisté dans les années quatre-vingt à l’émergence d’une nouvelle branche des mathématiques : la géométrie fractale.
Plusieurs mathématiciens précurseurs ont contribué à la naissance de la géométrie fractale :

  • En 1500, le graveur et géomètre Albrecht Dürer invente la première figure fractale connue sous le nom de pentagone de Dürer. _ Il s’agit de placer dans un pentagone six pentagones adjacents en laissant de côté le pentagone central et en recommençant le partage pour les pentagones restants.
  • Vers 1700, Leibniz introduit et étudie la propriété d’autosimilarité. Cette propriété est l’une des plus importantes propriétés théoriques des objets fractals.
  • En 1904, Von Koch propose une courbe désormais connue sous le nom de flocon de Von Koch. Cette courbe a permis d’établir l’existence de fonctions continues mais non dérivables en tout point, fonctions pathologiques, considérées d’abord comme des monstres mathématiques et qui se sont avérées utiles pour définir de manière rigoureuse les règles du calcul infinitésimal.
  • En 1915, le mathématicien polonais Sierpinski introduit le triangle qui porte désormais son nom et que l’on va définir plus bas.
  • En 1925, apparaît la première représentation graphique d’un ensemble de Julia. Rappelons que les ensembles de Julia sont des sous-ensembles du plan complexe associés à des suites complexes $(z_n)$ satisfaisant une relation de récurrence de la forme

    $$z_{n+1}=z_n^2+c$$

    Abandonnés pendant de nombreuses années, les travaux de Julia ont été remis à l’honneur essentiellement grâce à Benoît Mandelbrot puis à Adrien Douady. Ce dernier a notamment établi les propriétés fondamentales de l’ensemble de Mandelbrot qu’il a lui-même défini et baptisé, et qui est une mine de problèmes ouverts difficiles.
  • D’autres mathématiciens ont donné leur nom à des fractales (on peut citer Peano, Cantor, Hilbert).

Notons que les fractales ont de nombreuses applications au sein des mathématiques et également dans des domaines aussi variés que la biologie, la physique, l’astrophysique, la géophysique, l’étude des phénomènes naturels, l’industrie, les finances, l’art (voir aussi [Ta]). Enfin, elles interviennent dans la théorie du chaos qui présente elle-même de nombreuses applications en chimie et en mécanique des fluides.

2. Le triangle de Sierpinski

Il est défini de la manière suivante : on part d’un triangle équilatéral que l’on partage en quatre triangles équilatéraux et dont on enlève le triangle central. On recommence l’opération pour les triangles restants et ainsi de suite. Les figures ci-dessous donnent le rang 0 et les trois premières étapes :

II. Prérequis, objectifs et modalités

Les activités que l’on propose dans cet article sont conçues pour des élèves de premières ou de terminales scientifiques, elles peuvent cependant être en partie adaptées dès la seconde. Elles nécessitent une durée de cinq à six heures ainsi que la maîtrise de plusieurs prérequis dont on fait la liste ci-dessous. On peut demander aux élèves de faire au préalable une recherche documentaire sur les fractales. Il serait bon de prévoir au moins un PC par groupe de deux élèves. Le suivi et l’évaluation de leur production peuvent se faire sous différentes formes (un compte-rendu oral peut être envisagé).

1. Prérequis mathématiques

  • Maîtrise du programme de géométrie de collège (hauteur d’un triangle équilatéral, détermination d’aires et de périmètres, … ).
  • Suites définies par récurrence.
  • Définition et propriétés des suites géométriques.
  • Calcul des premiers termes d’une suite géométrique et utilisation du signe somme S.
  • Sens de variation et limite d’une suite.

2. Prérequis informatiques

  • B2I (pour la manipulation des fichiers).
  • Les variables.
  • Construction d’un algorithme simple.
  • Des notions sur les procédures et les fonctions.
  • Les tests.
  • Les boucles.
  • Quelques explications (avec exemples) sur les algorithmes itératifs et récursifs.
  • Quelques rudiments en Python.
  • Affichage graphique.
  • Utilisation basique d’un tableur de type Excel.

3. Les objectifs

  • Pratiquer une activité algorithmique.
  • Modéliser un problème géométrique comme celui de la construction de fractales.
  • Faire un travail d’abstraction pour comprendre une propriété de récurrence et un algorithme récursif.
  • S’initier à l’écriture de programmes informatiques.
  • Habituer les élèves à la rigueur et à la pratique systématique de la vérification et du contrôle en les confrontant à des langages de programmation tels que Python.
  • Utiliser un tableur pour émettre des conjectures sur des suites.
  • Démontrer les conjectures.

4. Le langage de programmation utilisé

Le logiciel Python semble être bien adapté pour pratiquer l’algorithmique en classes de lycée. Il s’agit d’un logiciel gratuit qui possède de nombreuses fonctions mathématiques et plusieurs applications graphiques. La syntaxe de Python est réputée simple, elle conduit en général à des programmes à la fois compacts et lisibles. De nombreuses bibliothèques informatiques ont été développées pour Python. Dans cet article, on utilise Pygame qui est une bibliothèque gratuite et simple d’emploi. Elle permet entre autres d’afficher en une instruction un polygone. Il est à noter qu’en Pygame l’origine du repère dans la fenêtre graphique est fixée en haut à gauche. À signaler que chaque programme commence par des procédures d’initialisation graphique et se termine par une boucle infinie dont il n’est pas utile d’expliquer la syntaxe aux élèves : on peut se contenter de leur dire que tout programme informatique commence par initialiser certains paramètres comme la largeur et la hauteur de la fenêtre dans laquelle il travaille. Pour le reste, les élèves intéressés pourront consulter le site de la Pygame [Py] qui contient toutes les explications et les tutoriaux nécessaires à l’approfondissement de la question. On pourra de plus se référer à [RD].

III. Présentation des algorithmes et des programmes

Les algorithmes que nous allons considérer vont permettre de construire les étapes menant à une fractale jusqu’à un certain rang n arbitraire. On peut distinguer deux types d’algorithmes : les algorithmes itératifs et les algorithmes récursifs. Soyons plus précis.

  • Dans la démarche itérative, on passe de l’étape 1 à l’étape n à l’aide d’une boucle « pour » ; c’est-à-dire que l’on part de l’étape 1 (connue), on passe de 1 à 2, puis de 2 à 3, …, de $n - 1$ à n, on s’arrête à l’étape n souhaitée.
  • Dans la démarche récursive, on part de l’étape n (inconnue). Cette étape n’est pas connue, mais on la décrit en fonction de l’étape $n-1$, qui elle-même est décrite en fonction de l’étape $n - 2$ et ainsi de suite jusqu’à arriver à l’étape 1 connue.
    On parvient au résultat voulu en écrivant un algorithme qui s’appelle lui-même.

Dans la suite, nous allons appliquer la démarche récursive car c’est la méthode la plus pratique à utiliser pour construire les fractales de Sierpinski.

Construction du triangle de Sierpinski

On part donc d’un triangle équilatéral coloré (non blanc) de côté 1. En joignant les milieux des côtés, on obtient un triangle équilatéral central que l’on met en blanc et des triangles équilatéraux colorés. On répète l’opération pour les triangles colorés. On réitère le procédé un nombre n arbitraire de fois. Décrivons la méthode récursive pour le triangle de Sierpinski. L’idée est de dire qu’un triangle de Sierpinski au rang n n’est autre que la réunion de trois triangles de Sierpinski au rang $n - 1$. Les coordonnées des sommets des triangles sont bien-sûr différentes, il faudra donc mettre en données les coordonnées des sommets du triangle « père », puis déterminer les coordonnées des sommets des triangles « fils ».
Plus précisément, l’algorithme va partager un triangle ABC (voir la figure ci-dessus) dont les sommets ont pour coordonnées $A(x_A,y_A), B(x_B,y_B), C(x_C,y_C)$, en quatre triangles : AEG, EBF, GFC et le triangle central EFG où E désigne le milieu de [AB], F le milieu de [BC] et G le milieu de [AC]. Voici cet algorithme :
Algorithme récursif pour le triangle de Sierpinski : La construction peut alors être mise en œuvre : on commence par l’initialisation en traçant le premier triangle coloré, puis on fait appel à l’algorithme précédent.

Traduction en Python avec les commentaires intégrés :

Remarques :

  • Il est possible d’écrire quelques variantes du programme proposé. On peut par exemple partir d’un triangle quelconque. On peut incorporer dans le triangle central un cercle inscrit ou un autre dessin. On peut utiliser plusieurs couleurs, modifier les contours des polygones, … On peut même demander aux élèves d’imaginer et de programmer leur propre variante.
  • On peut généraliser la construction de Sierpinski à tout polygone régulier à p côtés. Pour p = 4, on obtient le carré (ou tapis) de Sierpinski. Pour p = 5, on retrouve le pentagone de Dürer. Pour p = 6, la figure obtenue s’appelle l’hexagone (ou napperon) de Von Koch car la partie centrale est un flocon de Von Koch. Bien entendu, même si le principe reste le même, les programmes correspondants sont beaucoup plus difficiles à écrire (dès que p ≥ 5).
  • En classe de terminale scientifique, on peut demander aux élèves d’utiliser les complexes pour programmer les fractales de Sierpinski.
  • Dans cette section, on a pu se rendre compte du fait que les algorithmes récursifs sont bien adaptés à la construction des fractales et permettent de bien saisir la propriété d’autosimilarité des objets fractals. En réalité, ces algorithmes nécessitent au départ un effort d’abstraction notable mais se révèlent a posteriori moins laborieux à écrire que les algorithmes itératifs.
  • Pour une réflexion sur l’enseignement de l’algorithmique, le lecteur pourra se reporter à [Ap].

IV. Calcul des périmètres et des aires des fractales avec Excel

Énoncé possible : Le triangle de départ est un triangle équilatéral coloré (non blanc) de côté 1. En joignant les milieux des côtés, on partage le triangle en quatre triangles dont un triangle blanc au centre et trois autres triangles colorés pour lesquels on répète l’opération. On réitère le processus un certain nombre de fois. On note $p_n$ le périmètre de la surface blanche à l’étape n et $a_n$ l’aire de la surface blanche à l’étape n.

a) Créer un fichier Excel comprenant 20 lignes et 7 colonnes avec

  • en colonne 1 : le numéro n de l’étape ;
  • en colonne 2 : la longueur du côté d’un triangle blanc rajouté à l’étape n ;
  • en colonne 3 : le nombre de triangles blancs rajoutés à l’étape n ;
  • en colonne 4 : le périmètre d’un triangle blanc rajouté à l’étape n ;
  • en colonne 5 : le périmètre $p_n$ de la surface blanche à l’étape n  ;
  • en colonne 6 : l’aire d’un triangle blanc rajouté à l’étape n ;
  • en colonne 7 : l’aire $a_n$ de la surface blanche à l’étape n.

b) À l’aide du fichier Excel construit, conjecturer le sens de variation et la limite éventuelle des suites (p_n) et (a_n) .

c) Montrer que pour tout entier naturel n non nul, on a : $p_n=p_{n-1}+3\times \left( \frac{1}{2}\right)^n \times 3^{n-1}$ et $a_n=a_{n-1}+\frac{\sqrt 3}{4} \times \left( \frac{1}{4}\right)^n \times 3^{n-1}$ et déterminer le sens de variation et la limite des suites $(p_n)$ et $(a_n)$.

d) Conclure.

Réponse attendue (succincte) : Pour construire le fichier Excel, on entre les formules suivantes. Pour la première colonne : $A_1= 1$, puis $A_2= A_1+ 1$. Pour la colonne B, on fait $B_1=\frac{1}{2}$, puis $B_2=\frac{1}{2}\times B_1$. Pour la colonne C, on a $C_1=1$, puis $C_2= 3 \times C_1$. Pour la colonne D, on a $D_1= 3 \times B_1$. Pour la colonne E, on a $E_1= D_1$ , puis $E_2= E_1+ D_2 \times C_2$. Enfin pour la colonne F, on a $F_1=\frac{\sqrt 3}{4} \times B_1^2$ et pour la colonne G, on fait $G_1= F_1$, puis $G_2=G_1+ F_2 \times C_2$. On complète le tableau en utilisant les fonctionnalités du logiciel Excel. On obtient alors : On peut conjecturer que la suite $(p_n)$ croît et tend vers $+\infty$ alors que la suite $(a_n)$ croît vers une limite finie. On comprend aussi qu’à l’étape n, on a rajouté des triangles de côté deux fois plus petit que ceux de l’étape $ n - 1$. Le nombre de triangles blancs rajoutés à l’étape n est $3^{n-1}$. Le périmètre supplémentaire à l’étape n est donc $3\times \left( \frac{1}{2}\right)^n \times 3^{n-1}$ et l’aire supplémentaire à l’étape n est $\frac{\sqrt 3}{4} \times \left( \frac{1}{4}\right)^n \times 3^{n-1}$ . Il s’ensuit que pour tout n ≥ 1, on a

$$p_n=p_{n-1}+3\times \left( \frac{1}{2}\right)^n \times 3^{n-1}$$

et

$$a_n=a_{n-1}+\frac{\sqrt 3}{4} \times \left( \frac{1}{4}\right)^n \times 3^{n-1}.$$

Par conséquent pour tout n ≥ 1,

$$p_n=\sum_{i=1}^n 3\times \left( \frac{1}{2}\right)^i \times 3^{i-1} = \frac{3}{2}\times \sum_{i=0}^{n-1} \left( \frac{3}{2} \right)^i=\frac{3}{2} \frac{1- \left( \frac{3}{2} \right)^n}{1-\frac{3}{2}}=3 \left( \left (\frac{3}{2} \right)^n-1 \right)$$

Comme $\frac{3}{2}>1$, $\lim_{n \to +\infty} p_n=+\infty$, D’autre part,

$$a_n=\sum_{i=1}^n \frac{\sqrt 3}{4}\times \left( \frac{1}{4}\right)^i \times 3^{i-1} = \frac{\sqrt 3}{16}\times \sum_{i=0}^{n-1} \left( \frac{3}{4} \right)^i=\frac{\sqrt 3}{16} \frac{1- \left( \frac{3}{4} \right)^n}{1-\frac{3}{4}}=\frac{\sqrt 3}{4} \left( 1-\left (\frac{3}{4} \right)^n-1 \right)$$

d’où comme $\frac{3}{4}<1$, on a $\lim_{n \to \infty} \left (\frac{3}{4} \right)^n = 0$ donc $\lim_{n \to +\infty} a_n=\frac{\sqrt 3}{4}$. On conclut que le périmètre du triangle de Sierpinski, qui n’est autre que le périmètre de la surface blanche auquel on additionne le périmètre du triangle initial (c’est-à-dire 3), est infini puisque $ \lim_{n \to +\infty} p_n=+\infty$. En revanche son aire, qui n’est autre que l’aire du triangle initial (à savoir $\frac{\sqrt 3}{4}$) à laquelle on soustrait l’aire de la surface blanche, est nulle puisque $ \lim_{n \to +\infty} a_n=\frac{\sqrt 3}{4}$.

Bibliographie

[Ap] Algorithmique I et II, Bulletin de l’APMEP, n°486 et n°487 (2010).
[BAFP] X. Buff, J.L. Aced, C. Ferrero, D. Pallec, Article publié dans le fil d’Ariane 13 bis, Une collaboration entre le collège de Lalande et l’Université Paul Sabatier à Toulouse, IREM de Toulouse (2003).
[Ga] D. Gardes, Travaux personnels encadrés. La dimension fractale, Feuille de Vigne 83, p.11-43, IREM de Dijon (2002), publié aussi dans le Bulletin de l’APMEP n°440 (2002).
[GG] D. Gaud, J. Guichard, Les fractales : objet interdisciplinaire mathématiques-philosophie, Bulletin de l’APMEP n°424 (1999).
[LW] R. Lornell, J. Westerberg, Fractals in High School : Exploring a new geometry, The Mathematics Teacher 92 (1999).
[Py] http://pygame.org/news.html
[Ma] B. Mandelbrot, Les objets fractals, Flammarion, 4ième édition (1995).
[RD] G.Van Rossum, F.L. Drake Jr, An introduction to Python, revised and update for Python 3.2, published by Network theory LTD (2011).
[Ta] Tangente, Les fractales, Art, Nature et Modélisation, Tangente Hors Série 8, Éditions Pôles (2004).

(Article mis en ligne par Armelle BOURGAIN)

[1] Professeur de mathématiques à l’IUT de Mesures Physiques de Metz, gammella@univ- metz.fr

[2] Professeur d’histoire-géographie au collège d’Homécourt, nicolas.mathieu@ac-nancy- metz.fr


 Accueil   Plan du site   Haut de la page   Page précédente