Utilisation des Listes (Matrices)

a) 3        (nombre de lignes)
b) 3        (nombre de colonnes)
c) 6
d) 9
e) [1, 4, 7]      premiere colonne
f) [1, 5, 9]      diagonale principale
g) [3, 5, 7]      antidiagonale
h) 45             somme de tous les coefficients

A[:] cree une nouvelle liste externe, mais dont les elements sont les memes objets-lignes. Modifier B[0][0] modifie donc A[0][0]. Seule la copie ligne par ligne [l[:] for l in A] isole completement les deux matrices.

def est_matrice(A):
    """Toutes les lignes ont-elles la meme longueur, non nulle ? Theta(n)."""
    return bool(A) and bool(A[0]) and all(len(l) == len(A[0]) for l in A)

def est_carree(A):
    """Theta(n)."""
    return est_matrice(A) and len(A) == len(A[0])

def est_symetrique(A):
    """A = A^T ? Theta(n^2), en ne parcourant que le triangle superieur."""
    if not est_carree(A):
        return False
    n = len(A)
    for i in range(n):
        for j in range(i + 1, n):
            if A[i][j] != A[j][i]:
                return False
    return True

def trace(A):
    """Somme des coefficients diagonaux. Theta(n)."""
    return sum(A[i][i] for i in range(len(A)))

def est_triangulaire_sup(A):
    """Tous les coefficients sous la diagonale sont-ils nuls ? Theta(n^2)."""
    n = len(A)
    for i in range(1, n):
        for j in range(i):
            if A[i][j] != 0:
                return False
    return True

assert est_symetrique([[1, 2], [2, 3]])
assert not est_symetrique([[1, 2], [0, 3]])
assert trace([[1, 2], [3, 4]]) == 5
assert est_triangulaire_sup([[1, 2], [0, 3]])
assert not est_matrice([[1, 2], [3]])

Dans est_symetrique, la boucle interne demarre a i+1 : tester \(a_{i,j}\) et \(a_{j,i}\) puis \(a_{j,i}\) et \(a_{i,j}\) serait redondant. On divise ainsi le travail par deux (la complexite reste \(\Theta(n^2)\), mais la constante compte).

def transposee(A):
    """A^T, nouvelle matrice p x n. Theta(np)."""
    n, p = len(A), len(A[0])
    return [[A[i][j] for i in range(n)] for j in range(p)]

def transpose_en_place(A):
    """Transpose une matrice CARREE en place. Theta(n^2), Theta(1) memoire."""
    n = len(A)
    for i in range(n):
        for j in range(i + 1, n):        # triangle superieur strict uniquement
            A[i][j], A[j][i] = A[j][i], A[i][j]

M = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose_en_place(M)
assert M == [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

3. Une matrice \(n\times p\) devient \(p\times n\) : le nombre de lignes change, donc la structure meme de la liste de listes doit etre reconstruite. On ne peut pas se contenter d'echanger des coefficients. (En memoire lineaire contigue, comme en NumPy, la transposition en place existe mais requiert de suivre les cycles de la permutation d'indices — c'est nettement plus complexe.)

Noter aussi que si la boucle interne partait de 0 au lieu de i+1, chaque paire serait echangee deux fois et la matrice resterait inchangee.

import random
def produit(A, B):
    n, m, p = len(A), len(B), len(B[0])
    return [[sum(A[i][k]*B[k][j] for k in range(m)) for j in range(p)] for i in range(n)]

for _ in range(200):
    n, m, p = (random.randint(1, 4) for _ in range(3))
    A = [[random.randint(-5, 5) for _ in range(m)] for _ in range(n)]
    B = [[random.randint(-5, 5) for _ in range(p)] for _ in range(m)]
    assert transposee(produit(A, B)) == produit(transposee(B), transposee(A))
print("(AB)^T = B^T A^T verifie")

def identite(n):
    return [[1 if i == j else 0 for j in range(n)] for i in range(n)]

def produit(A, B):
    """A x B, avec verification des dimensions. Theta(n m p)."""
    n, m = len(A), len(A[0])
    if len(B) != m:
        raise ValueError(f"dimensions incompatibles : {n}x{m} et {len(B)}x{len(B[0])}")
    p = len(B[0])
    C = [[0] * p for _ in range(n)]
    for i in range(n):
        for k in range(m):
            a = A[i][k]
            if a:                      # petite optimisation : on saute les zeros
                for j in range(p):
                    C[i][j] += a * B[k][j]
    return C

def puissance(A, k):
    """A^k par exponentiation rapide. O(log k) produits matriciels."""
    R, P = identite(len(A)), [l[:] for l in A]
    produits = 0
    while k > 0:
        if k & 1:
            R = produit(R, P); produits += 1
        k >>= 1
        if k:
            P = produit(P, P); produits += 1
    return R, produits

A = [[0, 1], [1, 0]]
B = [[1, 1], [0, 1]]
assert produit(A, B) != produit(B, A)      # non commutativite

F = [[1, 1], [1, 0]]
R, nb = puissance(F, 50)
print(R[0][1], nb)          # 12586269025  et une dizaine de produits

La methode naive demanderait 49 produits matriciels ; l'exponentiation rapide en utilise \(\le 2\lfloor\log_2 50\rfloor + 1 = 11\). Pour \(k = 10^{18}\), on passe de \(10^{18}\) produits (impossible) a environ 120.

Verification : \(F_{50} = 12\,586\,269\,025\). L'ordre de la boucle i, k, j dans produit plutot que i, j, k ameliore la localite memoire : on parcourt B[k] et C[i] de facon contigue.

def compte_voisins(G, i, j):
    """Nombre de voisines vivantes parmi les 8 cases adjacentes."""
    n, p = len(G), len(G[0])
    c = 0
    for di in (-1, 0, 1):
        for dj in (-1, 0, 1):
            if di == 0 and dj == 0:
                continue
            i2, j2 = i + di, j + dj
            if 0 <= i2 < n and 0 <= j2 < p:
                c += G[i2][j2]
    return c

def generation(G):
    """Grille de la generation suivante. Theta(np)."""
    n, p = len(G), len(G[0])
    H = [[0] * p for _ in range(n)]
    for i in range(n):
        for j in range(p):
            v = compte_voisins(G, i, j)
            if G[i][j] == 1:
                H[i][j] = 1 if v in (2, 3) else 0
            else:
                H[i][j] = 1 if v == 3 else 0
    return H

def affiche(G):
    for ligne in G:
        print("".join("#" if x else "." for x in ligne))
    print()

# le planeur
G = [[0]*8 for _ in range(8)]
G[0][1] = G[1][2] = G[2][0] = G[2][1] = G[2][2] = 1

for etape in range(5):
    affiche(G)
    G = generation(G)

Apres 4 generations, le motif est identique mais decale d'une case en diagonale : c'est ce qui lui vaut son nom.

3. Les regles s'appliquent simultanement a toutes les cellules : chaque cellule doit etre evaluee d'apres l'etat de la generation precedente. Si l'on ecrivait dans G au fur et a mesure, les cellules traitees en fin de parcours verraient un voisinage deja partiellement mis a jour, et le resultat serait faux. Il faut donc une grille H distincte. C'est le motif du double tampon, universel en simulation.

def gauss(A, b, pivot_partiel=True):
    """Resout A x = b. Renvoie None si A est (numeriquement) singuliere."""
    n = len(A)
    M = [A[i][:] + [b[i]] for i in range(n)]
    for k in range(n):
        if pivot_partiel:
            imax = max(range(k, n), key=lambda i: abs(M[i][k]))
            M[k], M[imax] = M[imax], M[k]
        if abs(M[k][k]) < 1e-14:
            return None
        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]
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        x[i] = (M[i][n] - sum(M[i][j]*x[j] for j in range(i+1, n))) / M[i][i]
    return x

def determinant(A):
    """Determinant par elimination de Gauss. Theta(n^3)."""
    n = len(A)
    M = [l[:] for l in A]
    det, signe = 1.0, 1
    for k in range(n):
        imax = max(range(k, n), key=lambda i: abs(M[i][k]))
        if abs(M[imax][k]) < 1e-14:
            return 0.0
        if imax != k:
            M[k], M[imax] = M[imax], M[k]
            signe = -signe                 # chaque echange change le signe
        det *= M[k][k]
        for i in range(k + 1, n):
            f = M[i][k] / M[k][k]
            for j in range(k, n):
                M[i][j] -= f * M[k][j]
    return signe * det

