Mémoïsation vs Tabulation : l'exemple simple

1. Le principe général : stocker pour ne pas recalculer

Avant d'examiner chaque approche, rappelons l'idée maîtresse. Face à un grand nombre de sous-problèmes identiques, la solution est de ne les résoudre qu'une seule fois. Pour cela, on utilise une structure de données (typiquement un tableau ou une table de hachage) pour stocker les résultats intermédiaires. La différence entre mémoïsation et tabulation réside dans la manière de remplir et d'utiliser cette structure.

La vidéo suivante introduit de manière très claire ces deux stratégies et leur application au calcul de la suite de Fibonacci.

Maintenant que vous avez une vue d'ensemble, nous allons disséquer et formaliser chaque approche.

2. L'approche descendante : la Mémoïsation

La mémoïsation est souvent la transition la plus naturelle depuis une fonction récursive. La logique est la suivante :

1. On conserve la structure d'appels récursifs de la solution naïve (d'où le terme top-down, on part du problème F(n) pour descendre vers les cas de base).
2. On ajoute un "cache" (mémoire), souvent un dictionnaire ou un tableau, pour stocker les résultats.
3. Au début de la fonction, on vérifie si le résultat pour l'entrée courante est déjà dans le cache.
   • Si oui, on le retourne directement, coupant court à toute branche récursive inutile.
   • Si non, on effectue le calcul récursif normalement.
4. Juste avant de retourner le résultat nouvellement calculé, on le stocke dans le cache pour un usage futur.

C'est une stratégie de "paresseux intelligent" : on ne calcule une valeur que si on en a besoin, et la première fois seulement.

Reprenons l'exemple du calcul de fib(n) :

• Sans mémoïsation, l'appel à fib(5) génère des appels redondants à fib(3), fib(2), etc.
• Avec mémoïsation, lorsque fib(4) est appelé la première fois (via fib(5)), il calcule et stocke fib(3) et fib(2). Plus tard, lorsque fib(5) appelle directement fib(3), le résultat est trouvé instantanément dans le cache.

Le gain en complexité est spectaculaire : on passe d'une complexité exponentielle $O({\varphi }^n)$ à une complexité linéaire $O(n)$, car chaque valeur de fib(k) pour k de 0 à n n'est calculée qu'une seule fois.

La vidéo suivante vous montre le code Python correspondant à cette approche, ainsi que la mesure de sa performance.

Pour une référence textuelle, le document ci-dessous présente une implémentation quasi-identique.

3. L'approche ascendante : la Tabulation

La tabulation adopte une philosophie différente. Au lieu de partir du haut et de descendre, elle part du bas et construit la solution étape par étape.

1. On identifie l'ordre dans lequel les sous-problèmes doivent être résolus (des plus petits aux plus grands).
2. On alloue une table (généralement un tableau) pour stocker les résultats des sous-problèmes.
3. On initialise la table avec les cas de base.
4. On parcourt la table de manière itérative, en remplissant chaque entrée à partir des valeurs déjà calculées (celles des sous-problèmes plus petits).

Pour Fibonacci, cela revient à faire ce que l'on ferait à la main :

• On crée un tableau fib de taille n+1.
• On initialise fib[0] = 0 et fib[1] = 1.
• On boucle de i = 2 à n, et pour chaque i, on calcule fib[i] = fib[i-1] + fib[i-2].

Cette approche est itérative et garantit que lorsque nous devons calculer fib[i], les valeurs fib[i-1] et fib[i-2] dont il dépend sont déjà disponibles dans notre table.

Reprenez la vidéo et le document pour voir les implémentations correspondantes.

4. Synthèse et Comparaison

Maintenant que vous comprenez les deux approches, il est crucial de savoir les comparer. C'est une question d'analyse algorithmique fine.

Le document suivant, plus théorique, offre une perspective mature et synthétique, particulièrement adaptée à votre niveau de préparation.

Résumons les points clés de la comparaison dans un tableau :

Terminologie pour l'agrégation : Il est important d'être précis. Souvent, le terme "programmation dynamique" est utilisé pour désigner l'approche ascendante (tabulation) par opposition à la mémoïsation. Cependant, on peut aussi considérer la programmation dynamique comme le paradigme général qui englobe ces deux techniques d'implémentation. Soyez prêt à clarifier le sens que vous donnez aux termes.

Conclusion

Vous avez maintenant les outils pour implémenter une solution de programmation dynamique de deux manières distinctes et pour analyser leurs compromis.

Points clés à retenir :

• La mémoïsation est une technique top-down qui optimise une fonction récursive en ajoutant un cache. Elle est intuitive mais limitée par la profondeur de la pile d'appels.
• La tabulation est une technique bottom-up qui résout les sous-problèmes de manière itérative dans un ordre prédéfini. Elle est souvent plus performante en pratique et n'a pas de limite de récursion.
• Le choix entre les deux dépend du problème : si tous les sous-problèmes doivent être résolus, la tabulation est souvent préférable. Si l'espace des sous-problèmes est vaste et que seule une petite partie est nécessaire, la mémoïsation peut être plus efficace.

Dans notre prochaine leçon, nous quitterons l'exemple unidimensionnel de Fibonacci pour aborder un problème classique en deux dimensions : la plus longue sous-séquence commune (LCS). Vous devrez alors formuler la relation de récurrence et implémenter la solution par tabulation, ce qui mettra en jeu une table à deux dimensions.