Terminaison d'un algorithme
La terminaison d'un algorithme désigne le fait qu'il termine ou pas, c'est-à-dire qu'il existe un moment où le calcul s'arrête ou pas. Le plus souvent on souhaite qu'un algorithme s'arrête et donne une sortie, on doit alors s'assurer de sa terminaison.
Un cas particulier est la terminaison d'un système de réécriture.
Méthode de preuve de terminaison
L'une des méthodes classiques pour prouver la terminaison d'un algorithme, est de définir une fonction, parfois appelée fonction de terminaison[1], qui satisfait les conditions suivantes. Elle a pour variables, les variables du programme, elle décroît pendant l'exécution et elle est à valeur dans un ensemble bien ordonné, typiquement l'ensemble des entiers. Par exemple, on choisira une fonction qui, pour un algorithme itératif décroît à chaque boucle, et pour un programment récursif décroît à chaque appel[2].
Problème de l'arrêt
Le problème de l'arrêt consiste, étant donné un algorithme, à décider si il termine ou pas. Ce problème est indécidable, au sens informatique du terme.
Notes et références
- ↑ « Terminaison des algorithmes », sur CPGE du lycée Montesquieu.
- ↑ Paul Gastin, « Algorithmique : Terminaison », sur ENS de Cachan, .