A = [[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
x = gauss(A, [8, -11, -3])
assert all(abs(v - r) < 1e-9 for v, r in zip(x, [2, 3, -1]))
assert gauss([[1, 1], [2, 2]], [1, 2]) is None            # singuliere
assert abs(determinant([[1, 2], [3, 4]]) + 2) < 1e-12     # det = -2

3. Instabilite sans pivot. Considerons \[\begin{pmatrix} 10^{-18} & 1 \\ 1 & 1\end{pmatrix} \begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}1\\2\end{pmatrix},\] de solution exacte \(x \approx 1\), \(y \approx 1\).

A = [[1e-18, 1.0], [1.0, 1.0]]
b = [1.0, 2.0]
print(gauss(A, b, pivot_partiel=False))   # [0.0, 1.0]   FAUX
print(gauss(A, b, pivot_partiel=True))    # [1.0, 1.0]   correct

Sans pivot, le facteur vaut \(f = 1/10^{-18} = 10^{18}\). La deuxieme equation devient \(y(1 - 10^{18}) = 2 - 10^{18}\) : les termes \(1\) et \(2\) sont absorbes par les arrondis, on obtient \(y = 1\) puis, par remontee, \(x = (1 - y)/10^{-18} = 0\). Toute l'information de la premiere ligne a ete detruite.

4. L'elimination ne modifie pas le determinant (on ajoute a une ligne un multiple d'une autre), mais chaque echange de lignes le change de signe. A la fin, la matrice est triangulaire superieure et son determinant est le produit des pivots. D'ou \(\det A = (-1)^{\text{nb echanges}} \prod_k M_{k,k}\). Cette methode coute \(\Theta(n^3)\), a comparer aux \(n!\) termes du developpement par la formule de Leibniz : pour \(n=20\), \(8000\) operations contre \(2{,}4\cdot10^{18}\).

1. La somme de tous les coefficients vaut \(1 + 2 + \cdots + n^2 = \frac{n^2(n^2+1)}{2}\). Comme les \(n\) lignes ont toutes la meme somme \(S\) et partitionnent la matrice, \(nS = \frac{n^2(n^2+1)}{2}\), d'ou \(S = \frac{n(n^2+1)}{2}\). Pour \(n=3\) : \(S = 15\).

def est_magique(A):
    """A est-elle un carre magique ?"""
    n = len(A)
    if any(len(l) != n for l in A):
        return False
    if sorted(x for l in A for x in l) != list(range(1, n*n + 1)):
        return False
    S = n * (n*n + 1) // 2
    if any(sum(l) != S for l in A):
        return False
    if any(sum(A[i][j] for i in range(n)) != S for j in range(n)):
        return False
    if sum(A[i][i] for i in range(n)) != S:
        return False
    return sum(A[i][n-1-i] for i in range(n)) == S

def siamoise(n):
    """Carre magique d'ordre n impair (methode siamoise / de La Loubere)."""
    assert n % 2 == 1, "n doit etre impair"
    A = [[0] * n for _ in range(n)]
    i, j = 0, n // 2                    # milieu de la premiere ligne
    for k in range(1, n*n + 1):
        A[i][j] = k
        i2, j2 = (i - 1) % n, (j + 1) % n     # monter a droite, avec rebouclage
        if A[i2][j2] == 0:
            i, j = i2, j2
        else:
            i = (i + 1) % n             # case occupee : descendre
    return A

for n in (3, 5, 7, 9, 11):
    A = siamoise(n)
    assert est_magique(A), f"echec pour n = {n}"
print("carres magiques valides")

for ligne in siamoise(3):
    print(" ".join(f"{x:3}" for x in ligne))

  8   1   6
  3   5   7
  4   9   2

Les operations % n realisent le rebouclage : la grille se comporte comme un tore, ce qui evite tout test de bord. C'est l'un des rares cas ou le comportement « circulaire » des indices est voulu.

Complexite : \(\Theta(n^2)\), soit un temps constant par case — optimal.

1. Demonstration par recurrence sur \(k\).

Initialisation : pour \(k=1\), \((A^1)_{i,j} = a_{i,j}\) vaut 1 s'il existe un arc, c'est-a-dire un chemin de longueur 1, et 0 sinon.

