Triangle de Pascal

Cours/Algorithmie/Projet : calcul de complexité/Triangle de Pascal

Le calcul du coefficient binomial se fait en utilisant le triangle de Pascal.

Pour $n > p > 0$ :

$$ \binom{n}{k} = \binom{n-1}{k-1} \mathrel{+} \binom{n-1}{k} $$

et :

$$ \binom{n}{0} = \binom{n}{n} = 1 $$

Récursif

algorithme binom_rec(n: entier, k: entier) → entier:
    si (n == k) ou (k == 0):
        rendre 1
    sinon:
        rendre binom_rec(n-1, k-1) + binom_rec(n - 1, k)

Montrez que la complexité de l'algorithme binom_rec est en $\Omega(\binom{n}{k})$.

corrigé

L'équation de récursion donne, en fonction de n et k :

$$ \begin{array}{lcl} C(n, k) & = & \mathcal{O}(1) + C(n-1, k-1) + C(n-1, k) \\ &\geq&C(n-1, k-1) + C(n-1, k)\\ \end{array} $$

Or comme $C(n, n) = C(n, 0) = \mathcal{O}(1) \geq 1$

que $C(n, k) \geq \binom{n}{k}$

Nous allons montrer que cette complexité est rédhibitoire pour la plupart des calculs.

Montrez que pour $n \geq 1$:

$$ \begin{array}{lcl} \binom{2n}{n} & \geq & 2^{n}\\ \end{array} $$

corrigé

$$ \begin{array}{lcl} \binom{2n}{n} & = & \binom{2n-1}{n-1} + \binom{2n-1}{n}\\ && \binom{2n-2}{n-2} + \binom{2n-2}{n-1} + \binom{2n-1}{n}\\ &\geq & \binom{2n-2}{n-1} + \binom{2n-1}{n}\\ &\geq & \binom{2n-2}{n-1} + \binom{2n-2}{n-1} + \binom{2n-2}{n}\\ &\geq & 2\cdot\binom{2n-2}{n-1}\\ &\geq & \dots \\ &\geq & 2^k\cdot\binom{2(n-k)}{n-k}\\ &\geq & 2^{n}\cdot\binom{n}{0} \end{array} $$

En déduire que cette complexité est rédhibitoire dans le cas le pire.

corrigé

Comme la complexité du calcul récursif de $\binom{n}{k}$ est en $\Omega(\binom{n}{k})$, le calcul de $\binom{2n}{n}$ va prendre un temps de calcul $\Omega(2^n)$, ce qui est exponentiel.

Itératif v1

algorithme binom_matrice(n: entier) → [[entier]]:
    matrice ← un tableau de [entier] de taille n+1

    pour chaque i de [0, n]:
        ligne ← un tableau d'entiers de taille i+1

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

    rendre matrice

Utilisez la fonction binom_matrice(n: entier) → [[entier]] pour créer l'algorithme itératif de signature :

algorithme binom(n: entier, k:entier) → entier

calculant $\binom{n}{k}$.

Donnez-en sa complexité.

corrigé

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

    rendre matrice[n-1][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}(n^2)$

Itératif v2

Modifier l'algorithme précédent pour donner un algorithme itératif de complexité $\mathcal{O}(nk)$ pour calculer $\binom{n}{k}$.

corrigé

On a pas besoin de toute la matrice triangulaire inférieure, on peut se restreindre à ne calculer que les k première colonnes :

algorithme binom_matrice2(n: entier, k: entier) → [[entier]]:
    matrice ← un tableau de [entier] de taille n+1

    pour chaque i de [0, n]:
        ligne ← un tableau d'entiers de taille i+1

        matrice[i] ← ligne
        pour chaque j allant de 0 à min(i, k):
            si (j == i) ou (j == 0):
                ligne[j] ← 1
            sinon:
                précédent ← matrice[i-2]
                ligne[j] ← précédent[j-1] + précédent[j]

    rendre matrice

La complexité de la fonction binom_matrice2 est clairement en $\mathcal{O}(nk)$ puisque la boucle intérieure ne fera jamais plus de $k$ itérations.

de là, l'algorithme suivant est aussi de complexité $\mathcal{O}(nk)$ :

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

    rendre matrice[n-1][k]

La complexité est maintenant maîtrisée, mais la complexité spatiale est aussi en $\mathcal{O}(nk)$. On peut faire mieux car pour calculer la $i$ème ligne de la matrice triangulaire inférieure de Pascal on a uniquement besoin de la ligne précédente.

Modifier l'algorithme précédent pour donner un algorithme itératif de complexité $\mathcal{O}(nk)$ pour calculer $\binom{n}{k}$ et de complexité spatiale $\mathcal{O}(k)$

corrigé

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

algorithme binom_ligne(n: entier, k: entier) → [[entier]]:
    courante ← un tableau d'entiers de taille k+1
    précédente ← un tableau d'entiers de taille k+1

    pour chaque i de [0, n]:
        pour chaque j allant de 0 à min(i, k):
            précédente[j] ← courante[j]

        pour chaque j allant de 0 à min(i, k):
            si (j == i) ou (j == 0):
                courante[j] ← 1
            sinon:
                ligne[j] ← précédent[j-1] + précédent[j]

    rendre matrice

Sachez que l'on peut encore faire mieux en utilisant qu'un seul tableau auxiliaire (la deuxième boucle devant aller de $min(i, k)$ à 0) ce qui divise par deux la complexité spatiale (mais qui reste en $\mathcal{O}(k)$).