Livre_silo 30 août 2013 16:32 Page 165
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
165
6 – Notions de complexité et algorithmique sur les tableaux
Puis on initialise les éléments de t avec une double boucle qui parcourt tous les éléments
de m :
for j in range(p):
for i in range(n):
t[j][i] = m[i][j]
return t
Ici, on remplit t ligne par ligne, mais on aurait pu tout aussi bien la remplir colonne par colonne. Comme pour la création et la copie, on peut utiliser la notation par compréhension
pour réécrire la fonction transpose de la manière suivante :
def transpose(m):
n, p = dimensions(m)
return [[m[i][j] for i in range(n)] for j in range(p)]
Bien que cette seconde version soit plus concise que la première, elle n’est pas forcément
plus claire : en particulier, on ne voit pas facilement l’égalité T j,i = M i,j , alors qu’elle
est manifeste dans la première version. De manière générale, nous n’abuserons pas de la
notation par compréhension dans cet ouvrage.
6.5.5 Produit matriciel
On va terminer avec une opération courante, à savoir la multiplication de deux matrices
a et b. On commence par récupérer les dimensions des deux matrices et par vérifier leur
compatibilité, c’est-à-dire que le nombre de colonnes de a est égal au nombre de lignes
de b :
def mult_matrice(a, b):
n, p = dimensions(a)
q, r = dimensions(b)
assert q == p
On crée alors une nouvelle matrice c de dimensions (n, r), initialisée par 0, puis on effectue
le calcul :
c i,j =
p−1
∑
k=0
a i,k × b k,j
par une triple boucle sur les indices i, j et k :
c = creer_matrice(n, r, 0)
for i in range(n):
for j in range(r):
for k in range(p):
c[i][j] += a[i][k] * b[k][j]
return c
La structure de triple boucle de cette fonction montre clairement que sa complexité est
O(n × p × r). L’ exercice 6.33 propose de réécrire cette fonction à l’aide de la transposition
et du produit scalaire (sans en changer la complexité cependant).
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
165
6 – Notions de complexité et algorithmique sur les tableaux
Puis on initialise les éléments de t avec une double boucle qui parcourt tous les éléments
de m :
for j in range(p):
for i in range(n):
t[j][i] = m[i][j]
return t
Ici, on remplit t ligne par ligne, mais on aurait pu tout aussi bien la remplir colonne par colonne. Comme pour la création et la copie, on peut utiliser la notation par compréhension
pour réécrire la fonction transpose de la manière suivante :
def transpose(m):
n, p = dimensions(m)
return [[m[i][j] for i in range(n)] for j in range(p)]
Bien que cette seconde version soit plus concise que la première, elle n’est pas forcément
plus claire : en particulier, on ne voit pas facilement l’égalité T j,i = M i,j , alors qu’elle
est manifeste dans la première version. De manière générale, nous n’abuserons pas de la
notation par compréhension dans cet ouvrage.
6.5.5 Produit matriciel
On va terminer avec une opération courante, à savoir la multiplication de deux matrices
a et b. On commence par récupérer les dimensions des deux matrices et par vérifier leur
compatibilité, c’est-à-dire que le nombre de colonnes de a est égal au nombre de lignes
de b :
def mult_matrice(a, b):
n, p = dimensions(a)
q, r = dimensions(b)
assert q == p
On crée alors une nouvelle matrice c de dimensions (n, r), initialisée par 0, puis on effectue
le calcul :
c i,j =
p−1
∑
k=0
a i,k × b k,j
par une triple boucle sur les indices i, j et k :
c = creer_matrice(n, r, 0)
for i in range(n):
for j in range(r):
for k in range(p):
c[i][j] += a[i][k] * b[k][j]
return c
La structure de triple boucle de cette fonction montre clairement que sa complexité est
O(n × p × r). L’ exercice 6.33 propose de réécrire cette fonction à l’aide de la transposition
et du produit scalaire (sans en changer la complexité cependant).