En mathématiques, un théorème bien fait n'a pas d'hypothèses superflues : si un résultat, disons une formule avec $x, y$ et $z$, est vrai pour $x, y, z$ pris dans un anneau quelconque, on ne va pas se contenter de l'énoncer pour $x, y, z\in\mathbb{Z}$. On donne un seul théorème, qui peut resservir dans de nombreuses situations.
Il y a un phénomène similaire en informatique : si on peut écrire un algorithme intéressant, qui dépend de trois arguments x, y et z, et qui fonctionne correctement dès que les opérations (disons) + et * peuvent s'appliquer, alors on ne va se contenter d'écrire notre algorithme pour x, y et z entiers (enfin, on pourrait le faire pour des raisons de vitesse; mais ici ce qui nous intéresse c'est la généralité).
Typiquement, écrire un algorithme "général" (on dit plus souvent "générique" en informatique) est très facile, en tout cas en Python : il suffit de ne rien dire sur, disons, x, y, et z, et le code est accepté. A l'exécution, Python voit s'il arrive à donner un sens au code avec les valeurs sur lesquelles on fait un essai. Par contre, pour faire fonctionner du code que l'on a écrit, il va parfois être nécessaire de dire à Python quoi faire lorsqu'il rencontre par exemple x+y et que x et y sont d'un type un peu compliqué, par exemple des entiers modulo $p$ ou des matrices.
Voyons comment redéfinir le sens de + , *, / etc etc, en Python. Pour ça, il faut comprendre un peu de programmation orientée objet. Cette technique a beaucoup d'autres utilisations, et nous ne faisons qu'effleurer le sujet.
Voici le sommaire :
Pour commencer, on peut créer une classe en Python simplement pour regrouper des variables ensemble :
class Rectangle: # l'usage est de donner un nom avec une majuscule
largeur= 0
longueur= 0
Ensuite on crée un exemple (on dit une instance) comme ceci :
R= Rectangle()
On dit que R est un objet de classe Rectangle. Ce qui permet de faire :
R.longueur= 10
R.largeur= 5
print(R.longueur)
Jusqu'ici, le seul intérêt est que les deux valeurs sont regroupées ensemble "dans" l'objet R, avec cette syntaxe qui utilise un point. Mais on peut apprendre à un objet de class Rectangle à calculer tout seul son aire, par exemple :
# ceci remplace la définition précédente
class Rectangle:
largeur= 0
longueur= 0
def aire(self):
return self.longueur * self.largeur
R= Rectangle()
R.longueur= 3
R.largeur= 2
print(R.aire())
Décortiquons un peu ceci. La fonction aire est définie dans la classe Rectangle (on dit que c'est une méthode de celle-ci). Elle reçoit comme paramètre l'objet en question, celui qui est en train de calculer son aire, et on l'appelle toujours self (=soi-même en anglais) parce qu'on rédige la fonction en pensant "quand un rectangle veut calculer son aire, il lui faut connaître sa propre longueur et sa propre largeur".
Bref, que l'on pense comme ça ou pas, dans la fonction on a maintenant accès à self.longueur et self.largeur. Quand on fait l'appel R.aire(), tout se passe comme si on faisait aire(R) -- sauf que c'est la bonne fonction aire qui est appelée. Par exemple supposons que l'on ait aussi :
class Disque():
rayon= 0
def aire(self):
return 3.14*self.rayon**2
D= Disque()
D.rayon= 5
print(D.aire())
Si on écrit alors quelque part un portion de code avec if x.aire() < 10 (par exemple), et bien ça fonctionnera parfaitement que x soit un Rectangle ou un Disque, ou tout objet disposant d'une méthode aire. Cette propriété est vraiment très utile, comme on le disait dans l'introduction.
Les objets ont certaines méthodes avec un statut particulier. On les reconnait à leurs noms qui commencent par __ (deux fois le caractère de soulignement). Ainsi la méthode __init__ est appelée au moment où l'objet est crée. Exemple :
# ceci remplace encore la définition précédente
# après on arrête !
class Rectangle:
# noter que l'on n'indique plus la présence des variables
# "longueur" et "largeur" : elles sont créées dans __init__
def __init__(self, a, b):
self.longueur= max(a,b)
self.largeur= min(a,b)
def aire(self):
return self.longueur * self.largeur
R= Rectangle(2,3)
R.longueur
Concluons cette introduction avec une mention de ce qu'on appelle l'héritage. C'est une technique très puissante là encore, et bien des gens vous diront que c'est l'intérêt principal des objets, mais dans ce cours nous n'aurons pas le temps d'en parler beaucoup. On signale juste la chose pour que vous l'ayez vu une fois -- ce qui suit est "hors programme". Un exemple fera l'affaire :
class Carre(Rectangle):
def __init__(self, x):
self.longueur= x
self.largeur= x
C= Carre(12)
print("le carré de côté", C.longueur, "a pour aire", C.aire())
C'est assez simple : en écrivant Carre(Rectangle), on stipule que la classe que l'on construit hérite de tout ce qu'il y a dans la classe Rectangle, et ensuite on apporte des modifications. Ici on a modifié le comportement de __init__, on aurait pu aussi ajouter des méthodes, etc.
En plus de __init__, nous allons maintenant examiner quelques méthodes spéciales supplémentaires :
la méthode __str__. Quand on demande à Python print(x), il essaie d'appeler str(x) qui convertit x en chaîne de caractères ; et str(x) essaie d'appeler x.__str__() (si ça ne marche pas, la fonction str peut parfois se débrouiller autrement). Donc en donnant notre propre méthode __str__, on peut contrôler ce que donne la commande print pour nos objets.
la méthode __repr__. Celle-ci est utilisée dans l'interface graphique que nous utilisons quand on tape x en dernière ligne d'une cellule, parce qu'on a été trop paresseux pour écrire print(x). En général, on demande à cette méthode de renvoyer la même chose que __str__.
la méthode __add__. Elle sert à redéfinir le symbole + pour nos objets. Voir l'exemple ci-dessous.
la méthode __mul__ sert à redéfinir le symbole *. Voir l'exemple.
Voici un exemple. On définit une classe pour réprésenter les éléments de $\mathbb{Z}/p\mathbb{Z}$. On veut pouvoir les additionner avec + et les multiplier avec * -- après tout, c'est un anneau comme un autre. On peut aussi que le modulo soit rappelé à chaque fois qu'on affiche un objet. Ceci donne :
class EntierModulo:
def __init__(self, n, p):
self.n= n % p
self.modulo= p
def __str__(self):
return str(self.n) + " mod " + str(self.modulo)
def __repr__(self):
return str(self)
def __add__(self, autre):
addition= self.n + autre.n
return EntierModulo(addition, self.modulo) # la réduction mod p se fait ici
def __mul__(self, autre):
mult= self.n * autre.n
return EntierModulo(mult, self.modulo)
x= EntierModulo(3,11)
y= EntierModulo(9, 11)
print("x=", x, "et y=", y)
x+y
x*y
On vous demande de compléter le code ci-dessous, en remplaçant à chaque fois la commande pass (qui signifie : "rien") par les bonnes instructions. A la fin, on doit pouvoir entrer par exemple A= Matrice([[1,2], [3,4]]) puis B= Matrice([[0,1], [0,1]]), et ensuite calculer A+B, A*B, A.determinant() etc.
Voyez aussi les indications ci-dessous.
class Matrice:
def __init__(self, L):
"""L est une liste de listes. Cette méthode stocke L dans l'objet."""
pass
def __str__(self):
pass
def __repr__(self):
pass
def nb_lignes(self):
pass
def nb_colonnes(self):
pass
def __add__(self, autre):
pass
def __mul__(self, autre):
pass
def mineur(self, i, j):
"""Cette méthode renvoie le mineur (i,j).
Par définition, il s'agit de la matrice obtenue en supprimant la ligne i
et la colonne i.
"""
pass
def determinant(self):
"""Calcule le déterminant de self.
On procèdera par récurrence : formule directe pour les matrices 1x1 ou 2x2,
et développement par une ligne sinon. C'est très lent, mais c'est instructif.
"""
pass
Petits rappels sur les matrices utiles pour cet exercice.
Le produit de matrices.
Le produit de la matrice $A= (a_{ij})$ par la matrice $B= (b_{ij})$ est défini $A$ possède autant de colonnes, disons $m$, que $B$ possède de lignes.
Sur la ligne $i$, dans la colonne $j$ du produit $AB$ on trouve
$$ \sum_{k= 1}^m a_{ik}b_{kj} $$
Par ailleurs $AB$ a autant de lignes que $A$ et autant de colonnes que $B$.
Une formule pour le déterminant.
Si $A = (a_{ij})$ est une matrice $n\times n$ alors
$$ det(A) = \sum_{j=1}^n (-1)^{j+1} a_{1j} \, det(\Delta^{1j}) $$
où $\Delta^{ij}$ est le mineur $(i,j)$. En Python, si la matrice est self alors $\Delta^{i,j}$ est self.mineur(i-1,j-1). (On numérote à partir de 0 en python!)
Comme indiqué dans les commentaires ci-dessus, ce mineur est obtenu en supprimant la ligne $i$ et la colonne $j$ ; c'est donc une matrice strictement plus petite que celle de départ, et on a bien une définition par récurrence, si on ajoute que pour une matrice $1\times 1$, on a $det(a) = a$. Pour une matrice $2\times 2$ on obtient
$\displaystyle det \left(\begin{array}{cc} a & b \\ c & d \end{array}\right) = ad - bc$.
Il existe bien d'autres définitions du déterminant!
Voici une application. On va donner un algorithme très classique pour calculer rapidement $g^n$. Mathématiquement, nous dirions que $g$ est ici n'importe quel élément d'un groupe (ou même d'un monoïde...). Ici, on va calculer $g^n$ dès que g est un objet pour lequel la multiplication avec * fonctionne. Par exemple, ça va marcher avec les entiers, les entiers mod $p$ comme ci-dessus, et les matrices.
Qu'entendons par "calculer rapidement"? Il s'agit d'éviter de tomber dans le piège ci-dessous. Si on veut calculer $g^{16}$ par exemple, on peut calculer $g^2$ en multipliant $g$ avec lui-même, puis multiplier ça par $g$ pour obtenir $g^3$, puis multiplier par $g$... On fait donc 15 multiplications. Alors qu'on peut calculer $g^2$, le stocker, puis le mettre au carré pour obtenir $g^4$, et le remettre au carré pour obtenir $g^8$, et encore au carré pour $g^{16}$. On a fait seulement 4 multiplications!
Plus généralement, l'algorithme de mise à la puissance rapide s'appuie sur la remarque suivante. On veut calculer $g^n$. On écrit alors $n= 2k + \epsilon$ avec $\epsilon\in\{0,1\}$ (division euclidienne de $n$ par $2$). Alors
$$g^n = (g^k)^2\cdot g^\epsilon .$$
Ceci donne une méthode par récurrence (puisque $g^n$ est très facile à calculer pour $n=0$ ou $n=1$...), mais comme $k$ est environ deux fois plus petit que $n$, ça va très vite.
Exercice (puissances rapides) Ecrivez une fonction
puissance_rapide(g,n)qui calcule $g^n$ par la méthode ci-dessus. Votre fonction doit marcher correctement pour tout objetgpour lequel*fonctonne comme prévu. Par contre, on ne demande pas que la fonction marche pour $n=0$, parce qu'on ne sait pas s'il faudrait renvoyer 1 ou la matrice identité etc.Puis, modifier les classes
EntierModuloetMatricepour leur ajouter une méthode__pow__(self, n), qui sera appelée par la syntaxe usuelle en Python**n. Faites-la fonctionner même pour $n=0$.
Supposons que l'on travaille avec des rectangles, et que l'on ait trouvé utile de définir les objets Rectangle comme ci-dessus. Admettons maintenant que l'aire d'un rectangle soit la seule information qui compte vraiment pour nous, et que deux rectangles de même aire puissent être considérés comme égaux pour nous. Mathématiquement, on dirait, de manière très sophistiquée, qu'on regarde la relation d'équivalence $\equiv$ sur l'ensemble des rectangles, pour laquelle $R\equiv R'$ signifie qu'ils ont la même aire, et qu'on va travailler avec "l'ensemble quotient..." De manière plus terre à terre, en Python on peut tout simplement redéfinir ==, à l'aide de la méthode spéciale __eq__. Voyons ça :
# Revoilà une version de la classe Rectangle !
# Nous avions menti.
class Rectangle:
def __init__(self, a, b):
self.longueur= max(a,b)
self.largeur= min(a,b)
def aire(self):
return self.longueur * self.largeur
def __eq__(self, autre):
return self.aire() == autre.aire()
R1= Rectangle(2,3)
R2= Rectangle(6,1)
R1 == R2
Nous avions promis dans la première feuille qu'il était possible d'apprendre à Python comment manipuler les fractions ; voici comment. (Evidemment, nous ne sommes pas les premiers à faire ça, et nous pourrions utiliser du code existant, et d'ailleurs nous aborderons ça dans un autre TP.)
Les élements de $\mathbb{Q}$ peuvent être définis comme les paires $(a, b)$ d'entiers avec $b\ne 0$, modulo la relation qui identifie $(a,b)$ et $(c,d)$ si et seulement si $ad = bc$. Le nombre rationnel défini par $(a,b)$ est noté $\frac a b$.
Exercice (nombres rationnels) Définir une classe
Rationnelqui modélise les nombres rationnels. Il faut en particulier que l'on obtienne les résultats suivants (la valeur renvoyée étant en commentaire) :
Rationnel(1,2) # 1/2
Rationnel(2,4) # 1/2
Rationnel(5,1) # 5
Rationnel(1,2) == Rationnel(2,4) # True
Rationnel(1,2) + Rationnel(1,3) # 5/6Si on ajoute
Z= lambda n : Rationnel(n,1)(leZétant censé nous rappeler $\mathbb{Z}$) alors on doit avoir aussi :
Z(1)/Z(2) + Z(1)/Z(3) # 5/6Pour ceci, il va falloir redéfinir
/, à l'aide de la méthode__truediv__.
Rappels