De la théorie des graphes à l'optimisation · Chapitre 03

La mémoire au service du calcul

Programmation dynamique · Fibonacci

Et si un algorithme pouvait se souvenir de ses calculs ? Explorez la différence entre la récursion naïve, la mémoïsation et la construction itérative d'un tableau.

✦ Tester mes connaissances · QCM

⚡ Laboratoire Fibonacci

Modifiez le rang puis comparez les trois stratégies. Le nombre d'appels de la récursion naïve est calculé exactement sans exécuter des millions d'appels inutiles.

Valeur recherchée : F(10) = 55
Prêt à comparer les méthodes.
Récursion naïve—

Appels récursifs · croissance exponentielle

Mémoïsation top-down—

Appels récursifs avec cache

Bottom-up—

Additions effectuées · temps O(n)

📊 Comparaison du travail effectué

Pour comparer les méthodes, les barres représentent des opérations de nature différente : appels de fonction pour les deux méthodes récursives et additions pour la méthode itérative.

Naïve
—
Mémoïsation
—
Itérative
—
La mémoïsation évite de recalculer les sous-problèmes déjà résolus.

🧠 Construire le tableau, étape par étape

Les cases montrent les résultats intermédiaires F(0), F(1), …, F(n). Utilisez « Étape suivante » ou « Animer » pour voir la construction bottom-up.

Sélectionnez un rang et démarrez l'animation.

Rang iValeur F(i)Calcul / justification

📚 À retenir pour le partiel

Récursion naïve

F(n) = F(n−1) + F(n−2). Les mêmes valeurs sont recalculées. Temps Θ(φⁿ), avec φ ≈ 1,618 ; pile O(n).

Top-down

On conserve les résultats dans un cache et on ne résout chaque sous-problème qu'une fois. Temps O(n), mémoire O(n).

Bottom-up

On calcule F(0), F(1), puis les termes suivants. Temps O(n), tableau O(n), ou O(1) avec seulement deux variables.

Distinction importante : la mémoïsation est généralement une stratégie top-down avec cache ; la tabulation est une stratégie bottom-up. Les deux relèvent de la programmation dynamique. Les temps d'exécution en millisecondes sont volontairement omis : à ces tailles, ils dépendent fortement du navigateur et peuvent induire en erreur.