I. IntroductionOn 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 n2 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(n2).
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 1re 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 |
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 |
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 X3 + 2 = 2 + 0.X + 0.X2 + X3 sera représenté par la liste de coefficients [2, 0, 0, 1].
Par conséquent, le développement du produit (X3 + 2)(X3 + 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 |
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 |
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 |
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 |
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