User

I. Introduction

On souhaite montrer comment utiliser le principe du « diviser pour régner » afin de développer un produit de petits polynômes avec un minimum d'opérations de multiplication entre termes.

Pour cela, on va d'abord décrire cette méthode à l'aide d'un exemple simple de multiplication de nombre entiers, puis de petits polynômes, pour ensuite l'implémenter en Python.


II. Principe du « diviser pour régner »

Une multiplication entre deux nombres entiers nécessite de multiplier chaque chiffre du multiplicateur par chaque chiffre du multiplicande.

Si ces deux nombres ont n chiffres, cela exige n² produits. La multiplication 10*10 nécessite ainsi 4 multiplications de chiffre.

On dit que le calcul a une complexité en temps quadratique, ou en O(n²).

Si on prend maintenant le produit de nombres entiers :

p = 10 × 10 × 11 × 11 × 12 × 12 × 13 × 13

En effectuant les calculs de gauche à droite, on obtient successivement :

p = (10×10) × 11 × 11 × 12 × 12 × 13 × 13

La 1^re multiplication nécessite donc 4 opérations de multiplication entre chiffres.

En poursuivant les calculs :

p = 100 × 11 × 11 × 12 × 12 × 13 × 13

p = (100 × 11) × 11 × 12 × 12 × 13 × 13

On a ainsi besoin jusque là de 4 + 6 opérations de multiplication.

Puis :

p = (1100 × 11) × 12 × 12 × 13 × 13

Ce qui fait alors au total 4 + 6 + 8 opérations.

etc..

En poursuivant les calculs vers la droite, on obtient finalement 4 + 6 + 8 + 10 + 12 + 14 + 16 = 70 opérations de multiplication en tout pour ce produit.


Considérons maintenant le même produit réarrangé :

p = ((10 × 10) × (11 × 11)) × ((12 × 12) × (13 × 13))

Si on effectue les calculs en respectant la règle de priorité des parenthèses, on peut alors les représenter sur un arbre de produits :

On a donc besoin dans ce cas de seulement 59 opérations de multiplication entre chiffres au lieu de 70 précédemment.

Il s'agit du principe du « diviser pour régner » :

• Diviser : découper un problème initial en sous-problèmes ;
• Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
• Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.

On peut également appliquer ce même principe pour la multiplication de petits polynômes :

Important : L'intérêt principal des arbres de produits est en fait de tirer parti des algorithmes de multiplication rapide d'entiers ou de polynômes.

La situation la plus simple est celle où l'on cherche à calculer le produit d'un grand nombre de « petits » entiers ou polynômes.

Dans ce contexte, et pourvu que l'on dispose d'une multiplication rapide, l'algorithme diviser pour régner est plus efficace que la méthode classique.

Dans notre cas, on va déjà montrer ses avantages dans le développement d'un produit de petits polynômes sans parler de multiplication rapide.



III. Implémenter le développement d'un produit de polynômes

On utilise à nouveau notre classe Polynome à laquelle on ajoute un attribut permettant de compter le nombre d'opérations de multiplication entre termes nécessaires pour développer un produit de polynômes :

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
class Polynome:
 
    def __init__(self, liste_coefs=[0]): # méthode constructeur de la classe
 
	# on définit la liste des coefficients du polynôme [a0, a1, ..., an]
        self.coefs = liste_coefs
 
        # on initialise le nombre d'opérations de multiplication entre termes
        self.nombre_operations = 0
 
	# suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1]
        self.reduire() 
 
    ...

Le code de la méthode permettant de multiplier deux polynômes devient alors :

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
class Polynome:
 
    ...    
 
    def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) =  1 + 3x + 2x^2
 
        # initialisation de la liste des coefficients qu'avec des zéros
        liste_coefs=[0]*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0]
        for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1
            for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2
                # multiplication des coefficients d'indices i1 et i2
                liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs[i1]*other.coefs[i2]
 
        poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste
 
        # ajout du nombre d'opérations de multiplication entre termes effectuées lors de la multiplication entre polynômes
        poly.compteur_operations = self.compteur_operations + other.compteur_operations +  len(self.coefs)*len(other.coefs)
 
        return poly # renvoie le polynôme résultat de la multiplication

Rappel important : les objets Polynome de notre classe sont représentés par une liste de coefficients dont la longueur est égale au degré du polynôme + 1 :

Par exemple, le polynôme X³ + 2 = 2 + 0.X + 0.X² + X³ sera représenté par la liste de coefficients [2, 0, 0, 1].

Par conséquent, le développement du produit (X³ + 2)(X³ + 2) nécessite en fait 4*4 = 16 multiplications entre termes.


III-A. Méthode classique

