Correction.
Ci-dessous, on a rajouté la classe __pow__. Attention, c'est à lire après la partie sur les puissances rapides.
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)
def __pow__(self, n):
if n > 1:
return puissance_rapide(self, n)
else:
return EntierModulo(1, self.modulo)
x= EntierModulo(3,11)
y= EntierModulo(9, 11)
print("x=", x, "et y=", y)
x+y
x*y
x**0
def matrice_nulle(m, n):
"""renvoie la matrice nulle à m lignes et n colonnes"""
return [ [0]*n for i in range(m)]
class Matrice:
def __init__(self, L):
"""L est une liste de listes. Cette méthode stocke L dans l'objet."""
self.coeffs= L
def __str__(self):
# on utilise + pour additionner des chaines de caractères
# de plus la chaine "\n" donne un retour à la ligne
chaine= ""
for ligne in self.coeffs:
chaine= chaine + str(ligne) + "\n"
return chaine
def __repr__(self):
return self.__str__()
def __getitem__(self, tup): # redéfinit []
# self[tup] renvoie self.__getitem__(tup)
# ici tup = (i,j) sera une paire
i= tup[0]
j= tup[1]
return self.coeffs[i][j]
def __add__(self, autre):
nb_lignes= len(self.coeffs)
nb_colonnes= len(self.coeffs[0])
M= matrice_nulle(nb_lignes, nb_colonnes)
for i in range(nb_lignes):
for j in range(nb_colonnes):
M[i][j]= self[i,j] + autre[i,j]
return Matrice(M)
def __mul__(self, autre):
nb_lignes= len(self.coeffs)
nb_colonnes= len(autre.coeffs[0])
M= matrice_nulle(nb_lignes, nb_colonnes)
m= len(self.coeffs[0]) # nb de colonnes de self
for i in range(nb_lignes):
for j in range(nb_colonnes):
M[i][j]= sum([ self[i,k]*autre[k,j] for k in range(m) ])
return Matrice(M)
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.
"""
nb_lignes= len(self.coeffs)
nb_colonnes= len(self.coeffs[0])
# on fait une copie des coeffs
M= matrice_nulle(nb_lignes, nb_colonnes)
for x in range(nb_lignes):
for y in range(nb_colonnes):
M[x][y]= self[x,y]
# ou alors M= [ ligne[:] for ligne in self.coeffs ]
# on efface la ligne i
M.pop(i)
# on efface la colonne j
for ligne in M:
ligne.pop(j)
# et voilà
return Matrice(M)
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.
"""
n= len(self.coeffs) #nb de lignes -- fonctionne seulement pour les matrices carrées...
if n == 1:
return self[0,0]
elif n == 2:
return self[0,0]*self[1,1] - self[0,1]*self[1,0] # 'produit en croix'
else:
return sum([ (-1)**j * self[0,j] * self.mineur(0,j).determinant() for j in range(n) ])
def __pow__(self, n):
if n > 1 :
return puissance_rapide(self, n)
else:
# il faut faire la matrice identité de la bonne taille
nb_lignes= len(self.coeffs)
I= matrice_nulle(nb_lignes, nb_lignes)
for i in range(nb_lignes):
I[i][i]= 1
return Matrice(I)
Petits rappels sur les matrices utiles pour comprendre le code ci-dessus.
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$.
Développement d'un déterminant par la première ligne.
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!)
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$.
def puissance_rapide(g,n):
if n == 1:
return g
else:
# division euclidienne n = 2k + eps
k= n//2
eps= n%2
# g^n = (g^k)^2 * g^eps donc :
g_k= puissance_rapide(g,k) # notez k != 0. Ici g_k = g^k.
g_2k= g_k * g_k
if eps == 0 :
#print("on a fait une multiplication")
return g_2k
else:
#print("on a fait deux multiplications")
return g_2k * g
def puissance_lente(g,n):
if n == 1:
return g
else:
return g*puissance_lente(g, n-1)
%time puissance_rapide(2, 100)
%time puissance_lente(2, 100)
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__.
def pgcd(a,b):
if b == 0:
return a
else:
r= a % b
return pgcd(b,r)
pgcd(-24, 15)
class Rationnel:
def __init__(self, a, b):
# on simplifie la fraction a/b:
d= pgcd(a, b)
self.num= a // d
self.den= b // d
def __str__(self): # appelé par x.__str__()
if self.den == 1:
return str(self.num)
else:
return str(self.num) + "/" + str(self.den)
def __repr__(self):
return self.__str__()
def __eq__(self, autre):
a= self.num
b= self.den
c= autre.num
d= autre.den
return a*d == b*c
def __add__(self, autre): # x + y appelle x.__add__(y) ou encore __add__(x,y)
a= self.num
b= self.den
c= autre.num
d= autre.den
return Rationnel(a*d + b*c, b*d)
def __mul__(self, autre):
a= self.num
b= self.den
c= autre.num
d= autre.den
return Rationnel(a*c, b*d)
def __truediv__(self, autre): # truediv = /, floordiv= //
a= self.num
b= self.den
c= autre.num
d= autre.den
return Rationnel(a*d, b*c )
Rappel : addition de fractions
On a
$$ \frac a b + \frac c d =\frac {ad + bc} {bd} $$
Rationnel(1,1) / Rationnel(2,1)
Z comme $\mathbb{Z}$
Z= lambda n : Rationnel(n,1)
Z(1) / Z(2) + Z(1)/Z(3)