-
Cours :
- Bases de données 1
- Bases de données 2
- Bases de données 3
- Bases de données 4
- Bases de données 5
- Programmation orientée objet
- cours 6
transparents : pdf, html - planche de TD/TP 6 (pdf)
- cours 6
- Programmation évènementielle
- Structures de données : listes, piles, files
- cours 8
transparents : pdf, html - planche de TD/TP 8 (pdf)
- cours 8
- Structures de données : arbres et ABR
- cours 9
transparents : pdf, html - planche de TD/TP 9 (pdf)
- cours 9
- Structures de données : graphes
- cours 10
transparents : pdf, html - planche de TD/TP 10 (pdf)
- cours 10
Paradigmes de programmation
On va travailler sur ce TP sur l’affichage de l’ensemble de Mandelbrot.
Classe Complex
Commencez par créer une classe pour stocker des complexes. Cette classe devra contenir les méthodes suivantes :
- un constructeur
__init__(self, real_part, imaginary_part)
qui initialise les parties réelles et imaginaire d’un complexe, - une méthode
square(self)
qui renvoie le carré du complexeself
, - une méthode
modulus(self)
qui renvoie le module du complexeself
, - une méthode
add(self, other_complex)
qui renvoie un nouveau complexe étant la somme deself
etother_complex
.
Classe RecursiveSequence
Vous allez créer une classe permettant de représenter des suites définies par récurrence.
Définition de la classe
Cette classe contient deux attributs :
current_value
: la valeur courante de la suite qui sera au départ la valeur initiale de la suite,recurrence_relation
: la fonction permettant de calculer le terme de rang \(n+1\) à partir du terme de rang \(n\).
Cela peut sembler étrange mais une fonction en Python est un objet comme un autre et peut donc être utilisé comme valeur d’une variable: on parle de programmation fonctionnelle.
Ajoutez une méthode next_value(self)
à cette classe, qui renvoie la valeur courante de la suite tout en mettant à jour cette valeur en appelant recurrence_relation
.
Lambda expression
Python offre une syntaxe intéressante qui permet de définir des mini-fonctions d’une ligne à la volée. La syntaxe utilise le mot-clé lambda
suivi des arguments de la fonction suivis de :
suivi de l’expression que doit retourner la fonction (qui peut alors utiliser les arguments). L’exemple ci-dessous illustre la définition de la même fonction de manière classique (f
) ou bien à l’aide d’une lambda
expression.
Cette syntaxe permet donc de définir des fonctions très rapidement, ce qui sera très utile pour créer des suites qui demande une fonction.
Test de la fonction et affichage de suite
Vous allez tester la classe que vous venez de créer en affichant les 100 premiers termes la suite \(u_n\) définie par :
\[ \left\{ \begin{array}{l} u_0 = 0\\ u_{n + 1} = u_n + 3\\ \end{array} \right. \]
Pour cela vous aller devoir utiliser pyplot
qui permet d’afficher des courbes. Il va vous falloir calculer deux listes X
et Y
contenant les valeurs des coordonnées des points que vous souhaitez afficher :
X
devra contenir les entiers de 0 à 99 inclusY
devra contenir les termes \(u_0, u_1 \dots, u_{99}\) de la suite.
Ensuite il vous suffit d’utiliser le code suivant pour afficher la suite :
Classe Mandelbrot
L’ensemble de Mandelbrot est une fractale définie comme l’ensemble des points \(c\) du plan complexe pour lesquels la suite de nombres complexes définie par récurrence ci-dessous est bornée :
\[ \left\{ \begin{array}{l} z_0 = 0\\ z_{n + 1} = z_n^2 + c\\ \end{array} \right. \]
Vous allez définir une classe Mandelbrot
afin de représenter les différentes suites de Mandelbrot (dépendant du paramètre \(c\)). Cette classe devra contenir les éléments suivants :
- un constructeur
__init__(self, complex_value)
qui initialise un attributsequence
contenant la suite (instance deRecursiveSequence
) de Mandelbrot définie par le complexecomplex_value
. - une méthode
diverging_value
qui calcule les termes de la suite jusqu’à ce que le module d’un terme soit supérieur à 2 ou bien qu’on ait calculé 50 termes. Cette fonction renverra le rang plus un du premier terme dont le module est supérieur à 2 ou bien 0 si aucun terme calculé n’avait un module supérieur à 2. On utilise cette méthode pour avoir un test efficace (bien qu’approché a priori) du caractère divergent de la suite de Mandelbrot.
Affichage de l’ensemble de Mandelbrot
Vous allez maintenant afficher l’ensemble de Mandelbrot grâce à la classe que vous venez de définir. Pour cela, on va définir les coordonnées des points que l’on souhaite afficher. On va utiliser une résolution de \(400\times 400\), des valeurs de \(x\) comprises entre \(-2\) et 0,5 et des valeurs de \(y\) comprises entre $-$1,25 et 1,25. On peut faire cela avec le code suivant (à l’aide du package numpy
) :
from numpy import linspace
xmin, xmax = -2.0, 0.5
ymin, ymax = -1.25, 1.25
nx, ny = 400, 400
X = linspace(xmin, xmax, nx)
Y = linspace(ymin, ymax, ny)
Maintenant, il vous suffit de calculer la valeur de diverging_value
pour chacun des complexes correspondant aux points \((x, y)\) avec \(x\in X\) et \(y\in Y\) et de stocker les valeurs dans une matrice. Pour calculer la matrice, nous vous conseillons d’écrire une fonction compute_line(y)
qui calcule la ligne \(y\) et la renvoie, puis une fonction compute_matrix()
qui calcule la matrice et la renvoie.
Vous pouvez ensuite afficher la matrice avec le code suivant :
from matplotlib import pyplot
pyplot.imshow(compute_matrix())
pyplot.show()
Vous devriez obtenir l’image suivante après le calcul :
Pour mesurer le temps de calcul, on peut utiliser la fonction perf_counter()
du module time
. Cette fonction retourne un flottant. La différence des valeurs retournées entre deux appels de la fonction est égale au temps écoulé entre les deux appels. Le code suivant permet donc de récupérer et d’afficher le temps écoulé par l’exécution d’un code :
import time
start = time.perf_counter()
# Code à exécuter
end = time.perf_counter()
print("Temps d'execution : " + str(end - start) + " secondes")
Utilisez cette technique pour mesurer le temps nécessaire pour dessiner la fractale de Mandelbrot.
Programmation parallèle
Essayons de diminuer ce temps total de calcul en dispersant le travail sur plusieurs processeurs en parallèle. Pour cela, on explore un peu plus les possibilités de la programmation fonctionnelle dans un premier temps : c’est l’un des atouts de ce paradigme, qui permet ensuite de paralléliser très aisément le travail.
Map
En python, il existe une fonction map
ayant deux argument et qui permet d’appliquer une fonction (premier argument) sur chacun des élément d’un objet iterable (deuxième argument qui peut être une liste) et de créer un itérateur (qu’on peut transformer en liste avec list()
) contenant chacun des retours de la fonction. Par exemple le code suivant, permet de calculer la liste \(Y\) des carrés des entiers de 0 à 99.
Réécrivez la fonction compute_matrix()
pour utiliser un map
de compute_line(y)
sur la liste Y
.
Multiprocessing
Il existe une variante de map
dans le packaqe multiprocessing
qui permet de paralléliser le calcul entre plusieurs processus et donc de profiter des multiples processeurs de votre ordinateur.
Le code suivant permet de distribuer le calcul du map
précédant avec deux processus et donc d’avoir un calcul potentiellement plus rapide.
from multiprocessing import Pool
pool = Pool(2) # nombre de processus en parallèle
X = list(range(100))
Y = list(pool.map(lambda x : x**2, X))
Changez le code de la fonction compute_matrix()
pour utiliser un pool
de 2 processus pour le map
. Qu’observez-vous sur le temps de calcul ?
On peut obtenir l’identifiant du processus en cours utilisant le package os
et la fonction os.getpid()
. Changez le code de la fonction compute_line
pour que la valeur dépende de l’identifiant du processus. On pourra utiliser par exemple (os.getpid() % 11) + 2
lorsque la valeur de diverging_value
est 0
et 1
sinon : cette formule un peu obscure permet de répartir les identifiants des processus, qui sont des entiers assez grands, sur une petite plage de valeurs, permettant d’obtenir une image plus esthétique.
Changez le code pour utiliser davantage de processus. Que remarquez-vous ? Vous pouvez obtenir le nombre de processeurs de votre ordinateur avec la méthode cpu_count()
de la bibliothèque multiprocessing
. Tracez puis commentez la courbe du temps de calcul de la fractale de Mandelbrot en fonction du nombre de processus utilisé.