Testons maintenant l'opérateur de multiplication entre polynômes avec la méthode classique :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
# création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4
p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1])
 
# produit de polynômes
p = p1*p1*p2*p2*p3*p3*p4*p4
 
print("produit = ({0})*({0})*({1})*({1})*({2})*({2})*({3})*({3})".format(p1,p2,p3,p4))
print()
 
print("produit développé = " + str(p))
print()
 
print("nombre d'opérations = " + str(p.nombre_operations))

Le code affiche :

produit = (1 + X)*(1 + X)*(2 + X)*(2 + X)*(3 + X)*(3 + X)*(4 + X)*(4 + X)

produit développé = 576 + 2400.X + 4180.X^2 + 3980.X^3 + 2273.X^4 + 800.X^5 + 170.X^6 + 20.X^7 + X^8

nombre d'opérations = 70


III-B. Principe du « diviser pour régner »

On peut également, comme on l'a vu précédemment, regrouper les sous-produits sur un arbre de produits.

On obtient ainsi la fonction récursive basée sur le principe du « diviser pour régner » :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def produit_polynomes(*polynomes):
 
    # test si le tuple polynomes contient plus de 1 élément
    if len(polynomes)>1:
        i=len(polynomes)//2 # valeur du milieu
        # appels récursifs
        return produit_polynomes(*polynomes[:i])*produit_polynomes(*polynomes[i:])
    else: # sinon
        # renvoie l'unique polynôme du tuple
        return polynomes[0]

Libre à chacun ensuite d'optimiser ce code.

Testons notre fonction avec ces quelques lignes :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
# création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4
p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1])
 
# p = ((p1*p1)*(p2*p2))*((p3*p3)*(p4*p4))
p = produit_polynomes(p1,p1,p2,p2,p3,p3,p4,p4)
 
print("produit = ((({0})*({0}))*(({1})*({1})))*((({2})*({2}))*(({3})*({3})))".format(p1,p2,p3,p4))
print()
 
print("produit développé = " + str(p))
print()
 
print("nombre d'opérations = " + str(p.nombre_operations))

Le code affiche :

produit = (((1 + X)*(1 + X))*((2 + X)*(2 + X)))*(((3 + X)*(3 + X))*((4 + X)*(4 + X)))

produit développé = 576 + 2400.X + 4180.X^2 + 3980.X^3 + 2273.X^4 + 800.X^5 + 170.X^6 + 20.X^7 + X^8

nombre d'opérations = 59


IV. Module complet

