L’ensemble de Julia est, pour un nombre complexe c donné, l’ensemble des points d’affixes \(z_0\) tels que la suite définie pour tout entier naturel n par \(z_{n+1}=z_n^2+c\) est bornée.
Selon les valeurs de c, on peut obtenir des ensembles plutôt jolis:
Pour les personnes abonnées à mathweb.fr, vous trouverez un code Python ainsi que les 10 images (sans marquage) sur cette page.
Pour la faire courte, l’ensemble de Mandelbrot est l’ensemble des points du plan complexe d’affixe c tels que la suite définie par \( \left\lbrace\begin{array}{l} z_0=0\\z_{n+1}=z_n^2+c\end{array}\right. \) est bornée.
Cet ensemble peut être construit à l’aide de Python, et de son module pygame. La vitesse à laquelle l’ensemble est construit est remarquable! Sur mon ordinateur (16 Mo RAM, sous Windows, processeur Intel Core i5), cela ne met pas plus de 10 secondes pour afficher ceci:
Avec une autre suite, j’ai obtenu:
Je vous l’accorde, elle est nettement moins esthétique que la première, mais je ne suis pas Julia, ni Fatou 🙂
Les abonné.e.s de mathweb.fr trouveront les codes Python de ces deux fractales sur cette page.
Je ne suis pas très fan du module turtle, car je préfère la programmation numérique, mais il faut bien avouer que ce module est pratique pour dessiner des schémas récursifs, comme les fractales.
Je me suis donc mis à la recherche d’un code donnant un tel schéma pour tenter de me familiariser avec le module. J’avais une idée bien précise : celle d’un arbre fractal, que j’avais vu quelque part.
Après quelques recherches, je suis enfin tombé sur le code suivant (que je me suis permis de commenter):
from turtle import *
angle = 30
color('#3f1905')
def arbre(n,longueur):
if n==0:
color('green')
forward(longueur) # avance
backward(longueur) # recule
color('#3f1905')
else:
width(n)
forward(longueur/3) #avance
left(angle) # tourne vers la gauche de angle degrés
arbre(n-1,longueur*2/3)
right(2*angle) # tourne vers la droite de angle degrés
arbre(n-1,longueur*2/3)
left(angle) # tourne vers la gauche de angle degrés
backward(longueur/3) # recule
hideturtle() # cache la tortue
up() # lève le stylo
right(90) # tourne de 90 degrés vers la droite
forward(300) # avance de 300 pixels
left(180) # fait un demi-tour
down() # pose le stylo
arbre(11,700) # exécute la macro
showturtle() # affiche la tortue
mainloop()
qui donne ceci:
Mais attention… Le dessin met un certain temps avant d’être fini (par exemple, sur mon ordinateur 16 Mo de RAM, processeur Intel Core i5, il met une vingtaine de minutes… arf !)
Si on modifie l’angle (disons pour le mettre à 50°), on obtient ceci:
Et avec un angle de 110° :
N’est-il pas choupinou ? 🙂
Vous pouvez remarquer dans le code la fonction récursive : c’est une notion que l’on verra en NSI (nouveau lycée)… mais prévue en cycle de maturité (en Terminale quoi !)… même si je n’ai pas pu résister à l’envie d’en mettre dans mon livre d’exercices corrigés qui sortira en version papier pour la rentrée 2019.
Une fonction récursive est une fonction qui fait appel à elle-même dans sa définition. On retrouve ce genre de fonction par exemple pour calculer le pgcd de deux nombres:
def pgcd(a,b):
if b==0:
return a
else:
r=a%b
return pgcd(b,r)
print(pgcd(56,42))
Ici, la récursivité s’appuie sur la propriété du pgcd qui stipule que:$$\text{pgcd}(a,b)=\text{pgcd}(b,r)$$où \(a = bq + r,\ 0\leq r < b\).
Les mathématiques sont donc très importantes pour construire des algorithmes (et par suite des programmes) performants. En effet, on aurait très bien pu calculer le pgcd de la manière suivante:
def pgcd(a,b):
while b<>0:
r=a%b
a,b=b,r
return a
print(pgcd(56,42))
Pour comparer deux algorithmes, on parle souvent de complexité. Cet article ne parle pas de cette notion, mais sachez tout de même que la complexité d’une fonction récursive est donnée par une suite arithmético-géométrique. Dans la fonction pgcd, il y a 2 instructions élémentaires (le test sur b et l’affectation de r). La complexité \(C_n\) est donc égale à \(2+C_{n-1}\), où \(C_{n-1}\) est celle de la fonction pgcd(b,r). On démontre alors que la complexité de la fonction récursive est de l’ordre de O(n) [complexité linéaire]. En fait, la complexité est linaire dans le pire des cas (quand a et b sont deux nombres successifs de la suite de Fibonacci), car dans les autres cas, la complexité est logarithmique [O(ln(n))].
L’évaluation moyenne de la complexité de l’algorithme d’Euclide version récursive est assez compliquée. Le nombre d’appels moyen de la fonction pgcd est:$$\frac{12\ln(2\ln n)}{\pi^2}+1,47.$$
http://imss-www.upmf-grenoble.fr/prevert/Prog/Complexite/euclide.html
La complexité de l’algorithme non récursif est quasi-identique à sa version récursive.
https://www.labri.fr/perso/betrema/deug/poly/euclide.html
La version récursive de l’algorithme d’Euclide est peut-être un peu plus facile à écrire que la version itérative. Les deux versions ont fondamentalement la même complexité, avec un petit avantage à la version itérative, car l’appel d’une fonction n’est pas gratuit.
Mais là, je m’égare… Saint-Lazare !