Résumé du chapitre 15

  Itération


Nous avons constaté qu'une traduction naïve d'équations de récurrence aboutissait parfois à un programme inexpoitable. Afin de contourner ce problème, il est possible de passer par un autre algorithme résolvant le problème selon un processus itératif.

La constitution de cet algorithme nécessite l'établissement d'un invariant qui, comme son nom l'indique, est une propriété du calcul qui reste toujours vrai au cours de celui-ci. L'invariant permet également de prouver la correction de l'algorithme.

On peut construire le programme itératif à partir de la version naïve en ajoutant des paramètres permettant la mémorisation d'étapes intermédiaires du calcul, le principe étant de transférer les calculs non terminaux vers ces paramètres.

L'algorithme itératif est plus performant que le récursif, parfois en temps, touours en espace. Ces différences sont dues à un calcul de ``haut en bas'' de l'itératif plutôt que ``bas en haut'' du récursif.


next up previous
Next: Résumé du chapitre 16 Up: No Title Previous: Résumé du chapitre 14

Eric.Wegrzynowski
Thu Mar 20 13:58:10 MET 1997