Corrigé
Algorithme récursif
La formule de récursion s'arrête dans deux cas possibles soit $k = 1$ (première récursion) soit $n - 1 = k$ deuxième récursion. On a alors deux conditions d'arrêts à regarder pour $1\leq k \leq n$ :
- soit $k = 0$ et $\binom{n}{0} = 1$
- soit $k = n$ et $\binom{n}{n} = 1$
Ce qui donne le code :
algorithme binom(n: entier, k: entier) → entier:
si (n == k) ou (k == 0):
rendre 1
sinon:
rendre binom(n-1, k-1) + binom(n - 1, k)
Comme $n$ diminue strictement et $1\leq k \leq n$ on se rapproche strictement de la condition d'arrêt, le programme s'arrête à chaque fois : c'est un algorithme.
L'équation de récursion donne, en fonction de n et k :
Or comme $C(n, n) = C(n, 0) = \mathcal{O}(1) \geq 1$, on a $C(n, k) \geq \binom{n}{k}$
Or :
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 exponentiel $\Omega(2^n)$.
Algorithme itératif
v1
Première version qui calcule toute la matrice triangulaire inférieure :
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 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, alorsligne
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)$
v2
On va créer un algorithme qui rend uniquement la dernière ligne de la matrice :
algorithme ligne_suivante(l: [entier]) → [entier]:
l2 ← un tableau d'entiers de taille l.longueur +1
l2[0] ← 1
l2[-1] ← 1
pour chaque i de [1, l2.longueur - 1[:
l2[1] ← 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 ← [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]:
m ← min(k, l.longueur + 1)
l2 ← un tableau d'entiers de taille m + 1
l2[0] ← 1
l2[-1] ← 1
pour chaque i de [1, m]:
l2[1] ← l[i] + l[i-1]
rendre l2
algorithme binom(n: entier, k:entier) → entier:
l ← [0]
répéter n fois:
l ← ligne_suivante(l, k)
rendre l[k]
Algorithme liste
fonction ligne_suivante(l: Liste<entier>, k: entier) → ∅:
si l.longueur + 1 < k:
l.append(1)
l[0] ← 1
l[-1] ← 1
de j=min(l.longueur -1, k)-1 à j=1 par pas de -1:
l[j] ← l[j] + l[j-1]
algorithme binom(n: entier, k:entier) → entier:
l ← Liste<entier>
l[0] ← 1
répéter n fois:
ligne_suivante(l, k)
rendre l[k]
L'algorithme devient joli, avec une seule boucle et un seul tableau.