On donne pour finir le contenu du module complet :

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
class Polynome:
 
    def __init__(self, liste_coefs=[0]): # méthode constructeur de la classe
 
	# on définit la liste des coefficients du polynôme [a0, a1, ..., an]
        self.coefs = liste_coefs
 
        # on initialise le nombre d'opérations de multiplication entre termes
        self.nombre_operations = 0
 
	# suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1]
        self.reduire() 
 
    def __str__(self): # permet d'afficher le polynôme sous la forme 1 + 2x + 3x^2
        s="" # initialisation de la chaîne de caractères
        # on vérifie d’abord si le degré du polynôme est nul
        if (len(self.coefs)-1==0):
            return str(self.coefs[0])
        else: # sinon
            if self.coefs[0]!=0:
                s=str(self.coefs[0]) + " + "
            for i in range(1, len(self.coefs)): # parcours des indices des coefficients du polynôme : [a1, a2, ..., an]
                if self.coefs[i]!=0: # si le coefficient de degré i n'est pas nul
                    if self.coefs[i]!=1: # si le coefficient de degré i est différent de 1
                        s+="{}.X^{} + ".format(self.coefs[i],i)
                    else: s+="X^{} + ".format(i)  
 
            # élimination des caractères en trop           
            s = s[:-3].replace("+ -", "- ").replace("X^1 ","X ").replace(" 1.X"," X")
            if s[-2:]=="^1": s = s[:-2]
            if s[:3]=="1.X": s = s[3:]
 
            return s # on retourne l'expression du polynôme
 
 
    def degre(self): # retourne le degré du polynôme
        return (len(self.coefs)-1)
 
 
    def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
        # p1 = self, p2 = other     
        if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1 
            liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite. 
        else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
 
        for i in range(n): # parcours des indices de liste_coefs
            liste_coefs[i] = self.coefs[i] + other.coefs[i] # addition des coefficients de degré i
 
        return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
 
 
    def __sub__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
        # p1 = self, p2 = other     
        if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1 
            liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite. 
        else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
 
        for i in range(n): # parcours des indices de liste_coefs
            liste_coefs[i] = self.coefs[i] - other.coefs[i] # addition des coefficients de degré i
 
        return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
 
 
    def reduire(self):
        # tant que le dernier élément de la liste est nul
        while round(self.coefs[-1],12) == 0 and len(self.coefs)>1:
            self.coefs.pop() # supprimer le dernier élément
 
        for i in range(len(self.coefs)):
            self.coefs[i] = round(self.coefs[i],12)
 
 
    def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) =  1 + 3x + 2x^2
 
        # initialisation de la liste des coefficients qu'avec des zéros
        liste_coefs=[0]*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0]
        for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1
            for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2
                # multiplication des coefficients d'indices i1 et i2
                liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs[i1]*other.coefs[i2]
 
        poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste
 
        # ajout du nombre d'opérations de multiplication entre termes effectuées lors de la multiplication entre polynômes
        poly.nombre_operations = self.nombre_operations + other.nombre_operations +  len(self.coefs)*len(other.coefs)
 
        return poly # renvoie le polynôme résultat de la multiplication
 
 
    def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n
        # on crée l'objet poly à partir d'une liste contenant un seul élément 1, élément neutre pour la multiplication des polynômes
        poly = Polynome([1]) 
 
        for i in range(n): # on multiplie n fois poly par self à l'aide de l'opérateur *            
            poly = poly*self # équivalent à : poly = poly.__mul__(self)
 
        return poly # renvoie le polynôme résultat de l'opération (self ** n)
 
 
    def __eq__(poly1, other): # méthode permettant de redéfinir l'opérateur « == » pour 2 polynômes
 
        return (poly1.coefs==other.coefs) # renvoie True si les 2 listes de coefficients sont égales
 
 
    def eval(self,x): # méthode permettant d'évaluer le polynôme en fonction de x
        # intialisation des variables
        valeur_polynome = self.coefs[0] # valeur_polynome = a0
        power=1    
 
        for coef in self.coefs[1:]: # parcours des coefficients du polynôme à partir de a1 : a1, a2, ..., an
            power = power*x # calcul de la puissance de x pour ai : power = x^i
            valeur_polynome += coef*power # valeur_polynome = valeur_polynome + ai*x^i
 
        return valeur_polynome # renvoie la valeur du polynôme
 
    def eval_horner(self,x): # méthode permettant d'évaluer le polynôme en fonction de x
        # intialisation de la variable
        valeur_polynome = self.coefs[-1] # valeur_polynome = an
 
        for coef in reversed(self.coefs[:-1]): # parcours des coefficients du polynôme à partir de an-1 : an-1, ..., a1, a0
            valeur_polynome = valeur_polynome*x + coef  # valeur_polynome = valeur_polynome*x + ai
 
        return valeur_polynome # renvoie la valeur du polynôme
 
 
def produit_polynomes(*polynomes):
 
    # test si le tuple polynomes contient plus de 1 élément
    if len(polynomes)>1:
        i=len(polynomes)//2 # valeur du milieu
        # appels récursifs
        return produit_polynomes(*polynomes[:i])*produit_polynomes(*polynomes[i:])
    else: # sinon
        # renvoie l'unique polynôme du tuple
        return polynomes[0]
 
 
print()
print("I. Produit de polynômes : méthode classique")
print()
 
# création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4
p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1])
 
# produit de polynômes
p = p1*p1*p2*p2*p3*p3*p4*p4
 
print("produit = ({0})*({0})*({1})*({1})*({2})*({2})*({3})*({3})".format(p1,p2,p3,p4))
print()
 
print("produit développé = " + str(p))
print()
 
print("nombre d'opérations = " + str(p.nombre_operations))
 
print()
print()
print("II. Produit de polynômes : principe du diviser pour régner")
print()
 
# produit de polynômes
# p = (p1*p1*p1)*(p2*p2*p2)
# p = ((p1*p1)*(p2*p2))*((p3*p3)*(p4*p4))
p = produit_polynomes(p1,p1,p2,p2,p3,p3,p4,p4)
 
print("produit = ((({0})*({0}))*(({1})*({1})))*((({2})*({2}))*(({3})*({3})))".format(p1,p2,p3,p4))
print()
 
print("produit développé = " + str(p))
print()
 
print("nombre d'opérations = " + str(p.nombre_operations))

V. Conclusion

Nous avons donc pu montrer les avantages du « diviser pour régner » dans le calcul du produit de nombres entiers, puis dans le développement du produit de petits polynômes, pour enfin le vérifier en Python à l'aide de la classe Polynome.


Sources :

https://fr.wikipedia.org/wiki/Algori...on_d%27entiers
https://fr.wikipedia.org/wiki/Divise...(informatique)
https://fr.wikipedia.org/wiki/Arbre_de_produits
https://fr.wikipedia.org/wiki/Tri_fusion