[Actualit�] Initiation au calcul formel avec Python
par
, 29/08/2023 � 16h50 (9579 Affichages)
I. Introduction
On souhaite dans notre cas utiliser le calcul symbolique pour d�velopper et r�duire des expressions math�matiques, et obtenir ainsi des polyn�mes � une ou plusieurs variables. Ce processus va nous permettre ensuite de v�rifier si deux expressions sont �gales.Envoy� par Wikipedia
Pour cela, on va cr�er une classe Polynome dans laquelle on red�finira les op�rateurs d'addition, de multiplication et de puissance pour ces nouveaux objets.
II. Principe du calcul formel
Comment v�rifier par exemple que l'identit� (a + b)2 = a2 + b2 + 2(a∗b) est correcte ?
Une v�rification na�ve pourrait consister � examiner toutes les valeurs possibles de a, � les croiser avec toutes les valeurs possibles de b et, pour chaque couple, � calculer (a + b)2, puis a2 + b2 + 2(a∗b) et � s'assurer que l'on obtient le m�me r�sultat. Si les domaines de a et de b sont grands, cette v�rification peut �tre tr�s longue, et si les domaines sont infinis (par exemple les r�els), elle ne peut pas �tre exhaustive.
En v�rification formelle, on utilise des variables symboliques et on applique les r�gles qui r�gissent le � + � et le � ∗ �. Ici, les r�gles pourraient �tre :
∀x, x2 = x∗x (R1)
∀x,y,z, x∗(y + z) = x∗y + x∗z (R2)
∀x,y, x∗y = y∗x (R3)
∀x, x + x = 2x (R4)
∀x,y, x + y = y + x (R5)
En se servant de ces r�gles, on peut ainsi d�velopper et r�duire progressivement l'expression (a + b)2 pour aboutir finalement � l'�galit� recherch�e :
(a + b)2 = (a + b)∗(a + b) (R1)
(a + b)2 = (a + b)∗a + (a + b)∗b (R2)
(a + b)2 = a∗(a + b) + b∗(a + b) (R3)
(a + b)2 = a∗a + a∗b + b∗a + b∗b (R2)
(a + b)2 = a2 + a∗b + b∗a + b2 (R1)
(a + b)2 = a2 + a∗b + a∗b + b2 (R3)
(a + b)2 = a2 + 2(a∗b) + b2 (R4)
(a + b)2 = a2 + b2 + 2(a∗b) (R5)
On obtient ainsi un polyn�me � 2 variables a et b.
Dans notre cas, on va donc d�terminer � l'aide des r�gles pr�c�dentes l'expression polynomiale de chacun des membres de l'identit� � v�rifier :
(a + b)2 = a2 + 2(a∗b) + b2
Et :
a2 + b2 + 2(a∗b) = a2 + 2(a∗b) + b2
Puis, on va comparer les polyn�mes obtenus pour v�rifier si l'identit� de d�part est vraie, un peu comme si on �valuait deux expressions num�riques pour savoir si elles sont �gales.
On remarquera �galement pour finir que ces expressions math�matiques peuvent �tre vues comme des combinaisons d'op�rations entre polyn�mes.
III. Impl�mentation en Python
Pour repr�senter ces polyn�mes en Python et pouvoir r�aliser des op�rations entre eux, il nous faut cr�er une classe Polynome :
Notre classe comportera en plus un constructeur, c'est � dire une m�thode particuli�re __init__() dont le code est ex�cut� quand la classe est instanci�e.
Elle va nous permettre de d�finir la liste de termes du polyn�me au moment de la cr�ation de l'objet :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Polynome: def __init__(self, termes): # méthode constructeur de la classe # on s'assure que l'argument termes est une liste if not isinstance(termes, list): termes = [termes] # parcours des indices et des termes de la liste for indice, terme in enumerate(termes): # si le terme est de type string : 'a' if isinstance(terme, str): # on met à jout l'élément de la liste avec un tuple de la forme (1,('a',)) : (coef, var) termes[indice] = (1,(terme,)) elif len(terme)==1: # ou si le terme est un tuple à un seul élément : ('a',) : (coef, var) termes[indice] = (1,terme) # regroupement des termes identiques en utilisant les règles R4 et R5 termes = regrouper_termes(termes) # on définit la liste de termes correspondant au polynôme. Ex. : [(1,('a','a')), (2,('a','b')), (1,('b','b'))] -> a^2 + 2ab + b^2 self.liste_termes = termes def __str__(self): # permet d'afficher l'expression sous sa forme développée et réduite # initialise la chaîne à renvoyer chaine_expression = '' ...
La m�thode __str__ permet d'afficher une expression sous la forme a^2 + 2*a*b + b^2. Le code de la fonction est disponible dans le module complet propos� � la fin du billet.
Pour tester ces m�thodes, nous ajoutons simplement deux lignes au module :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2 p = Polynome(['a','b']) # création de l'objet Polynome représentant l'expression (a+b) print(p) # affiche l'expression
Le code affiche :
a+b
III-A. Surcharge de l'op�rateur d'addition
Pour surcharger l'op�rateur � + � et pouvoir ainsi r�aliser l'addition entre 2 objets Polynome, nous devons ajouter une m�thode __add __ () � la classe :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Polynome: ... def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 objets Polynome : self + other # concaténation des 2 listes de termes # [(1,('a', 'a')), (1,('b',))] + [(1,('a', 'a')), (1,('b',))] = [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))] # tri et regroupement des termes identiques en utilisant les règles R4 et R5 : # R5 : a*a + b + a*a + b -> a*a + a*a + b + b (tri) # R4 : a*a + a*a + b + b -> 2*a*a + 2*b (regroupement) # [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))] -> [(2,('a','a')), (2,('b',))] # concaténation des 2 listes de termes de self et other liste_termes = self.liste_termes + other.liste_termes # renvoie l'objet Polynome résultat de l'addition de self et other avec regroupement des termes identiques return Polynome(liste_termes)
Cette m�thode permet donc de red�finir l'op�ration � + � pour des polyn�mes en utilisant les relations R4 et R5 :
(a + b) + (a + b) = (a + b + a + b)
(a + b) + (a + b) = (a + a + b + b) (R5)
(a + b) + (a + b) = 2a + 2b (R4)
Pour tester l'op�rateur d'addition portant sur 2 objets de la classe Polynome, nous ajoutons simplement ces lignes de code :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4 a = Polynome('a') # création du 1er objet de la classe Polynome représentant la variable a b = Polynome('b') # création du 2e objet de la classe Polynome représentant la variable b print((a+b)+(a+b)) # affiche l'expression (a+b)+(a+b) sous sa forme réduite
Le code affiche :
2*a + 2*b
III-B. Surcharge de l'op�rateur de multiplication
Pour surcharger l'op�rateur � * � et l'appliquer � 2 objets Polynome, nous devons �galement ajouter une m�thode __mul __ () � la classe :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 class Polynome: ... def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 objets Polynome : self * other # règles R2, R3, R4 et R5 # R2 : (a+b)*(a+b) = (a+b)*a + (a+b)*b # R3 : = a*(a+b) + b*(a+b) # R2 : = a*a + a*b + b*a + b*b # R3 = a*a + a*b + a*b + b*b # R4 : = a*a + 2*a*b + b*b # initialisation de la liste de termes liste_termes = [] # si le 2e membre est un numérique if isinstance(other, (int,float)): # on multiplie les coefficients des termes de self.liste_termes par other liste_termes = [(other*terme[0],terme[1]) for terme in self.liste_termes] return Polynome(liste_termes) # parcours des termes de la liste de other for terme_droite in other.liste_termes: # parcours des termes de la liste de self for terme_gauche in self.liste_termes: coef = terme_droite[0]*terme_gauche[0] var = terme_droite[1] + terme_gauche[1] # tri des variables var = tuple(sorted(var)) # ajout du tuple (coef,var) à la liste liste_termes.append((coef,var)) # renvoie l'objet Polynome résultat de la multiplication de self et other avec regroupement des termes identiques return Polynome(liste_termes)
Cette m�thode permet donc de red�finir l'op�ration de multiplication pour 2 polyn�mes en utilisant les r�gles R2, R3, R4 et R5 :
(a+b)∗(a+b) = (a+b)∗a + (a+b)∗b (R2)
(a+b)∗(a+b) = a∗(a+b) + b∗(a+b) (R3)
(a+b)∗(a+b) = a∗a + a∗b + b∗a + b∗b (R2)
(a+b)∗(a+b) = a∗a + a∗b + a∗b + b∗b (R3)
(a+b)∗(a+b) = a∗a + 2∗a∗b + b∗b (R4)
Pour tester l'op�rateur de multiplication portant sur 2 objets de la classe Polynome, nous ajoutons maintenant ces lignes :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4 a = Polynome('a') # création du 1er objet de la classe Polynome représentant la variable a b = Polynome('b') # création du 2e objet de la classe Polynome représentant la variable b print((a+b)*(a+b)) # affiche l'expression (a+b)*(a+b) sous sa forme développée et réduite
Le code affiche :
a^2 + 2*a*b + b^2
III-C. Surcharge de l'op�rateur de puissance
Maintenant que nous avons red�fini l'op�rateur de multiplication dans notre classe Polynome, nous pouvons ajouter une m�thode __pow__() qui va permettre d'obtenir le r�sultat d'un polyn�me �lev� � la puissance n.
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 class Polynome: ... def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 objets Polynome : self * other # règles R2, R3, R4 et R5 # R2 : (a+b)*(a+b) = (a+b)*a + (a+b)*b # R3 : = a*(a+b) + b*(a+b) # R2 : = a*a + a*b + b*a + b*b # R3 = a*a + a*b + a*b + b*b # R4 : = a*a + 2*a*b + b*b # initialisation de la liste de termes liste_termes = [] # si le 2e membre est un numérique if isinstance(other, (int,float)): # on multiplie les coefficients des termes de self.liste_termes par other liste_termes = [(other*terme[0],terme[1]) for terme in self.liste_termes] return Polynome(liste_termes) # parcours des termes de la liste de other for terme_droite in other.liste_termes: # parcours des termes de la liste de self for terme_gauche in self.liste_termes: coef = terme_droite[0]*terme_gauche[0] var = terme_droite[1] + terme_gauche[1] # tri des variables var = tuple(sorted(var)) # ajout du tuple (coef,var) à la liste liste_termes.append((coef,var)) # renvoie l'objet Polynome résultat de la multiplication de self et other avec regroupement des termes identiques return Polynome(liste_termes) def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n # on utilise pour cela la règles R1 : # R1 : ∀x, x^2 = x∗x # a^2 = a*a # a^3 = a*a*a #... # on initialise la variable objet p avec un polynôme égal à 1 p = Polynome((1,())) # on multiplie n fois p par self à l'aide de l'opérateur * for i in range(n): p = p*self # équivalent à : p = p.__mul__(self) # renvoie l'objet Polynome résultat de l'opération (self ** n) return p
Nous testons maintenant l'op�rateur pour (a + b) ** 2 :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4 a = Polynome('a') # création du 1er objet de la classe Polynome représentant la variable a b = Polynome('b') # création du 2e objet de la classe Polynome représentant la variable b print((a+b)**2) # affiche l'expression (a+b)^2 sous sa forme développée et réduite
Le code renvoie :
a^2 + 2*a*b + b^2
Tableau de quelques op�rateurs et de leur m�thode correspondante en Python :
Op�rateur Expression Interpr�tation Python Addition p1 + p2 p1.__add__(p2) Soustraction p1 - p2 p1.__sub__(p2) Multiplication p1 * p2 p1.__mul__(p2) Puissance p1 ** n p1.__pow__(n) Division p1 / p2 p1.__truediv__(e2) ... ... ...
III-D. Surcharge de l'op�rateur de comparaison � == �
Pour surcharger l'op�rateur � == � et pouvoir ainsi tester si 2 polyn�mes sont �gaux, nous ajoutons finalement une m�thode __eq__ () � notre classe :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4
5
6
7 class Polynome: ... def __eq__(self, other): # méthode permettant de redéfinir l'opérateur « == » pour 2 polynômes # renvoie True si les listes de termes des 2 polynômes sont égales return (self.liste_termes==other.liste_termes)
V�rifions pour terminer notre identit� de d�part :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 a = Polynome('a') # création d'un 1er objet représentant la variable a b = Polynome('b') # création d'un 2e objet représentant la variable b # création d'un objet Polynome à partir de l'expression (a+b)^2 p1 = (a+b)**2 # affiche l'expression de p1 print(p1) # création d'un objet Polynôme à partir de l'expression a^2 + b^2 + 2*a*b p2 = a**2 + b**2 + a*b*2 # affiche l'expression de p2 print(p2) # affiche le résultat de la comparaison p1=p2 print("p1=p2 ? : " + str(p1==p2))
Le code affiche :
p1=p2 ? : True
Tableau de quelques op�rateurs de comparaison et de leur m�thode correspondante en Python :
Op�rateur Expression Interpr�tation Python Inf�rieur � p1 < p2 p1.__lt__(p2) Inf�rieur ou �gal p1 <= p2 p1.__le__(p2) Egal p1 == p2 p1.__eq__(p2) ... ... ...
Si vous souhaitez avoir une liste plus compl�te des op�rateurs, je vous invite � consulter cette page.
IV. Module complet
On donne pour finir le code complet du module contenant la classe Polynome :
Code Python : S�lectionner tout - Visualiser dans une fen�tre � part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190 def regrouper_termes(liste_termes): # permet de regrouper les termes identiques dans une liste triée en utilisant les règles R4 et R5 : # R5 : a*a + b + a*a + b + c = a*a + a*a + b + b + c (tri) # R4 : a*a + a*a + b + b + c = 2*a*a + 2*b + c (regroupement) # [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',)), (1,('c',))] -> [(2,('a','a')), (2,('b',)), (1,('c',))] # créer une liste triée de variables ou de tuples uniques : [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',)), (1,('c',)] -> [('a','a'), ('b',), ('c',)] liste_vars = [t[1] for t in liste_termes] liste_vars_uniques = sorted(set(liste_vars)) # règle R5 # initialisation de la liste de termes à renvoyer liste_termes_groupes = [] # parcours les variables uniques de la liste for var in liste_vars_uniques: # compte le nombre de fois que la variable est présente dans la liste coef = sum([t[0] for t in liste_termes if t[1]==var]) # Règle R4 if coef!=0: # si le coef. n'est pas égal à 0 # ajout du tuple (coef,var) à la liste : liste_termes_groupes.append((2,('a',))) liste_termes_groupes.append((coef,var)) # renvoie de la liste des termes groupés return liste_termes_groupes class Polynome: def __init__(self, termes): # méthode constructeur de la classe # on s'assure que l'argument termes est une liste if not isinstance(termes, list): termes = [termes] # parcours des indices et des termes de la liste for indice, terme in enumerate(termes): # si le terme est de type string : 'a' if isinstance(terme, str): # on met à jout l'élément de la liste avec un tuple de la forme (1,('a',)) : (coef, var) termes[indice] = (1,(terme,)) elif len(terme)==1: # ou si le terme est un tuple à un seul élément : ('a',) : (coef, var) termes[indice] = (1,terme) # regroupement des termes identiques en utilisant les règles R4 et R5 termes = regrouper_termes(termes) # on définit la liste de termes correspondant au polynôme. Ex. : [(1,('a','a')), (2,('a','b')), (1,('b','b'))] -> a^2 + 2ab + b^2 self.liste_termes = termes def __str__(self): # permet d'afficher l'expression sous sa forme développée et réduite # initialise la chaîne à renvoyer chaine_expression = '' # si le polynôme est égal à un nombre : p=1 if (len(self.liste_termes)==1) and self.liste_termes[0][1]==(): return str(self.liste_termes[0][0]) # renvoie le nombre # parcours de la liste de termes du polynôme for terme in self.liste_termes: # création de la liste de variables uniques : ['a', 'b', 'c'] liste_vars = sorted(set(terme[1])) if liste_vars==[]: # si c'est un nombre chaine_terme=str(terme[0]) else: # sinon # si le coefficient du terme vaut 1 : (1,'a') if terme[0]==1: chaine_terme='' # on part d'une chaîne vide else: # sinon chaine_terme=str(terme[0]) + '*' # on part d'une chaîne contenant le coef. : '2*' # parcours des variables du terme : ('a','a','b') -> a*a*b = (a^2)*b for var in liste_vars: # évalue l'exposant de la variable : ('a','a','a') -> a^3 (R1) exp = len([v for v in terme[1] if v==var]) # si l'exposant vaut 1 if exp==1: chaine_terme += var + '*' else: # sinon chaine_terme += var + '^' + str(exp) + '*' chaine_terme = chaine_terme[:-1] chaine_expression += chaine_terme + " + " # renvoie la chaîne représentant l'expression du polynôme return chaine_expression[:-3] def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 objets Polynome : self + other # concaténation des 2 listes de termes # [(1,('a', 'a')), (1,('b',))] + [(1,('a', 'a')), (1,('b',))] = [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))] # tri et regroupement des termes identiques en utilisant les règles R4 et R5 : # R5 : a*a + b + a*a + b -> a*a + a*a + b + b (tri) # R4 : a*a + a*a + b + b -> 2*a*a + 2*b (regroupement) # [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))] -> [(2,('a','a')), (2,('b',))] # concaténation des 2 listes de termes de self et other liste_termes = self.liste_termes + other.liste_termes # renvoie l'objet Polynome résultat de l'addition de self et other avec regroupement des termes identiques return Polynome(liste_termes) def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 objets Polynome : self * other # règles R2, R3, R4 et R5 # R2 : (a+b)*(a+b) = (a+b)*a + (a+b)*b # R3 : = a*(a+b) + b*(a+b) # R2 : = a*a + a*b + b*a + b*b # R3 = a*a + a*b + a*b + b*b # R4 : = a*a + 2*a*b + b*b # initialisation de la liste de termes liste_termes = [] # si le 2e membre est un numérique if isinstance(other, (int,float)): # on multiplie les coefficients des termes de self.liste_termes par other liste_termes = [(other*terme[0],terme[1]) for terme in self.liste_termes] return Polynome(liste_termes) # parcours des termes de la liste de other for terme_droite in other.liste_termes: # parcours des termes de la liste de self for terme_gauche in self.liste_termes: coef = terme_droite[0]*terme_gauche[0] var = terme_droite[1] + terme_gauche[1] # tri des variables var = tuple(sorted(var)) # ajout du tuple (coef,var) à la liste liste_termes.append((coef,var)) # renvoie l'objet Polynome résultat de la multiplication de self et other avec regroupement des termes identiques return Polynome(liste_termes) def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n # on utilise pour cela la règles R1 : # R1 : ∀x, x^2 = x∗x # a^2 = a*a # a^3 = a*a*a #... # on initialise la variable objet p avec un polynôme égal à 1 p = Polynome((1,())) # on multiplie n fois p par self à l'aide de l'opérateur * for i in range(n): p = p*self # équivalent à : p = p.__mul__(self) # renvoie l'objet Polynome résultat de l'opération (self ** n) return p def __eq__(self, other): # méthode permettant de redéfinir l'opérateur « == » pour 2 polynômes # renvoie True si les listes de termes des 2 polynômes sont égales return (self.liste_termes==other.liste_termes) a = Polynome('a') # création d'un 1er objet représentant la variable a b = Polynome('b') # création d'un 2e objet représentant la variable b # création d'un objet Polynome à partir de l'expression (a+b)^2 p1 = (a+b)**2 # affiche l'expression de p1 print(p1) # création d'un objet Polynôme à partir de l'expression a^2 + b^2 + 2*a*b p2 = a**2 + b**2 + a*b*2 # affiche l'expression de p2 print(p2) # affiche le résultat de la comparaison p1=p2 print("p1=p2 ? : " + str(p1==p2))
A noter qu'il existe des biblioth�ques en Python sp�cialis�es dans le calcul formel, comme par exemple la librairie Sympy.
V. Conclusion
Ce billet nous aura donc permis de mieux comprendre l'int�r�t du calcul symbolique et comment le mettre en �uvre en Python.
Chacun pourra ensuite librement ajouter de nouvelles m�thodes � cette classe Polynome en utilisant de nouvelles r�gles math�matiques, pour par exemple red�finir les op�rateurs de soustraction ou de division entre deux polyn�mes.
Sources :
https://fr.wikipedia.org/wiki/Calcul_formel
https://en.wikipedia.org/wiki/Computer_algebra
https://fr.wikipedia.org/wiki/M%C3%A...(informatique)
https://fr.wikipedia.org/wiki/Polyn%C3%B4me
https://www.sympy.org/en/index.html
https://docs.python.org/fr/3/library/operator.html