Techniques de mémoïzation

Soit {E} un ensemble muni d’une relation d’ordre {\preceq (}partielle ou totale). On dit que {(E,\preceq )} est « bien fondé » si les conditions équivalentes suivantes sont vérifiées :

  • il n’existe pas de suite infinie strictement décroissante d’éléments de {E}
  • toute partie non vide {A} de {E} admet au moins un élément minimal {a,} c’est-à-dire tel que {\forall x\in A,(x\preceq a\Rightarrow x=a)}

Soit à calculer {f(x),} où {f} est une fonction et {x} un élément d’un ensemble {(E,\preceq )} bien fondé. La mémo ̈ization est une technique d’optimisation du code informatique qui consiste à stocker en mémoire, au moins provi- soirement, les résultats {f(x^{\prime })(}avec {x^{\prime }\preceq x)} qui sont utiles au calcul de la valeur {f(x).}

7.2.1 Retour aux coefficients du binôme

La fonction tpascal renvoie le triangle de Pascal (pour les lignes de 0 à {n)} sous la forme d’un tableau de tableau d’entiers.

On en déduit une fonction tcnp assez évidente de calcul de {\binom{n}{p}:} let tcnp n p = (tpascal n).(n).(p);;

Si on ne recherche que la ligne d’indice {n} du triangle de Pascal, on peut optimiser la complexité spatiale de la fonction tpascal. On écrit pour cela une fonction lpascal renvoyant seulement la ligne d’indice {n.} Dans la fonction lpascal, on notera (et on en comprendra la raison) que la boucle est de type downto.

On en déduit une fonction lcnp assez évidente de calcul de {\binom{n}{p}:} let lcnp n p = (lpascal n).(p);;

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :