Utilisation des Listes (Matrices)

1Representer une matrice par une liste de listes

Python n'a pas de type « matrice » natif : on represente une matrice par une liste de listes, chaque sous-liste etant une ligne. Cette representation est simple, mais elle a des pieges qu'il faut connaitre avant d'ecrire la moindre ligne de code.

A = [[1, 2, 3],
     [4, 5, 6]]        # matrice 2 x 3

n = len(A)             # 2 : nombre de lignes
p = len(A[0])          # 3 : nombre de colonnes
A[1][2]                # 6

A = [[0] * 3] * 2         # PIEGE : une seule ligne, referencee deux fois
A[0][0] = 9
print(A)                  # [[9, 0, 0], [9, 0, 0]]

A = [[0] * 3 for _ in range(2)]     # CORRECT
A[0][0] = 9
print(A)                  # [[9, 0, 0], [0, 0, 0]]

Constructions usuelles

def matrice_nulle(n, p):
    """Matrice n x p remplie de zeros."""
    return [[0] * p for _ in range(n)]

def identite(n):
    """Matrice identite d'ordre n."""
    return [[1 if i == j else 0 for j in range(n)] for i in range(n)]

def matrice_depuis(f, n, p):
    """Matrice de terme general a[i][j] = f(i, j)."""
    return [[f(i, j) for j in range(p)] for i in range(n)]

H = matrice_depuis(lambda i, j: 1 / (i + j + 1), 3, 3)     # matrice de Hilbert
assert identite(2) == [[1, 0], [0, 1]]

Parcours

A = [[1, 2, 3], [4, 5, 6]]
n, p = len(A), len(A[0])

# par indices : indispensable des qu'on modifie
for i in range(n):
    for j in range(p):
        A[i][j] *= 2

# par valeurs : quand on ne fait que lire
for ligne in A:
    for x in ligne:
        print(x, end=" ")

# une colonne
colonne_1 = [A[i][1] for i in range(n)]

# la diagonale d'une matrice carree
diagonale = [A[i][i] for i in range(min(n, p))]

B = A                              # alias : aucune copie
B = A[:]                           # copie SUPERFICIELLE : les lignes sont partagees !
B = [ligne[:] for ligne in A]      # copie correcte
import copy; B = copy.deepcopy(A)  # equivalent, plus general

Affichage lisible

def affiche(A, largeur=7, decimales=2):
    """Affiche une matrice en colonnes alignees."""
    for ligne in A:
        print(" ".join(f"{x:{largeur}.{decimales}f}" if isinstance(x, float)
                       else f"{x:{largeur}d}" for x in ligne))

affiche([[1, 20, 300], [4000, 5, 6]])

      1      20     300
   4000       5       6

2Operations matricielles et pivot de Gauss

Operations matricielles

def dimensions(A):
    """(nombre de lignes, nombre de colonnes)."""
    return len(A), (len(A[0]) if A else 0)

def somme(A, B):
    """A + B. Precondition : memes dimensions. Theta(np)."""
    n, p = dimensions(A)
    return [[A[i][j] + B[i][j] for j in range(p)] for i in range(n)]

def scalaire(k, A):
    """k.A"""
    n, p = dimensions(A)
    return [[k * A[i][j] for j in range(p)] for i in range(n)]

def transposee(A):
    """A^T : la ligne i devient la colonne i. Theta(np)."""
    n, p = dimensions(A)
    return [[A[i][j] for i in range(n)] for j in range(p)]

def produit(A, B):
    """A x B. Precondition : colonnes(A) = lignes(B). Theta(n m p)."""
    n, m = dimensions(A)
    m2, p = dimensions(B)
    assert m == m2, "dimensions incompatibles"
    C = [[0] * p for _ in range(n)]
    for i in range(n):
        for j in range(p):
            s = 0
            for k in range(m):
                s += A[i][k] * B[k][j]
            C[i][j] = s
    return C

A = [[1, 2], [3, 4]]
I = [[1, 0], [0, 1]]
assert produit(A, I) == A
assert transposee(transposee(A)) == A
assert produit([[1, 2, 3]], [[1], [2], [3]]) == [[14]]

Puissance rapide d'une matrice

def puissance(A, k):
    """A^k par exponentiation rapide. Theta(n^3 log k) au lieu de Theta(n^3 k)."""
    n = len(A)
    R = identite(n)
    P = [ligne[:] for ligne in A]
    while k > 0:
        if k % 2 == 1:
            R = produit(R, P)
        P = produit(P, P)
        k //= 2
    return R

# suite de Fibonacci par puissance de matrice
F = [[1, 1], [1, 0]]
assert puissance(F, 10)[0][1] == 55        # F(10) = 55

Systemes lineaires : le pivot de Gauss

def gauss(A, b):
    """Resout A x = b par elimination de Gauss avec pivot partiel.

    A : matrice carree n x n (non modifiee), b : liste de n reels.
    Renvoie la liste solution, ou None si la matrice est singuliere.
    """
    n = len(A)
    # matrice augmentee, copiee pour ne pas modifier les arguments
    M = [A[i][:] + [b[i]] for i in range(n)]

    for k in range(n):
        # 1. recherche du pivot de plus grande valeur absolue (stabilite numerique)
        imax = max(range(k, n), key=lambda i: abs(M[i][k]))
        if abs(M[imax][k]) < 1e-12:
            return None                      # colonne nulle : pas de solution unique
        M[k], M[imax] = M[imax], M[k]

        # 2. elimination sous le pivot
        for i in range(k + 1, n):
            f = M[i][k] / M[k][k]
            for j in range(k, n + 1):
                M[i][j] -= f * M[k][j]

    # 3. remontee (substitution arriere)
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        s = M[i][n] - sum(M[i][j] * x[j] for j in range(i + 1, n))
        x[i] = s / M[i][i]
    return x

A = [[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
b = [8, -11, -3]
x = gauss(A, b)
print([round(v, 10) for v in x])       # [2.0, 3.0, -1.0]

3Produit interactif, images et grilles

Matrices et images

Une image en niveaux de gris est exactement une matrice d'entiers de 0 (noir) a 255 (blanc). Les traitements du chapitre 19 sont donc des operations matricielles.

def negatif(img):
    """Inverse les niveaux de gris."""
    return [[255 - x for x in ligne] for ligne in img]

def rotation_90(A):
    """Rotation d'un quart de tour dans le sens horaire."""
    n, p = len(A), len(A[0])
    return [[A[n-1-i][j] for i in range(n)] for j in range(p)]

def symetrie_horizontale(A):
    return [ligne[::-1] for ligne in A]

A = [[1, 2], [3, 4]]
assert rotation_90(A) == [[3, 1], [4, 2]]
assert symetrie_horizontale(A) == [[2, 1], [4, 3]]

Grilles et voisinages

De nombreux problemes (jeu de la vie, labyrinthes, plus court chemin) manipulent une grille et les voisins d'une case. Le motif standard :

def voisins(A, i, j, diagonales=False):
    """Liste des coordonnees des voisins valides de la case (i, j)."""
    n, p = len(A), len(A[0])
    if diagonales:
        deplacements = [(-1,-1), (-1,0), (-1,1), (0,-1),
                        (0,1), (1,-1), (1,0), (1,1)]
    else:
        deplacements = [(-1,0), (1,0), (0,-1), (0,1)]
    res = []
    for di, dj in deplacements:
        i2, j2 = i + di, j + dj
        if 0 <= i2 < n and 0 <= j2 < p:       # test de bord INDISPENSABLE
            res.append((i2, j2))
    return res