 | Recherche Bioinformatique |
 |
 |
 |
 |
 |
 |
 |
Programmation Dynamique
Suite de Fibonacci
Prenons l'exemple de la suite de Fibonacci de manière à montrer comment l'utilisation d'un tableau de valeurs qui stocke les calculs intermédiaires permet d'améliorer l'efficacité d'un algorithme.La suite de Fibonacci est donnée par la formule récurrente :
- Fib(0) = 0
- Fib(1) = 1
- Fib(0) = Fib(n-1) + Fib(n-2)
| Algorithme 1 |
Fonction Fib1(n : entier) : entier debut si n <= 1 alors retour n; retour Fib1(n-1) + Fib1(n-2); fin |
| Algorithme récursif pour le calcul de la suite de Fibonacci |
Cet algorithme n'est pas efficace car il effectue les mêmes calculs de manière répétitive :
 |
Sur cet exemple on voit que pour calculer Fib(6),
il faut calculer Fib(5) puis Fib(4). Or, lors du calcul de Fib(5)
on évalue déjà Fib(4). On calculera donc 2 fois Fib(4). |
| Exemple de calcul pour Fibonacci de 6 |
Pour améliorer l'efficacité du calcul on peut envisager une solution qui enregistre dans un tableau les valeurs de Fib(n) une fois calculées. Ce tableau est initialisé à 0. Une valeur tab[i] à 0 signifie que Fib(i) n'a pas encore été calculée :
| Algorithme 2 |
Fonction Fib2(n : entier) : entier debut si n = 0 alors retour 0; si tab[n] != 0 alors retour tab[n]; tab[n] = Fib1(n-1) + Fib1(n-2); retour tab[n]; fin |
|
Algorithme récursif pour le calcul de la suite de Fibonacci avec stockage des valeurs intermédiaires dans un tableau |
Enfin une dernière amélioration peut être apportée à l'algorithme précédent en remarquant qu'il suffit d'évaluer Fib(n) dans l'ordre croissant des n :
| Algorithme 3 |
Fonction Fib3(n : entier) : entier
debut
tab[0] = 0;
tab[1] = 1;
pour i = 2 à n faire
tab[i] = tab[i-1] + tab[i-2];
fpour
retour tab[n];
fin
|
| Algorithme pour le calcul de la suite de Fibonacci avec calcul progressif |
L'implantation en langage C des algorithmes et leur exécution sur machine nous permet d'obtenir le tableau de résultats suivants :
| n | Fib1 | Fib2 ou 3 |
 | ||
| 10 | 1s < | 1s < |
| 20 | 1s < | 1s < |
| 30 | 1s < | 1s < |
| 40 | 10s | 1s < |
| 50 | 20m | 1s < |
| 60 | 42h27m | 1s < |
| Temps d'exécution sur serveur Helios | ||