Séance 1 : Matrices, suites récurrentes, algorithme de Hörner¶
A) Matrices en Python: explications¶
En mathématiques on appelle matrice un tableau de nombres (entiers, réels ou même complexes...). Voici par exemple une matrice ${\tt A}$ à 3 lignes et 4 colonnes: $$\left(\begin{array}{cccc} 3&-1&6&-1\\ -1&1&2&1\\ 0&7&4&-2\end{array}\right)$$
En Python on les représente par des listes de listes c'est-à-dire une liste dont les éléments sont eux mêmes des listes :
A = [ [3, 1, 6, -1] , [-1, 1, 2, 1] , [0, 7, 4, -2] ] # affectation
print( A ) # affichage de la valeur de A
[[3, 1, 6, -1], [-1, 1, 2, 1], [0, 7, 4, -2]]
Si on veut un affichage plus élégant on demande l'affichage ligne par ligne:
def affiche(A) :
for ligne in A :
print(ligne)
# la fonction ne renvoie rien
affiche(A)
[3, 1, 6, -1] [-1, 1, 2, 1] [0, 7, 4, -2]
1. Nombre de lignes d'une matrice¶
Le nombre lignes s'obtient ainsi:
print( len(A) ) # affichage de la valeur de len(A)
3
2. Nombre de colonnes d'une matrice¶
Pour le nombre de colonnes on compte le nombre d'éléments de la liste de la première ligne:
print( len(A[0]) ) # affichage de la valeur de len(A[0])
4
3. Lecture/Modification d'un élément¶
On accède à l'élément de ligne $i$ colonne $j$ avec la commande ${\tt A[i][j]}$ (attention on numérote lignes et colonnes à partir de $0$):
print( A[1][2] ) # Lecture
2
A[2][3] = 99 # Modification
affiche(A)
[3, 1, 6, -1] [-1, 1, 2, 1] [0, 7, 4, 99]
4. Lecture/Modification d'une ligne¶
La liste de la ligne d'indice i
s'obtient simplement avec la commande A[i]
.
Attention: comme les indices commencent à $0$ on obtient la i+1
-ième ligne de A
.
print( A[2] ) # i=2 donc affichage de la 3-ième ligne de A
[0, 7, 4, 99]
On modifie la ligne d'indice 2 :
A[2] = [4, 3, 2, 1]
affiche(A)
[3, 1, 6, -1] [-1, 1, 2, 1] [4, 3, 2, 1]
5. Lecture/Modification d'une colonne¶
Par contre la liste de la colonne $j$ doit être créée avec une liste définie par compréhension via la commande ${\tt [\; A[i][j]\; for\; i\; in \;range(len(A))\; ]}$
(on rappelle que ${\tt len(A)}$ donne le nombre de lignes).
Attention: comme les indices commencent à $0$ on obtient la $(j+1)$-ième colonne de A
.
[ A[i][0] for i in range(len(A)) ] # j=0 dont c'est la j+1=1ère colonne de A
[3, -1, 4]
Il est plus difficile de modifier toute une colonne. L'instruction précédente ne donne pas directement accès à la colonne mais seulement à une copie. Modifier la copie ne va pas modifier la valeur initiale.
On est obligé d'utilisé une boucle for
:
for i in range(len(A)) :
A[i][0] = 9 # on met 9 dans toute la première colonne
affiche(A)
[9, 1, 6, -1] [9, 1, 2, 1] [9, 3, 2, 1]
6. Initialisation d'une matrice dont tous les coefficients sont nuls¶
Pour intialiser une matrice à 3 lignes et 4 colonnes dont tous les coefficients sont nuls la meilleure méthode est d'utiliser la définition d'une liste par compréhension:
M = [ [ 0 for j in range(4) ] for i in range(3) ] # l'indice j pour les colonnes et l'indice i pour les lignes
affiche(M)
[0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]
En informatique les matrices sont utilisées par exemple pour le calcul vectoriel (dans les moteurs 3D des jeux vidéos) ou pour réprésenter des images (les couleurs étant codées par les valeurs stockées dans la matrice).
Q1. Ecrire une fonction Somme(Mat)
qui renvoie la somme des tous les coefficients de la matrice Mat
.
Q2. Ecrire une fonction Maximum(Mat)
qui renvoie le maximum des coefficients de la matrice Mat
.
Q3. Ecrire une fonction Transpose(Mat)
qui prend en argument une matrice Mat
et renvoie une nouvelle matrice dont les lignes sont les colonnes de la matrice Mat
. Cette fonction ne doit pas modifier la variable Mat
.
Par exemple $\left(\begin{array}{cccc} 3&-1&6&-1\\ -1&1&2&1\\ 0&7&4&-2\end{array}\right)$ devient $\left(\begin{array}{ccc} 3&-1&0\\ -1&1&7\\ 6&2&4\\ -1&1&-2\end{array}\right)$.
Si Mat
a n
lignes et p
colonnes il faudra donc créer une matrice Mat2
à p
lignes et n
colonnes dont tous les coefficients sont initialisés à 0
puis les modifier avec l'instruction Mat2[i][j] = Mat[j][i]
.
La suite de Fibonacci ${\tt (F_n)_{n\in\mathbb{N}}}$ est définie de la façon suivante: ${\tt F_0=F_1=1}$ et pour tout entier naturel ${\tt n}$, ${\tt F_{n+2} = F_{n+1} + F_n}$.
Cette suite doit son nom à Leonardo Fibonacci qui, dans un problème récréatif posé dans l'ouvrage Liber abaci publié en 1202, décrit la croissance d'une population de lapins : "Quelqu’un a déposé un couple de lapins dans un certain lieu, clos de toutes parts, pour savoir combien de couples seraient issus de cette paire en une année, car il est dans leur nature de générer un autre couple en un seul mois, et qu’ils enfantent dans le second mois après leur naissance."
https://www.pourlascience.fr/sd/logique/la-suite-de-fibonacci-et-ses-suites-9757.php
Q4. Ecrire une fonction Fibo(n)
qui prend en argument un entier naturel n
et renvoie la valeur de ${\tt F_n}$.
Q5. On peut démontrer que lorsque n
devient grand le nombre ${\tt F_n}$ devient très proche du nombre ${\tt \dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}}$.
On souhaite le constater graphiquement.
Pour cela écrire une fonction FiboListe(n)
qui prend en argument un entier naturel n
et renvoie la liste des ${\tt (n+1)}$ premiers termes de la suite de Fibonacci.
Utiliser ensuite cette fonction pour tracer sur un même graphe avec les ${\tt (n+1)}$ premiers termes de la suite de Fibonacci et de la suite de terme général ${\tt \dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}}$ pour constater graphiquement le résultat mathématique donné ci-dessus (à vous de bien choisir la valeur de l'entier n
).
On rappelle que si u
et v
sont deux listes des ${\tt (n+1)}$ premiers termes de deux suites alors on les représente graphiquement avec les instructions:
import matplotlib.pyplot as plt
plt.figure() # Initialise une nouvelle figure
plt.plot(u)
plt.plot(v)
plt.show()
D) Algorithme de Hörner¶
Pour additionner deux nombres à n
chiffres (en binaire), le temps de calcul pour le processeur est de l'ordre de n
. Pour multiplier ces deux nombres le temps de calcul est de l'ordre de n**2
donc beaucoup plus coûteux. L'algorithme de Schönage-Strassen publié en 1971 permet de ramener ce temps de calcul à n*ln(n)*ln(ln(n))
. Il a fallu attendre 2007 et la publication de l'algorithme de Fürer, puis 2019 et l'article de Harvey et van Der Hoeven pour avoir un temps de calcul en n*ln(n)
(temps jugé optimal selon la conjecture de Schönage-Strassen).
Retenons simplement qu'il est significativement plus coûteux de multiplier des nombres que de les additionner.
Nous allons implémenter l'algorithme de Hörner, qui permet de limiter le nombre de multiplications utilisées lorsqu'on évalue un poynôme en un réel x
.
En Python on peut représenter l'expression polynomiale $P(x)=a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1}x^{n-1}$ par une liste
a
contenant les coefficients du polynôme : ${\tt a[i] = a_i}$ pour tout ${\tt i\in[\![0,n-1]\!]}$.
La donnée de la listea
et d'un flottantx
permet alors de calculer la valeur de ${\tt P(x)}$.
Q6. Ecrire une fonction EvalPolynome(a,x)
qui prend en argument une liste de flottants a
et un flottant x
et renvoie le nombre a[0]+a[1]*x+a[2]*x**2+a[3]*x**3+...+a[len(a)-1]*x**(len(a)-1)
.
Compter le nombre de multiplications effectuées par l'algorithme (en fonction de n=len(a)
).
Q7. Ecrire une fonction Horner(a,x)
qui prend en argument une liste de flottants a
et un flottant x
et renvoie le nombre le même nombre mais calculé selon la formule de Hörner:
$$a_0+a_1x+a_2x^2+a_3x^3+\dots+a_{n-1}x^{n-1}=a_0+x*\Bigg(a_1+x*\Bigg(a_2+x*\Bigg(a_3+\dots+x*a_{n-1}\Bigg)\Bigg)\Bigg)$$
Compter le nombre de multiplications effectuées par ce nouvel algorithme (en fonction de ${\tt n}$).
Lequel des ces deux algorithmes vous paraît le plus performant?
https://fr.wikipedia.org/wiki/M%C3%A9thode_de_Ruffini-Horner
E) Approndissements¶
a] D'autres algorithmes sur les matrices¶
Q8. Ecrire une fonction MaxUn(Mat)
qui prend en argument une matrice Mat
de 0
et de 1
(par exemple une image en noir et blanc représentant un QR code) et renvoie le nombre maximal de 1
sur une ligne (le nombre maximal de pixels noirs sur une ligne).
Q9. Ecrire une fonction IndLigne(Mat)
qui prend en argument une matrice Mat
de 0
et de 1
et renvoie en sortie l'indice d'une des lignes possédant le plus de 1
.
Q10. Ecrire une fonction NbUn(Mat)
qui prend en argument une matrice Mat
de 0
et de 1
et renvoie le nombre de lignes possédant au moins un 1
.
b] Effets de bord et matrices¶
1. Création d'une matrice de zéros¶
Pour créer une liste de 0
on peut procéder par duplication:
liste = [0]*15
print(liste)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Malheureusement avec des listes de listes cela ne donne pas le résultat escompté:
N = [ [0]*4 ]*3
affiche(N)
[0, 0, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]
N[0][1] = 99 # on modifie le coefficient ligne 0 colonne 1
affiche(N)
[0, 99, 0, 0] [0, 99, 0, 0] [0, 99, 0, 0]
On pense ne modifier que la première ligne mais toutes les lignes ont été modifiées !!
Essayons avec une liste créée par compéhension:
M = [ [ 0 for j in range(4) ] for i in range(3) ]
M[0][1] = 99
affiche(M)
[0, 99, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]
Cette fois tout va bien on n'a modifié qu'un seul coefficient.
L'explication est que Python a fait pointer toutes les lignes vers la même adresse:
id(N[0]), id(N[1]), id(N[2]) # on affiche un tuple de 3 valeurs
(139813578520576, 139813578520576, 139813578520576)
Alors qu'avec la création par compréhension chaque ligne pointe sur une adresse différente:
id(M[0]), id(M[1]), id(M[2]) # on affiche un tuple de 3 valeurs
(139813578573440, 139813578553984, 139813578574208)
Nous n'entrerons pas dans les détails mais il n'était pas possible de ne pas mettre en lumière cette difficulté qui peut être source de nombreux bugs. Vous avez simplement à retenir que pour créer une matrice il ne faut pas procéder par duplication mais par compréhension.
2. Effets de bord¶
Pour terminer rappelons que les listes en Python peuvent être modifiées par une fonction dont elles sont l'argument: on parle d'effet de bord. En effet la fonction ne reçoit pas la valeur de variable en argument mais son adresse mémoire, ce qui lui permet de modifier la valeur stockée dans la variable.
On peut faire l'analogie avec une bibliothèque:
- si on emprunte une photocopie d'un livre et qu'on l'annote ou qu'on arrache une page, cela ne modifie pas le livre original,
- si on emprunte le livre original alors toute modification faite sur ce livre sera irréversible: c'est dans ce cas qu'on parle d'effet de bord.
Par exemple le programme suivant donne la valeur $99$ au coefficient ligne $0$ colonne $0$:
def prog1(Mat):
Mat[0][0] = 99
#cette fonction ne renvoie rien puisqu'il n'y pas de return!
# (en fait Python lui fait faire return None)
A = [ [3, 1, 6, -1] , [-1, 1, 2, 1] , [0, 7, 4, -2] ] # affectation
prog1(A)
# insistons sur le fait qu'on ne doit pas exécuter A = prog1(A) puisque la fonction prog1() renvoie None
affiche(A) # A a bien été modifiée par "effet de bord"
[99, 1, 6, -1] [-1, 1, 2, 1] [0, 7, 4, -2]
B = prog1(A) # on vérifie que la fonction prog1 renvoie None
print(B)
None
Q11. Ecrire une fonction Permutation(Mat, i, j)
qui prend en argument une matrice Mat
et échange ses lignes ${\tt L_i}$ et ${\tt L_j}$.
La matrice Mat
doit être modifiée par effets de bord.
Cette fonction ne renvoie rien.
Q12. Ecrire une fonction Dilatation(Mat, i, c)
qui prend en argument une matrice Mat
et multiplie les coefficients de la ligne ${\tt L_i}$ par c
.
La matrice Mat
doit être modifiée par effets de bord.
Cette fonction ne renvoie rien.
Q13. Ecrire une fonction Transvection(Mat, i, j, c)
qui prend en argument une matrice Mat
et remplace la ligne ${\tt L_i}$ par ${\tt L_i+cL_j}$.
La matrice Mat
doit être modifiée par effets de bord.
Cette fonction ne renvoie rien.
Q14. Utiliser ces fonctions dans un script pour triangulariser la matrice [[3, -1, 6, -1], [-1, 1, 2, 1], [2, 7, 4, -2]]
avec l'algorithme de Gauss.