Inverser une suite finie $u_{n+1}~:=f(u_{n})$ en Temps $\times$ Espace optimal

Soit $u_{0}\ldots u_{p}$ une suite finie, avec $u_{i+1}:=f(u_{i})$. On suppose que le temps de calcul de $u_{i+k}$ \`a partir de $u_{i}$ est $k$. Inverser la suite consiste \`a calculer $u_{p}$ \`a partir de $u_{0}$, puis $u_{p-1}$, etc, jusqu'\`a $u_{0}$. \noindent Pendant les calculs, on dispose de $r$ registres pour stocker des valeurs interm\'ediaires des $u_{i}$ pour ensuite les utiliser pour acc\'el\'erer les calculs des valeurs suivantes de la suite. \noindent Pour un nombre de registres fix\'e $r$, on donne l'expression du temps de calcul minimal $T$ pour inverser la suite, ainsi qu'un algorithme le r\'ealisant. \noindent On discutera ensuite la valeur minimale du produit $r T$ lorsque $r$ varie, exp\'erimentalement et th\'eoriquement. \noindent Enfin, on discutera l'extension du probl\`eme aux arbres, et l'application \`a la diff\'erentiation automatique de programmes.