Algorithmique/Preuve d'arrêt

Comme nous le savons, un algorithme est une séquence d'instructions créée dans l'optique de résoudre un problème. Il est alors important de vérifier que notre séquence réalise bien ce qu'on lui demande.

**Preuve d'arrêt**
Leçon : Algorithmique

Chapitre n^o 3
Chap. préc. :	Variables
Chap. suiv. :	Forme d'écriture d'un algorithme

En raison de limitations techniques, la typographie souhaitable du titre, « Algorithmique : Preuve d'arrêt
Algorithmique/Preuve d'arrêt », n'a pu être restituée correctement ci-dessus.

Avant cela, il est primordial d'étudier ce qu'on nomme la preuve d'arrêt d'un algorithme. C'est ce que nous ferons dans cette présente leçon.

Quelques exemples

Imaginons un algorithme tel que :

Exemple

Début
----
i ← 1
Tant que i < 10 faire
    Afficher i
Fin Tant que
----
Fin

Ici, le problème est simple : on réalise une condition qui sera toujours vérifiée car la variable reste identique. L'algorithme tournera alors à l'infini.

Voyons un autre exemple :

Exemple

Début
----
i ← 100
Tant que i > 0 faire
    Afficher i
    i ← i - 1
Fin Tant que
----
Fin

Là, l'algorithme s'arrête. Voyons comment noter la preuve de cet arrêt.

Écriture formelle de la preuve d'arrêt

Reprenons l'algorithme précédent. Nous avons une boucle qui réalise une comparaison itérative. À l'intérieur de cette boucle est opéré un certain nombre d'instructions mais l'élément primordial est la réaffectation de i. Sans celle-ci, nous aurions le même problème que pour le premier algorithme.

Formellement, notre algorithme s'arrête car i $_{0}$ est positif ET qu’il décroit strictement. L'arrêt est donc réalisé car la comparaison i > 0 sera fausse à un certain moment.

Algorithmique

Variables

Forme d'écriture d'un algorithme