Aller au contenu

1NSI : Cours Terminaison d'un Algorithme⚓︎

Histoire⚓︎

Mohammed Al Kwârizmî, c. 780-850 ap JC

Les algorithmes sont bien plus anciens que l'informatique. L'étymologie vient de Al Kwârizmî, un savant persan du 8ème Siècle (né dans les années 780 dans l'actuel Ouzbékistan, mort vers 850 à Bagdad - actuel Irak).

Ils sont décrits souvent dans un pseudo-code.

Terminaison d'un Algorithme⚓︎

La Terminaison d'un algorithme répond à la question suivante:
Cet algorithme s'arrête-t-il un jour?

Terminaison d'un Algorithme

On dit qu'un algorithme termine s'il exécute un nombre fini d'étapes. Dans ce cas, on parle de la terminaison de cet algorithme.

boucle Pour⚓︎

Exemple du parcours séquentiel d'un tableau, ou recherche de l'occurence d'une valeur par force brute:

On se donne un tableau \(A\) de \(n\) éléments : \(A[0],A[1],..., A[n-1]\), dans lequel on recherche l'occurence d'une valeur cible, c'est-à-dire que l'on veut savoir si cette valeur appartient aux éléments du tableau, ou PAS.

# Parcours séquentiel d'un tableau A, ou recherche par force brute
Saisir cible
Trouve = FAUX
Pour chaque élément el du tableau A
  Si el = cible
  Alors Trouve = VRAI
Afficher Trouve

Cette boucle Pour réalise exactement \(n\) itérations (tours). Le nombre de tours/itérations, est donc toujours connu à l'avance et surtout fini: cet algorithme termine toujours (quelle que soit la valeur de \(n\)). De manière générale, une boucle Pour termine toujours.

boucle Tant que (ou boucle Repeat)⚓︎

Une boucle Tant que (et/ou une boucle Repeat, dans certains langages) peut terminer, ou pas.

Une boucle infinie (Tant que/Repeat) ne termine pas⚓︎

# problème posé : afficher tous les nombres entiers pairs positifs
i prend la valeur 0
Tant que i0
  afficher 2*i
  i prend la valeur i+1

\(\hookrightarrow\)Cet algorithme ne termine pas.

Algorithmes ne terminant pas

Le seul cas où un algorithme itératif (donc non récursif) ne termine pas est lorsqu'il exécute une boucle infinie (boucle Tant que, ou boucle Repeat dans certains langages)

Boucles bornées ou non bornées

  • Une boucle finie s'appelle aussi boucle bornée
  • Une boucle infinie est aussi appelée boucle non bornée, ou boucle non finie

Une boucle finie (Tant que/Repeat) termine⚓︎

# affiche tous les nombres de 100 à 1
i prend la valeur 100
Tant que i  1
  afficher i
  i prend la valeur i-1

Du coup: Comment être sûr de la Terminaison? ou pas⚓︎

Terminaison dans un cas simple:
On peut aisément se convaincre que certains algorithmes simples, comme par exemple lorsque le nombre d'instructions à effectuer est connu à l'avance (ex: boucle Pour), terminent de manière "évidente"
Terminaison dans le cas général, et plus formel: On utilise la notion de variant de boucle, quelquefois appelé convergent, pour se convaincre totalement de, donc pour démontrer la terminaison d'un algorithme.

Variant de boucle, ou convergent⚓︎

Un variant de boucle est un outil utile pour démontrer la terminaison d'un algorithme.

Variant de Boucle

Un variant de boucle, quelquefois appelé convergent, est une quantité \(v\), telle que:

  • \(v\) est un nombre entier (plus généralement un p-uplet d'entiers)
  • \(v\gt0\) à l'entrée de la boucle (plus généralement, au sens de l'ordre lexicographique)
  • \(v\) décroit strictement à chaque itération (plus généralement, au sens de l'ordre lexicographique)
  • \(v\le0\) provoque une sortie de la boucle (plus généralement, au sens de l'ordre lexicographique)

Terminaison d'une boucle (d'un algorithme)

Une boucle possédant un variant de boucle se termine.

Exemple:
Dans l'algorithme précédent la variable \(i\) (que l'on retrouve dans le test du Tant que) est le variant de boucle. Cela prouve la terminaison de cet algorithme.

Exercice:
Déterminer les variants de boucles pour les algorithmes suivants:

  1. Algorithme 1:
i prend la valeur 0
Tant que i  100
  afficher i
  i prend la valeur i+1
  1. Algorithme d'Euclide
# on suppose que a >= b
Saisir a, b
Tant que b n'est pas égal à 0
  (a, b) <- (b, a mod b)
afficher a

Remarques:

  • la terminaison n'assure pas la correction du résultat : il peut calculer autre chose que le problème demandé (bug)
  • la terminaison assure un arrêt théorique: elle ne tient pas compte de la complexité/coût de l'algorithme. Une terminaison dans plusieurs milliards d'années n'est d'un intérêt que modeste.