Triangle de Pascal

Cours/Algorithmie/Utilisation des listes/Triangle de Pascal

Formule du coefficient binomial dit du triangle de Pascal, avec $1\leq k \leq n$ :

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

et :

$$ \binom{n}{0} = \binom{n}{n} = 1 \text{ pour tout } n\geq 0 $$

Algorithme récursif

Après avoir examiné les conditions d'arrêt, donner un algorithme récursif naïf mimant l'équation de récurrence permettant de calculer le coefficient binomial.

Il devra être de signature : binom(n: entier, k: entier) → entier

Montrez que la complexité de l'algorithme binom est en $\Omega(\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} $$

En déduire que la complexité de notre algorithme est rédhibitoire.

Algorithme itératif

La récursion terminale ne fonctionne pas s'il y a, comme pour l'algorithme précédent, une double récursion. Mais on peut tout de même ici en donner une version itérative en utilisant des matrices.

V1

Créez un algorithme rendant une matrice triangulaire inférieure $B$ telle que $B[n][k] = \binom{n}{k}$.

Sa signature devra être :

algorithme binom_matrice(n: entier) → [[entier]]:

Vous pourrez créer itérativement chaque ligne en utilisant la ligne créé à l'itération précédente pour créer la ligne actuelle.

Utilisez l'algorithme 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é spatiale et temporelle.

V2

Comme l'algorithme binom_matrice(n: entier) → [[entier]] n'a besoin que de la ligne précédente pour créer la ligne de l'itération actuelle, on peut améliorer la complexité spatiale de l'algorithme binom(n: entier, k:entier) → entier :

Créez l'algorithme ligne_suivante(l: [entier]) → [entier] qui à partir de la liste $l= [\binom{n}{0}, \dots, \binom{n}{n}]$ rend la liste $[\binom{n+1}{0}, \dots, \binom{n+1}{n+1}]$

Donnez-en sa complexité spatiale et temporelle.

Utilisez l'algorithme ligne_suivante(l: [entier]) → [entier] pour améliorer la complexité spatiale de l'algorithme binom(n: entier, k:entier) → entier.

Enfin, pour calculer binom(n: entier, k:entier) → entier on a pas besoin de toute la ligne de la matrice :

Modifiez l'algorithme ligne_suivante pour le rendre de signature ligne_suivante(l: [entier], k: entier) → [entier] tel que si $l= [\binom{n}{0}, \dots, \binom{n}{\min(k, n)}]$ rend le tableau $[\binom{n+1}{0}, \dots, \binom{n+1}{\min(k, n+1)}]$.

Utilisez le dans binom(n: entier, k:entier) → entier pour que sa complexité spatiale soit en $\mathcal{O}(k)$.

Algorithme avec liste

Il faut 2 tableaux de taille au plus $k$ pour faire fonctionner l'algorithme précédent. On peut faire mieux !

On va ici utiliser des listes car on va chercher à modifier et à faire grandir le paramètre d'entrée, ce qu'on ne peut pas faire avec un tableau.

En remplissant la ligne courante de droite à gauche montrez que l'on peut modifier ligne_suivante pour le rendre de signature ligne_suivante(l: Liste<entier>, k: entier) → [entier] telle que si $l= [\binom{n}{0}, \dots, \binom{n}{\min(k, n)}]$ en entrée, elle est modifiée en la liste $[\binom{n+1}{0}, \dots, \binom{n+1}{\min(k, n+1)}]$.

Utilisez le dans binom(n: entier, k:entier) → entier.

Cette dernière optimisation ne change pas la complexité spatiale en $\mathcal{O}$, elle ne fait que la diminuer par 2. Cette optimisation est cependant significative si $k$ est grand.