L3 MIASHS, Algorithme et Programmation 3, année 2022

Correction de la question 1 du premier TD

On souhaite réaliser une classe qui implémente un polynome de \(\mathbb{R}[X]\).

L’objectif de la question:

  1. Se (re)familiariser avec Python
  2. Apprendre à écrire une classe simple

Le fichier complet est ici.

Modélisation

Un polynôme est une représentation abstraite d’une fonction. L’ensemble des polynômes de \(\mathbb{R}[x]\) est en bijection avec l’ensemble des suites finis de \(\mathbb{R}\):

Étant donnée un polynôme \(P\in\mathbb{R}[x]\), il existe un unique \(d\in\mathbb{N}\) et des uniques et \(a_0,\cdots, a_d\) avec \(a_d\neq 0\) tel que \(P=\sum_i=0^d a_i X^i\). La séquence \((a_0, \cdots, a_d)\) caractérise complètement le polynôme \(P\).

Une manière de stocker les polynômes consiste à stocker sa liste de coefficient, en faisant attention à ce que le coefficient de gros degré ne soit pas nul, a l’exception du polynôme nul.

import math
class Polynome:
    def __init__(self, coefficients):
        coefficients = list(coefficients)
        for i in range(len(coefficients)):
            if coefficients[-1] == 0:
                coefficients.pop(-1)
            else:
                break
        if not coefficients:
            coefficients = (0,) # si aucun coefficient est non vide, on ajoute le coefficient nul à la liste.
        self._coefficients = tuple(coefficients) # mieux vaut stocker la liste des coefficients de manière non mutable.
        # Ça permet d'éviter des erreurs, un polynôme n'a pas de raison de changer de coefficients (c'est un objet non mutable).
        # On met un "_" devant le champ pour laisser définir une propriété, c'est une conventions
        #
    @property
    def degree(self):
        if self.coefficients == (0,):
            return -math.inf # le polynôme nul est de degré -∞ 
        return len(self.coefficients) - 1

    @property
    def coefficients(self):
        return self._coefficients

    def __repr__(self):
        s = f"{self.coefficients[0]}"
        if self.degree >= 1:
            c = self.coefficients[1]
            sign = " + "
            if c<0:
                sign = " - "
                c = -c
            s += f"{sign}{c}X"
        i = 2
        for c in self.coefficients[2:]:
            sign = " + "
            if c<0:
                sign = " - "
                c = -c
            s += f"{sign}{c}X^{i}"
            i += 1
        return s

Cette classe minimaliste permet d’avoir:

P = Polynome((0, 1, 2, -3, 4))
print(f"{P = }")
print(f"{P.degree = }")
P = 0 + 1X + 2X^2 - 3X^3 + 4X^4
P.degree = 4

On veut permettre la manipulation de l’anneau des Polynômes. Pour ça on ajoute des opérateurs à la classe. On surcharge les opération P + Q (add), -P (neg), P - Q (sub), P * Q (mul).

Pour éviter d’écrire toujours les mêmes codes, on peut appeler les méthodes déjà définit pour en construire des nouvelles. Cela simplifie beaucoup le travail. Par exemple, avec P + Q et -P on peut définir P - Q comme étant P + (-Q).

On définit également la construction P + a et P*a quand a est un nombre. Pour ça il faut vérifier que a est bien un nombre et introspecter sa valeur.

import numbers
class Polynome(Polynome): # Ignorez cette ligne, ça me permet de ne pas réécrire les méthodes au dessus.
# on verra ça plus tard quand on parlera d'héritage.
    def __add__(self, other):
        if isinstance(other, numbers.Number):
            other = Polynome([other]) # other est un nombre, on le transforme en Polynôme.
        if len(other.coefficients) > len(self.coefficients):
            return other + self
        coefficients = []
        for i in range(len(self.coefficients)):
            c = self.coefficients[i]
            if i < len(other.coefficients):
                c += other.coefficients[i]
            coefficients.append(c)
        return Polynome(coefficients)

    def __neg__(self):
        return Polynome([-a for a in self.coefficients])

    def __sub__(self, other):
        return self + (-other) # On utilise add et neg pour définir sub

    def __mul__(self, other):
        if isinstance(other, numbers.Number):
            other = Polynome([other])
        Q = Polynome([0]) # On va accumuler le résultat dans Q
        for i, c in enumerate(other.coefficients):
            coefficients = [0]*i + [c*e for e in self.coefficients] # On construit les P*cX^i avec P=self.
            Q = Q + Polynome(coefficients) # Et on additionne
        return Q

    def __call__(self, x):
        return sum(map(lambda c,i: c*x**i, self.coefficients, range(self.degree)))

Les méthodes qu’on a introduite permet de jouer un peu plus avec les Polynômes.

P = Polynome((1, 2, 3))
print(f"{P - P = }")
P - P = 0
print(f"{P(3) = }")
P(3) = 7
print(f"{P + 3 = }")
P + 3 = 4 + 2X + 3X^2
print(f"{P * (P + 3) = }")
P * (P + 3) = 4 + 10X + 19X^2 + 12X^3 + 9X^4

Par contre, les polynômes qu’on a définit ne sont pas des nombres. Il n’est pas possible de multiplier par un nombre à leur gauche.

Appeler 3*P revient à faire int.__mul__(P) mais vu que les entiers ne connaissent pas les polynômes, cela entraine nécessairement des erreurs:

print(f"{3*P = }")
Traceback (most recent call last):
  File "/var/www/cha/check_py_md", line 77, in repl
    exec(code, env)
  File "<string>", line 1, in <module>
TypeError: unsupported operand type(s) for *: 'int' and 'Polynome'

Il est possible d’utiliser pour ça une surcharge des opérateurs à droites, qui est systématiquement appeler quand la classes des objets ne concorde pas.

class Polynome(Polynome):
    def __rmul__(self, other):
        return self * other # Ici on a appeler other * self, ce qui est traduit pas self.__rmul__(other) si rmul est défini.

    def __rsub__(self, other):
        return (-self) + other

    def __radd__(self, other):
        return self + other
P = Polynome((1, 2, 3))
print(f"{3 + P = }")
3 + P = 4 + 2X + 3X^2
P = Polynome((1, 2, 3))
print(f"{3 * P = }")
3 * P = 3 + 6X + 9X^2

Dérivations

Ce n’est pas compliquer de dériver des polynômes depuis leur forme développer. En posant \(P=\sum_{i=0}^d a_i X^i\), alors \(P'=\sum_{i=1} a_i * i X^{i-1}\).

class Polynome(Polynome):
    def derivate(self):
        return (-self) + other
    
    def derivate(self):
        coefficients = []
        for i, c in enumerate(self.coefficients[1:]):
            coefficients.append(c*(i+1))
        return Polynome(coefficients)
P = Polynome((1, 2, 3))
print(f"{P.derivate() = }")
P.derivate() = 2 + 6X

Compiled the: mer. 04 sept. 2024 12:49:51 CEST