Utilisation des listes

Première version qui calcule toute la matrice triangulaire inférieure :

algorithme binom_matrice(n: entier) → [[entier]]:
    matrice := [[entier]]
    matrice ← [[entier]]{longueur: n+1}

    ligne := [entier]
    pour chaque i de [0 .. n]:
        ligne ← [entier]{longueur: i+1} 

        matrice[i] ← ligne
        pour chaque j de [0 .. i]:
            si (j == i) ou (j == 0):
                ligne[j] ← 1
            sinon:
                précédent ← matrice[i-1]
                ligne[j] ← précédent[j-1] + précédent[j]

    rendre matrice

Il y a deux boucles imbriquées, donc deux invariants à trouver !

L'invariant de la boucle 4-13 peut être :

Invariant de la boucle 4-13 : matrice[i-1] contient la $i$ème ligne de la matrice triangulaire inférieure de Pascal.

Pour le prouver, il faut trouver un invariant à la boucle 8-13. Par exemple :

Invariant de la boucle 8-13 : si matrice[i-2] contient la $i-1$ème ligne de la matrice triangulaire inférieure de Pascal, alors ligne contient la $i$ème ligne de la matrice triangulaire inférieure de Pascal.

Ce dernier invariant est évidemment vrai par construction de la boucle (c'est la relation de récurrence). Une fois la boucle 8-13 prouvée, cela prouve l'invariant de la boucle 4-13.

On utilise alors l'algorithme précédent pour déterminer la binomiale :

algorithme binom(n: entier, k:entier) → entier:
    matrice ← binom_matrice(n)

    rendre matrice[n][k]

La complexité est en $\mathcal{O}(1)$ plus la complexité de la fonction binom_matrice(n: entier) → [[entier]].

En utilisant la règle de calcul de complexité sur les boucles dépendantes mais croissantes, cette complexité est en $\mathcal{O}(n^2)$.

On en déduit que la complexité de l'algorithme binom est en $\mathcal{O}(nk)$. Comme il faut de plus stocker toute la matrice triangulaire inférieure, sa complexité spatiale est en $\mathcal{O}(nk)$

On va créer un algorithme qui rend uniquement la dernière ligne de la matrice :

algorithme ligne_suivante(l: [entier]) → [entier]:
    (l2 := [entier]) ← [entier]{longueur: l.longueur +1}

    l2[0] ← 1
    l2[-1] ← 1

    pour chaque i de [1 .. l2.longueur - 1[:
        l2[i] ← l[i] + l[i-1]

    rendre l2

L'algorithme ligne_suivante(l: [entier]) → [entier] est correct si $l= [\binom{n}{0}, \dots, \binom{n}{n}]$ puisque on applique directement l'équation de récursion. Sa complexité spatiale et temporelle est en $\mathcal{O}(l.\text{\small longueur})$.

On a alors la version améliorée de binom(n: entier, k:entier) → entier :

algorithme binom(n: entier, k:entier) → entier:
    (l := [entier]) ← [0]
    répéter n fois:
       l ← ligne_suivante(l)

    rendre l[k]

Si la complexité temporelle ne change pas, la complexité spatiale est maintenant de $\mathcal{O}(l.\text{\small longueur})$.

On peut faire mieux en ne calculant que les $k+1$ premiers éléments de chaque ligne. Il faut pour cela modifier l'algorithme en créant une version alternative de ligne_suivante : ligne_suivante(l: [entier]) → [entier]

fonction ligne_suivante(l: [entier], k: entier) → [entier]:
    (l2 := [entier]) ← [entier]{longueur: min(k + 1, l.longueur + 1)}

    l2[0] ← 1
    l2[-1] ← 1

    pour chaque i de [1 .. l.longueur[:
        l2[i] ← l[i] + l[i-1]

    rendre l2

algorithme binom(n: entier, k:entier) → entier:
    (l := [entier]) ← [0]
    répéter n fois:
       l ← ligne_suivante(l, k)

    rendre l[k]

fonction ligne_suivante(l: [entier], n: entier, k: entier) → ∅:
    de j=min(n, k) à j=1 par pas de -1:
        l[j] ← l[j] + l[j-1]

algorithme binom(n: entier, k:entier) → entier:
    (l := [entier]) ← [entier]{longueur: k+1}
    l[:] ← 1

    pour j dans [0 .. n-1] fois:
       ligne_suivante(l, j, k)

    rendre l[k]

algorithme échiquier(n: entier) → [[booléen]]:
    (E := [[booléen]]) ← [[booléen]]{longueur: n}

    pour chaque i de [0 .. n[:
        E[i] ← [booléen]{longueur: n}
        E[:] ← Faux

    rendre E

On regarde les lignes, les colonnes et les diagonales. Il faut faire attention à :

• ne pas regarder la case (i, j)
• rester dans les bornes de l'échiquier

algorithme position_correcte(E: [[booléen]], i: entier, j: entier) → booléen:
    (n := entier) ← E.longueur
    k := entier

    pour k dans [0 .. n[:
        si (k ≠i) ET E[k][j]:
            rendre Faux

    pour k dans [0 .. n[:
        si (k ≠ j) ET E[i][k]:
            rendre Faux

    pour k dans [1 .. n[:
        si (i + k < n) ET (j + k < n) ET E[i + k][j + k]:
            rendre Faux
        si (i + k < n) ET (j - k > -1) ET E[i + k][j - k]:
            rendre Faux
        si (i - k > -1) ET (j + k < n) ET E[i - k][j + k]:
            rendre Faux
        si (i - k > -1) ET (j - k > -1) ET E[i - k][j - k]:
            rendre Faux
        
    rendre Vrai

Elle est en $\mathcal{O}(n)$ avec $n$ le nombre de lignes de l'échiquier.

algorithme échiquier_correct(E: [[booléen]]) → booléen:
    (n := entier) ← E.longueur

    pour (i:= entier) de [0 .. n[:
        pour (j:= entier) de [0 .. n[:
            si E[i][j] ET (NON position_correcte(E, i, j)):
                rendre Faux
        
    rendre Vrai

Elle est en $\mathcal{O}(n^2)$ avec $n$ le nombre de lignes de l'échiquier.

algorithme tous_les_échiquiers_rec(E: [[booléen]], i: entier):
    (n := entier) ← E.longueur

    si i ≥ n:
        si échiquier_correct(E):
            affiche E à l'écran
        rendre ∅
    pour (j := entier) de [0 .. n[:
        E[i][j] ← Vrai
        tous_les_échiquiers_rec(E, i+1)
        E[i][j] ← Faux

tous_les_échiquiers_rec(échiquier(n), 0)

▢ ♕ ▢ ▢     ▢ ▢ ♕ ▢
▢ ▢ ▢ ♕     ♕ ▢ ▢ ▢
♕ ▢ ▢ ▢     ▢ ▢ ▢ ♕
▢ ▢ ♕ ▢     ▢ ♕ ▢ ▢

Il génère tous les échiquiers possibles avec 1 reine par ligne, il y en a $n^n$ et les vérifient en $\mathcal{O}(n^2)$. Sa complexité est donc égale à $\mathcal{O}(n^2 \cdot n^n)$.

On peut le démontrer rigoureusement en résolvant l'équation de complexité satisfaite par l'algorithme, à savoir :

algorithme tous_les_échiquiers_rec(E: [[booléen]], i: entier):
    (n := entier) ← E.longueur

    si i ≥ n:
        affiche E à l'écran
        rendre ∅
    pour (j := entier) de [0 .. n[:
        
        si position_correcte(E, i, j):
          E[i][j] ← Vrai
          tous_les_échiquiers_rec(E, i+1)
          E[i][j] ← Faux

tous_les_échiquiers_rec(échiquier(n), 0)

On vérifie à chaque positionnement de reines en $\mathcal{O}(i)$, l'équation de complexité satisfaite par l'algorithme est alors :

On retrouve notre complexité de $\mathcal{O}(n^2 \cdot n^n)$.

Comme deux reines ne peuvent partager une même ligne ou une même colonne : chaque ligne et chaque colonne possèdent exactement une reine. Le tableau $P$ de longueur $n$ tel que $P[i]$ corresponde à l'indice de la colonne de la reine de la ligne $i$ est une permutation de [0, ..., n-1].

algorithme permutation_correcte(P: [entier], i:entier) → booléen:
    (n := entier) ← P.longueur

    pour (k:= entier) de [0 .. i[:
        si (0 ≤ P[i] - i + k < n) ET (P[i] - i + k == P[k]):
            rendre Faux
        si (0 ≤ P[i] + i - k < n) ET (P[i] + i - k == P[k]):
            rendre Faux
        
    rendre Vrai

Elle est clairement en $\mathcal{O}(n^2)$.

Si $P$ est une permutation et si les $i-1$ premières reines sont placées dans la permutation, les valeurs de $P[i:]$ contiennent toutes les positions restantes possible pour la reine que l'on doit placer à la ligne d'indice $i$. L'algorithme teste alors toutes les possibilités et ne continue que lorsqu'il a trouvé une position cohérente pour la reine de la ligne d'indice $i$.

On vérifie à chaque positionnement de reines en $\mathcal{O}(i)$, l'équation de complexité satisfaite par l'algorithme est alors :

On à alors $C(0) = \mathcal{O}(\sum_{0 \leq i \leq n} i!)$, donc

Ce résultat est très bon puisqu'a priori il faut considérer toutes les permutations et les vérifier, ce qui nous prendrait $\mathcal{O}(n^2\cdot n!)$ si on vérifiait uniquement à la fin !

algorithme création_matrice(n: entier, m: entier)  → [[entier]]:
    M := [[entier]]
    M  ← [[entier]]{longueur: n}
    pour i dans [0 .. m[:
        M[i] ← [entier]{longueur: m}
        M[i][:] ← 0

    rendre M

algorithme extraction_matrice(M: [[entier]], n1: entier, n2: entier, m1: entier, m2: entier)  → [[entier]]:
    C = création_matrice(n2-n1, m2-m1)
    pour chaque i de [n1, n2[:
        pour chaque j de [m1, m2[:
            C[i][j] = M[i][j]
    rendre C

algorithme somme(A: [[entier]], B: [[entier]])  → [[entier]]:
    C ← création_matrice(A.longueur, A[0].longueur)

    pour (i:= entier) dans [0 .. C.longueur[:
        pour (j:= entier) dans [0 .. C[0].longueur[:
            C[i][j] ← A[i][j] + B[i][j]
    rendre C

algorithme multiplication(A: [[entier]], B: [[entier]]) → [[entier]]:
    C ← création_matrice(A.longueur, B[0].longueur)

    pour (i:= entier) dans [0 .. C.longueur[:
        pour (j:= entier) dans [0 .. C[0].longueur[:
            pour k dans [0 .. B.longueur[:
                C[i][j] ← C[i][j] + A[i][k] * B[k][j]
    rendre C

Si $n$ est un entier, il existe $p$ tel que $ 2^{p-1} < n \leq 2^p$, donc $2^p\leq 2n$. Si $A$ est une matrice carrée à $n$ on peut alors créer la matrice $A'$ à $2^p$ lignes telles que :

Et on aura clairement $A \cdot B = (A' \cdot B')[:n][:n]$. Enfin, comme $A'$ a au pire 4 fois plus d'éléments que $A$, les complexités vont rester les même en $\Theta$.

algorithme multiplication_rec(A: [[entier]], B: [[entier]]) → [[entier]]:
    (n := entier) ← A.longueur

    Si n ≤ 1:
        rendre [[A[0][0] * B[0][0]]]
    
    (A11 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    A11[:][:] ← A[:n //2][:n //2]
    (A12 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    A12[:][:] ← A[:n //2][n //2:]
    (A21 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    A21[:][:] ← A[n //2:][:n //2]
    (A22 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    A22[:][:] ← A[n //2:][n //2:]

    (B11 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    B11[:][:] ← B[:n //2][:n //2]
    (B12 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    B12[:][:] ← B[:n //2][n //2:]
    (B21 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    B21[:][:] ← B[n //2:][:n //2]
    (B22 := [[entier]]) ← [[entier]{longueur: n // 2}]{longueur: n // 2}
    B22[:][:] ← B[n //2:][n //2:]

    (C11 := [[entier]]) ← somme(multiplication_rec(A11, B11), multiplication_rec(A12, B21))
    (C12 := [[entier]]) ← somme(multiplication_rec(A11, B12), multiplication_rec(A12, B22))
    (C21 := [[entier]]) ← somme(multiplication_rec(A21, B11), multiplication_rec(A22, B21))
    (C22 := [[entier]]) ← somme(multiplication_rec(A21, B12), multiplication_rec(A22, B22))

    (C := [[entier]]) ← [[entier]{longueur: n}]{longueur: n}
    C[:n // 2][:n // 2] ← C11[:][:]
    C[:n // 2][n // 2:] ← C12[:][:]
    C[n // 2]:[:n // 2] ← C21[:][:]
    C[n // 2:][n // 2:] ← C22[:][:]

    rendre C

L'équation de complexité est claire car toutes les opérations de création et de some sont en $\Theta(n^2)$ et qu'il y a 8 appels récursifs. En triturant cette équation on trouve que pour tout $i$ on a :

Et donc au final

Il faut une récursion pur chaque matrice M. Comme le reste des opérations est toujours en $\Theta(n^2)$, on obtient l'équation de récursion :

En triturant l'équation de récursion on obtient :

Et donc au final

L'astuce qui consiste à remarquer que $p^{\log_k(q)} = q^{\log_k(p)}$ est à garder sous le coude. Cela ne sert pas tout le temps, mais quand ça sert, ça sert.

1. On englobe les matrices à multiplier dans des matrices ayant comme dimensions des puissances de 2 en ligne et en colonne.
2. on stoppe la récursion lorsqu'une des dimensions vaut $2^0 = 1$ et on multiplie des vecteurs ligne ou colonne.