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.
Notion de terminaison
Étant donné un algorithme, ou un programme, une question importante est de savoir si, une fois lancé, il va s'arrêter. Par exemple un algorithme prenant un entier i en entrée, et ayant comme code :
- tant que i est supérieur à 0, remplacer i par i+1,
ne s’arrêtera pas sur l'entrée 1.
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 algorithmique du terme.
Notes et références
- ↑ « Terminaison des algorithmes », sur CPGE du lycée Montesquieu.
- ↑ Paul Gastin, « Algorithmique : Terminaison », sur ENS de Cachan, .
Voir aussi
- Complexité en temps, une autre caractéristique importante pour les programme qui terminent : le temps de calcul en fonction de la taille de l'entrée
