Démontrer qu’un algorithme termine

Comme nous l’avons déjà vu, un algorithme a pour objectif de répondre à un problème donné. Plusieurs questions se posent alors, comme savoir si l’algorithme donne effectivement la réponse attendue (ce qu’on appelle la correction), et s’il va effectivement donner une réponse (ce qu’on appelle la terminaison).

Terminaison des algorithmes

La question se pose car certains algorithmes utilisent des boucles de calcul ou des récursions. Ces opérateurs itèrent un procédé tant qu’une condition est valide. Par exemple, considérons le programme suivant :

def example1 (x) :
    while True :
        x = x + 1
    return x

def example1 (x) :

while True :

x = x + 1

return x

L’algorithme associé à la fonction example1 ne termine pas, c’est-à-dire qu’il existe des entrées (ici x est l’entrée) pour lesquelles l’exécution de l’algorithme ne finira jamais (ici toute valeur initiale de x fera que l’algorithme ne terminera pas).

Pour démontrer qu’un algorithme termine, il faut souvent trouver un convergent (parfois appelé variant), c’est-à-dire une quantité modifiée à chaque itération d’une boucle, et qui suit un comportement monotone sur un ensemble bien fondé (voir le lien en bas sur les relations d’ordre). Considérons l’exemple ci-après, où l’entrée x est un entier naturel :

def example2 (x) :
    while x > 0 :
        x = x - 1
    return x

def example2 (x) :

while x > 0 :

x = x - 1

return x

On remarque qu’à chaque passage dans la boucle, la valeur de x décroît strictement. Comme x ∊ ℕ, on obtient une suite strictement décroissante d’entiers. La condition pour sortir de la boucle sera donc forcément atteinte car l’ensemble des entiers naturels ℕ est bien fondé, c’est-à-dire qu’il n’existe pas de suite infinie strictement décroissante d’entiers naturels (dans notre cas on finira toujours par arriver à 0). En conclusion, example2 termine.

Plus généralement, un programme peut contenir un grand nombre de boucles ou de récursions, dont certaines sont imbriquées. Il peut alors devenir complexe de prouver la terminaison de l’algorithme.

Quand la terminaison est un défi

Suite de Syracuse

Nous avons vu qu’on peut prouver la terminaison ou la non-terminaison d’un algorithme répondant à un problème. Toutefois, il existe certains problèmes célèbres dont on ne sait pas encore prouver s’ils terminent ou non.

C’est le cas par exemple de la célèbre suite de Syracuse dont un programme illustre le comportement ci-après, où x est un entier strictement positif :

def syracuse (x) :
    while (x != 1) :
        if x % 2 == 0 :
            x = x / 2
        else :
            x = 3 * x + 1

def syracuse (x) :

while (x != 1) :

if x % 2 == 0 :

x = x / 2

else :

x = 3 * x + 1

Indécidabilité

Le problème de l’arrêt peut être formulé comme suit : “Peut-on écrire un programme prenant en entrée un programme P et renvoyant true si P termine pour toute entrée, et false sinon ?”. On sait que ce problème est indécidable, c’est à dire qu’il n’existe aucun algorithme qui permette d’y répondre.

Souvent, pour prouver qu’un problème P est indécidable, on réduit le problème de l’arrêt (ou un autre problème connu comme indécidable) à P, c’est à dire qu’on montre que résoudre P permet de résoudre le problème de l’arrêt, ce qui est une contradiction.

Démontrer qu’un algorithme termine

Terminaison des algorithmes

Quand la terminaison est un défi

Suite de Syracuse

Indécidabilité

Pour approfondir

Laisser un commentaire Annuler la réponse.