L’objectif de cette activité n'est pas d'étudier la suite de Fibonacci, mais plutôt d’implémenter plusieurs algorithmes de calcul du $n$-ème terme de cette suite, et de les comparer entre eux (notamment leur complexité algorithmique “théorique” et leur performance en pratique). On verra au passage que se posent plusieurs problèmes de temps de calcul et de fiabilité des résultats.
Dans cette première partie, nous allons étudier les algorithmes les plus simples permettant de calculer un terme de rang donné de la suite de Fibonacci, et discuter leur complexité. On rappelle avant tout la définition de la suite de Fibonacci :
\begin{cases} f_0 = 0,\\ f_1 = 1,\\ f_n = f_{n-1}+f_{n-2} \text{ pour } n \geq 2. \end{cases}1) Dans le TP 3, vous avez déjà écrit une version récursive pour $f_n$. Reprenez ce code ici.
Rappel : cette fonction doit effectuer deux appels récursifs.
def fiboNaif(n):
if n < 2:
return n
else:
return fiboNaif(n-1)+fiboNaif(n-2)
print(fiboNaif(10))
print(fiboNaif(30))
2) Expérimentez un peu avec cette fonction. Essayez de calculer $f_n$ pour des valeurs croissantes de $n$. Qu'observez-vous ? Déterminez l'ordre de grandeur du plus grand rang $n$ tel qu'on puisse calculer en environ une seconde le terme $f_n$ à l'aide de cette fonction.
On peut observer qu'au dessus de 30 le code met plus d'une seconde a calculer le terme fn.
Essayons de comprendre pourquoi ce calcul est aussi inefficace. On se doute vaguement que le fait que fibo_naif(n) s'appelle elle-même deux fois pour calculer le résultat risque de provoquer beaucoup de calculs, mais combien exactement ?
3) Modifiez la fonction fiboNaif afin qu'elle renvoie, en plus de son résultat, le nombre d'additions effectuées pour le calculer.
Indication : on peut renvoyer deux valeurs a et b en écrivant dans une fonction return a, b. Si une fonction renvoie deux résultats, on peut également les récupérer en écrivant par exemple x, y = ma_fonction(...).
def fiboNaifComptage(n):
if n<2:
return n, 0
n1, cpt1 = fiboNaifComptage(n-1)
n2, cpt2 = fiboNaifComptage(n-2)
return n1+n2,cpt1+cpt2+1
print(fiboNaifComptage(10))
print(fiboNaifComptage(20))
print(fiboNaifComptage(30))
En modifiant la fonction pour qu'elle calcule simultanément $f_n$ et $f_{n-1}$, on peut rendre le calcul bien plus efficace. En effet, si ces deux termes sont connus, il est très simple de calculer $f_{n+1}$.
4) On reprend également votre travail du TP 3. Recopiez ici la fonction fiboCouple du TP3.
Rappel : cette fonction est une modification de fiboNaif pour qu'un appel avec le paramètre $n$ renvoie le couple d'entiers $(f_n, f_{n-1})$.
def fiboCouple(n):
if n<2:
return n, 0
dern, av_dern = fiboCouple(n-1)
return (dern+av_dern,dern)
print(fiboCouple(1))
print(fiboCouple(11))
5) Que pensez-vous de l'efficacité de cette fonction par rapport à la fonction naïve ? Essayez de déterminer l'ordre de grandeur du plus grand rang $n$ tel qu'on puisse calculer en environ une seconde le terme $f_n$ à l'aide de cette fonction. Que constatez-vous ?
Cette fonction semble beaucoup plus efficace que la fonction naîve car jusqu'au rang 975 la reponse au code est pratiquement instantané car apres elle depasse la pile qui est normalement parametré sur 1000.
6) Combien d'additions l'appel fiboCouple(n) effectue-t-il ?
La fonction effectue n-1 addition
On veut implémenter la même idée que dans la solution précédente, mais cette fois de manière itérative. À l’aide de deux variables, on mémorisera à tout moment les valeurs des deux derniers termes connus de la suite.
7) Reprenez la fonction fiboIteratif du TP 3. N'oubliez pas de vérifier les résultats des calculs en les comparant à ceux des fonctions précédentes.
def fiboIteratif(n):
if n<2:
return n
av_dern,dern=0,1
for rang in range(2, n+1):
x=dern
dern=av_dern+dern
av_dern=x
return dern
print(fiboIteratif(11))
print(fiboIteratif(20))
print(fiboIteratif(100))
8) Calculez $f_n$ grâce à cette fonction pour diverses valeurs de $n$. Qu'observez-vous ? Combien d'additions sont faites à chaque fois ?
On remarque que la reponse et tres rapide. Il y a n-1 additions qui correspondent au nombres de repetion de la boucle.
Avant de pouvoir implémenter une fonction de calcul de la suite de Fibonacci à l’aide des nombres flottants, nous nous dotons de plusieurs fonctions calculant la puissance entière d’un nombre flottant.
On souhaite écrire une fonction calculant une valeur proche de $a^n$ pour un nombre réel $a$ et un nombre entier positif $n$ donnés. Pour cela, on se munit des définitions suivantes de $a^n$ :
Définition 1 :
$a^n=\begin{cases} a*a^{n-1} & \mbox{ si $n>0$},\\ 1 & \mbox{ si $n=0$}. \end{cases}$
Définition 2 (où $\lfloor x \rfloor$ désigne la partie entière de $x$) :
$a^n=\begin{cases} (a^{\lfloor n/2\rfloor})^2 & \mbox{ si $n>0$ est pair},\\ a*(a^{\lfloor n/2\rfloor})^2 & \mbox{ si $n$ est impair},\\ 1 & \mbox{ si $n=0$}. \end{cases}$
9) Programmez deux fonctions implémentant chacune de ces deux définitions, puis évaluez leur complexité asymptotique.
def puissanceLente(a, n):
if n==0:
return 1
return a*puissanceLente(a,n-1)
def puissanceRapide(a, n):
if n==0:
return 1
elif n%2==0:
return (a**(n//2))**2
else :
return a*(a**(n//2))**2
print(puissanceLente(4,5))
print(puissanceRapide(5,6))
On peut donner une expression fonctionnelle du terme $f_n$ (c’est-à-dire non récursive mais dépendant uniquement de $n$) par une analyse mathématique de la suite. En résolvant le polynôme caractéristique de cette suite (récurrente d’ordre 2), on peut déterminer que ses termes sont de la forme
$$ f_n = \frac{1}{\sqrt{5}} (\varphi^n - {\varphi'}^n) \qquad \text{ avec } \qquad \varphi = \frac{1 + \sqrt{5}}{2} \quad \text{et} \quad \varphi' = \frac{1 - \sqrt{5}}{2}. $$$\varphi$ est appelé le nombre d’or.
Comme $\varphi^n$ tend vers $+\infty$ et $\varphi'^n$ vers 0 quand $n$ tend vers $+\infty$, le second terme de cette expression devient négligeable à partir d’un certain rang (en fait dès $n = 1$), et on peut calculer $f_n$ simplement en arrondissant $\frac{1}{\sqrt{5}} \varphi^n$ à l’entier le plus proche. Cela nous fournit un nouveau moyen pour calculer $f_n$ efficacement.
10) Implémentez deux versions de cet algorithme, l'une utilisant la fonction puissance_lente, la seconde puissance_rapide.
from math import sqrt
def puissanceLente(a, n):
if n==0:
return 1
return a*puissanceLente(a,n-1)
def fiboPhiLent(n):
return ((1/sqrt(5))*(puissanceLente((1+sqrt(5))/2, n)-puissanceLente(((1-sqrt(5))/2), n)))
print(fiboPhiLent(10))
print(fiboPhiLent(20))
print(fiboPhiLent(30))
def puissanceRapide(a, n):
if n==0:
return 1
elif n%2==0:
return (a**(n//2))**2
else :
return a*(a**(n//2))**2
def fiboPhiRapide(n):
return ((1/sqrt(5))*(puissanceRapide((1+sqrt(5))/2, n)-puissanceRapide(((1-sqrt(5))/2), n)))
print(fiboPhiRapide(10))
print(fiboPhiRapide(20))
print(fiboPhiRapide(30))
11) Quelle est d'après vous leur complexité algorithmique ? D'après vous, ces fonctions présentent-elles toutes les deux un gain en efficacité par rapport à la fonction fiboIteratif ?
Les complexités de l'algorithme fibophirapide et fibophilente sont respectivement les compléxités des algorithmes puissanceRapide et puissanceLente qui sont de O(n) et en O(logarithme en base 2 de n).
Tout a l'air de bien se passer, mais nous n'avons pas encore une idée claire des différences d'efficacité entre ces deux fonctions. Pour tenter d'y voir plus clair, calculons les résultats obtenus pour des valeurs plus grandes de $n$.
12) Calculez à l'aide de ces deux fonctions, ainsi qu'avec la fonction fiboIteratif, le terme $f_{10\,000}$. Quel problème constatez-vous ? À quel rang $n$ ce problème apparait-il ?
13) Calculez à l'aide de ces deux fonctions, ainsi qu'avec la fonction fiboIiteratif, le terme $f_{100}$. Quel problème constatez-vous ? À quel rang $n$ ce problème apparait-il ?
On a vu que le passage par les nombres flottants, malgré une performance très bonne, posait d’autres problèmes. Comment faire pour calculer $f_n$ avec précision pour une grande valeur de $n$ ?
La définition de la suite de Fibonacci peut se reformuler selon l'équation matricielle suivante pour $n \geq 2$ :
$$\left(\begin{array}{c}f_{n}\\f_{n-1}\end{array} \right) = \left(\begin{array}[c]{cc} 1 & 1\\ 1 & 0 \end{array}\right) \times \left(\begin{array}{c}f_{n-1}\\f_{n-2}\end{array} \right) $$où on a bien sûr toujours $f_0 = 0$ et $f_1 = 1$. On peut facilement en déduire l’égalité suivante (toujours pour $n \geq 2$) :
$$ \left(\begin{array}[c]{cc} 1 & 1\\ 1 & 0 \end{array}\right)^{n-1} =\ \ \left(\begin{array}[c]{cc} f_n & f_{n-1}\\ f_{n-1} & f_{n-2} \end{array}\right)$$En Python, manipuler une matrice peut se faire à l'aide de listes imbriquées (ou listes de listes). Par exemple, la matrice ci-dessus peut s'écrire [[1,1],[1,0]]. D'autre part, pour récupérer ou modifier la valeur de l'élément $(i, j)$ (ligne $i$, colonne $j$) de la matrice, on écrira : m[i][j] (j-ème élément de la i-ème liste).
La fonction ci-dessous (qui vous est donnée) calcule la matrice produit de deux matrices carrées de dimension 2.
def produit2x2(m1, m2):
return [[m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0],
m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]],
[m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0],
m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]]]
print(produit_2x2([[1,1],[1,0]],[[1,1],[1,0]]))
print(produit_2x2([[2,1],[1,1]],[[1,1],[1,0]]))
14) À l’aide de cette fonction, écrivez une fonction calculant la puissance $n$-ème rapide de la matrice $2 \times 2$ .
Rappel :
$$ \left( \begin{array}[c]{cc} a & b\\ c & d \end{array} \right)^0 =\ \left( \begin{array}[c]{cc} 1 & 0\\ 0 & 1 \end{array} \right). $$def puissance2x2(mat, n):
...
15) À l’aide de cette fonction, écrivez une fonction calculant $f_n$.
def fiboMat(n):
...
16) Comparez les résultats et les performances de cette fonction avec les précédentes. À partir de quel rang la fonction est-elle plus rapide que la fonction fiboIteratif ?
17) Exprimez la complexité asymptotique de cette fonction. Comment expliquez-vous que ses performances en pratique soient à ce point pires que toutes les autres fonctions ?