Descente infinie

Définition

On appelle variant d'une boucle "tant que" toute quantité $v$ vérifiant:

• $v\in\mathbb{N}$ (dans la boucle)
• $v$ décroit strictement à chaque passage dans la boucle.

Lien entre la notion de variant et la terminaison

Soit $v$ un variant d'une boucle tantQue dans un algorithme A.

On exécute l'algorithme A.
On note $v_0$ la valeur de $v$ au début du premier passage dans la boucle.

• Combien de valeurs $v$ peut-il prendre lors de l'exécution de l'algorithme ?

Solution

$v$ ne prend que des valeurs entières positives ou nulles (par définition d'un variant). Et les valeurs de $v$ décroissent strictement. Ce qui implique que $v$ ne prend jamais deux fois la même valeur et que les valeurs prises par $v$ appartiennent nécessairement à l'ensemble $\lbrace v_0, v_0-1, v_0-2, \dots, 2, 1, 0 \rbrace$.

$v$ prendra donc au plus $v_0+1$ valeurs lors de l'exécution de l'algorithme.

• En déduire que la boucle termine (ce qui signifie que l'on finit par sortir de la boucle).

Solution

$v$ prend au plus $v_0 +1$ valeurs. On passe donc au plus $v_0 + 1$ fois dans la boucle.

Remarque (lecture facultative)

Le principe de variant pour démontrer qu'une boucle se termine s'utilise plus généralement dans des raisonnements mathématiques. On parle de preuve par descente infinie pour les preuves suivant le schéma suivant:

• On suppose vraie une propriété A.
• On démontre que cela implique l'existence d'une suite strictement décroissante d'entiers naturels (c'est la descente infinie).
• Mais comme une descente infinie est impossible avec des entiers positifs, on en déduit que la propriété A ne peut pas être vraie.

Exemple.

Prouvons par exemple que $\sqrt{2}$ est irrationnel par descente infinie.

• On suppose que $\sqrt{2}$ est rationnel, c'est à dire que $\sqrt{2}$ peut s'écrire sous la forme d'un quotient de deux entiers $\frac{p}{q}$. Comme $\sqrt{2}$ est strictement positif, on peut prendre $p$ et $q$ strictement positifs.

• De l'égalité $\sqrt{2} = \frac{p}{q}$, on déduit $\boxed{q\sqrt{2} = p}$.
  Comme $1 < \sqrt{2} < 2$, on en déduit (en multipliant par le nombre $q > 0$) que $q < q\sqrt{2} < 2q$.
  Ce qui s'écrit également $q < p < 2q$. On en déduit (en enlevant q sur chaque membre) que $0 < p-q < q$: l'entier $q' = p-q$ est un entier naturel strictement positif et strictement plus petit que $q$.
  Soit $p' = 2q-p$ (c'est un entier strictement positif d'après l'inégalité précédente).

Calculons le rapport $\frac{p'}{q'}$:

$$\begin{align} \frac{p'}{q'} = \frac{2q-p}{p-q}\\ = \frac{2q-q\sqrt{2}}{q\sqrt{2}-q}\\ = \frac{q\sqrt{2}\left(\sqrt{2}-1\right)}{q\left(\sqrt{2}-1\right)}\\ = \sqrt{2} \end{align}$$

Comme $0 < q' < q$, on peut réitérer le procédé et définir $q''$ et $p''$ entiers tels que $0 < q'' < q' < q$ et $\frac{p''}{q''}= \sqrt{2}$... et ainsi de suite. On définit ainsi une descente infinie avec les entiers q, q', q''...

• Conclusion: $\sqrt{2}$ ne peut pas être rationnel.