Heredite : supposons que \((A^k)_{i,j}\) compte les chemins de longueur \(k\). Alors \[ (A^{k+1})_{i,j} = \sum_{l=1}^{n} (A^k)_{i,l}\, a_{l,j}. \] Tout chemin de longueur \(k+1\) de \(i\) a \(j\) se decompose de maniere unique en un chemin de longueur \(k\) de \(i\) vers un sommet intermediaire \(l\), suivi de l'arc \(l \to j\). Le terme \((A^k)_{i,l}\,a_{l,j}\) compte exactement les chemins passant par ce \(l\) en avant-dernier sommet ; la somme sur \(l\) les compte tous, sans repetition. D'ou le resultat.

2. Un chemin (s'il existe) peut toujours etre choisi sans repetition de sommet, donc de longueur \(\le n-1\). Il existe un chemin de \(i\) a \(j\) si et seulement si \(\bigl(A + A^2 + \cdots + A^{n-1}\bigr)_{i,j} > 0\). Le calcul coute \(n-2\) produits matriciels, soit \(\Theta(n^4)\) ; par exponentiation rapide sur \((I+A)^{n-1}\) on descend a \(\Theta(n^3\log n)\).

def roy_warshall(A):
    """Fermeture transitive de la matrice d'adjacence A. Theta(n^3)."""
    n = len(A)
    T = [[bool(A[i][j]) for j in range(n)] for i in range(n)]
    for k in range(n):                       # sommet intermediaire autorise
        for i in range(n):
            if T[i][k]:                      # petite optimisation
                for j in range(n):
                    if T[k][j]:
                        T[i][j] = True
    return [[1 if T[i][j] else 0 for j in range(n)] for i in range(n)]

# graphe 0 -> 1 -> 2 -> 3
A = [[0,1,0,0], [0,0,1,0], [0,0,0,1], [0,0,0,0]]
F = roy_warshall(A)
assert F[0] == [0, 1, 1, 1]
assert F[3] == [0, 0, 0, 0]

# verification par les puissances de matrice
def produit_bool(X, Y):
    n = len(X)
    return [[1 if any(X[i][k] and Y[k][j] for k in range(n)) else 0
             for j in range(n)] for i in range(n)]
import random
for _ in range(100):
    n = random.randint(1, 6)
    A = [[random.randint(0, 1) for _ in range(n)] for _ in range(n)]
    P, acc = A, [l[:] for l in A]
    for _ in range(n - 1):
        P = produit_bool(P, A)
        acc = [[1 if acc[i][j] or P[i][j] else 0 for j in range(n)] for i in range(n)]
    assert roy_warshall(A) == acc
print("Roy-Warshall valide")

3. Invariant. Notons \(T^{(k)}\) l'etat de la matrice apres les \(k\) premieres iterations de la boucle externe. L'invariant est :

\(T^{(k)}_{i,j}\) est vrai si et seulement s'il existe un chemin de \(i\) a \(j\) dont tous les sommets intermediaires appartiennent a \(\{0, \dots, k-1\}\).

• Initialisation : \(T^{(0)} = A\), et un chemin sans sommet intermediaire est exactement un arc. Vrai.
• Conservation : un chemin de \(i\) a \(j\) d'intermediaires dans \(\{0,\dots,k\}\) soit n'utilise pas \(k\) (il est deja compte dans \(T^{(k)}_{i,j}\)), soit l'utilise, et se decompose alors en un chemin de \(i\) a \(k\) puis de \(k\) a \(j\), tous deux d'intermediaires dans \(\{0,\dots,k-1\}\) : c'est le test T[i][k] and T[k][j]. La mise a jour realise donc exactement \(T^{(k+1)}_{i,j} = T^{(k)}_{i,j} \vee \bigl(T^{(k)}_{i,k} \wedge T^{(k)}_{k,j}\bigr)\).
• Conclusion : pour \(k = n\), tous les sommets sont autorises comme intermediaires : \(T^{(n)}_{i,j}\) vaut vrai si et seulement s'il existe un chemin de \(i\) a \(j\).

Subtilite : la mise a jour se fait en place, mais c'est sans danger car la ligne \(k\) et la colonne \(k\) ne changent pas pendant l'iteration \(k\) (on aurait \(T_{k,j} \vee (T_{k,k}\wedge T_{k,j}) = T_{k,j}\)).

4. Roy-Warshall est en \(\Theta(n^3)\) avec une constante minuscule (des tests booleens), contre \(\Theta(n^3\log n)\) et de l'arithmetique entiere pour les puissances. En revanche, les puissances de \(A\) donnent une information plus riche : le nombre de chemins de chaque longueur, et non seulement leur existence.