L'avantage d'utiliser un tableau est en fait celui de la Réification, on ne traite plus une méthode de calcul mais des valeurs. Par exemple si on veut tracer les courbes qui correspondent à la suite pour un n fixé, un nombre énorme de calculs seront refait plusieurs fois, alors qu'en ayant enregistré toutes les étapes intermédiaires, on ne refait jamais deux fois le même calcul, et le tableau se calcule en temps linéaire par rapport à sa taille.
Oui, c'est une manière comme une autre d'allouer sur le tas (en l'occurrence ici dans une matrice) ce qui autrement resterait dans la pile d'appel à chaque calcul de la fonction, ce qui revient à faire de la mémoïsation.
Pour le rapport avec la preuve de la correction d'algorithme et la théorie de la démonstration, voir par exemple le livre Categorical semantics of linear logic aux pages 11-13 sur l'élimination des coupures.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Programmation Dynamique
Posté par kantien . En réponse au journal Haskell -- Évaluation paresseuse. Évalué à 1. Dernière modification le 26 mai 2016 à 00:19.
Oui, c'est une manière comme une autre d'allouer sur le tas (en l'occurrence ici dans une matrice) ce qui autrement resterait dans la pile d'appel à chaque calcul de la fonction, ce qui revient à faire de la mémoïsation.
À l'inverse, dans certain cas, on peut vouloir éviter ce genre d'allocation pour gagner du temps de calcul lorsque l'on n'a pas besoin de réutiliser ultérieurement les données produites (traitement en flux) :
transformation CPS et réification de la pile d'appel
éviter les allocations en utilisant le paradigme Continuation Passing Style
Pour le rapport avec la preuve de la correction d'algorithme et la théorie de la démonstration, voir par exemple le livre Categorical semantics of linear logic aux pages 11-13 sur l'élimination des coupures.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.