Correction et Terminaison

Le cas (d) merite attention : la boucle comporte deux branches, et il faut verifier que le variant decroit dans chacune. Ici i += 1 comme j -= 1 diminuent \(j - i\) de 1 : c'est bien un variant.

Le cas (b) illustre le lien direct entre variant et complexite : un variant divise par 2 donne un nombre logarithmique d'iterations.

1. Terminaison. Variant \(V = n - k + 1\). C'est un entier, positif tant que la condition \(k \le n\) est vraie, et il decroit de 1 a chaque tour (k += 1). La boucle effectue donc exactement \(n\) iterations.

2. Invariant. \(P\) : « \(s = \sum_{j=1}^{k-1} j^2\) et \(1 \le k \le n+1\) ».

• Initialisation : \(k = 1\) et \(s = 0 = \sum_{j=1}^{0} j^2\) (somme vide). Vrai.
• Conservation : supposons \(P\) vraie et \(k \le n\). Apres le corps, \(s' = s + k^2 = \sum_{j=1}^{k-1} j^2 + k^2 = \sum_{j=1}^{k} j^2\) et \(k' = k+1\), donc \(s' = \sum_{j=1}^{k'-1} j^2\). De plus \(k' = k+1 \le n+1\). \(P\) est preservee.
• Exploitation : a la sortie, \(k > n\) et \(k \le n+1\), donc \(k = n+1\). L'invariant donne \(s = \sum_{j=1}^{n} j^2\), qui est la postcondition.

La fonction est totalement correcte, en \(\Theta(n)\).

3. Par recurrence : la formule est vraie pour \(n=0\) (les deux membres sont nuls) et \[ \frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{(n+1)\bigl(n(2n+1) + 6(n+1)\bigr)}{6} = \frac{(n+1)(2n^2+7n+6)}{6} = \frac{(n+1)(n+2)(2n+3)}{6}, \] qui est bien la formule au rang \(n+1\).

for n in range(200):
    assert somme_carres(n) == n*(n+1)*(2*n+1) // 6

4. Avec k < n, la boucle s'arrete des que \(k = n\) : le terme \(n^2\) n'est jamais ajoute. L'invariant reste vrai (il ne depend pas de la condition), mais l'exploitation change : a la sortie \(k = n\), donc \(s = \sum_{j=1}^{n-1} j^2\). La postcondition n'est plus verifiee : c'est l'erreur classique du « decalage de un » (off-by-one). C'est precisement l'etape d'exploitation qui la revele.

1. Boucle interne. Invariant \(Q_j\) : « \(t[\texttt{imin}] = \min(t[i..j-1])\) et \(i \le \texttt{imin} < j\) ».

• Initialisation (\(j = i+1\)) : \(\texttt{imin} = i\) et \(t[i] = \min(t[i..i])\). Vrai.
• Conservation : si \(t[j] < t[\texttt{imin}]\), on pose \(\texttt{imin} = j\) et alors \(t[\texttt{imin}] = t[j] = \min(t[i..j])\) ; sinon \(t[\texttt{imin}] \le t[j]\) reste le minimum de \(t[i..j]\). Dans les deux cas \(Q_{j+1}\) est vraie.
• Exploitation : a la sortie \(j = n\), donc \(t[\texttt{imin}] = \min(t[i..n-1])\).

La boucle interne est un for sur un range fini : elle termine.

2. Boucle externe. Invariant \(P_i\) : « \(t[0..i-1]\) est triee par ordre croissant, contient les \(i\) plus petits elements de la liste initiale, et \(t\) est une permutation de sa valeur initiale ».

3. Preuve complete.

• Initialisation (\(i=0\)) : \(t[0..-1]\) est vide, donc triee et contenant les 0 plus petits elements ; \(t\) est inchangee, donc permutation d'elle-meme. \(P_0\) est vraie.
• Conservation : supposons \(P_i\) vraie. La boucle interne place dans \(\texttt{imin}\) l'indice du minimum de \(t[i..n-1]\) (question 1). L'echange \(t[i] \leftrightarrow t[\texttt{imin}]\) place ce minimum en position \(i\) : c'est une transposition, donc \(t\) reste une permutation de sa valeur initiale.
  De plus, par \(P_i\), \(t[0..i-1]\) contient les \(i\) plus petits elements ; le minimum de ce qui reste est donc le \((i+1)\)-ieme plus petit, et il est superieur ou egal a tous les elements de \(t[0..i-1]\). Ainsi \(t[0..i]\) est triee et contient les \(i+1\) plus petits elements : \(P_{i+1}\) est vraie.
• Exploitation : a la sortie, \(i = n-1\). \(P_{n-1}\) donne que \(t[0..n-2]\) est triee et contient les \(n-1\) plus petits elements ; le dernier element restant est donc le plus grand, et \(t\) tout entiere est triee. C'est la postcondition.

Terminaison : les deux boucles sont des for sur des range finis. L'algorithme est totalement correct.

4. Complexite. Pour chaque \(i\) de 0 a \(n-2\), la boucle interne effectue \(n-1-i\) comparaisons. Total : \[ \sum_{i=0}^{n-2}(n-1-i) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}. \] C'est exact et independant de l'entree : le tri par selection n'a ni meilleur ni pire cas en nombre de comparaisons. En revanche il effectue au plus \(n-1\) echanges.

1. Specification.

• Precondition : \(t\) est une liste triee par ordre croissant.
• Postcondition : la fonction renvoie un indice \(i\) tel que \(t[i] = v\) si \(v\) appartient a \(t\), et \(-1\) sinon.

2. Terminaison. Variant \(V = d - g + 1\) (taille de l'intervalle). C'est un entier, positif tant que \(g \le d\). Avec \(m = \lfloor (g+d)/2 \rfloor\), on a \(g \le m \le d\). Deux cas :

• \(g \leftarrow m+1\) : \(V' = d - m \le d - g < V\) ;
• \(d \leftarrow m-1\) : \(V' = m - g \le d - g < V\).

Decroissance stricte dans les deux cas. De plus \(V' \le \lceil V/2 \rceil\) : le nombre d'iterations est \(\le \lfloor\log_2 n\rfloor + 1\).

3. Correction. Invariant \(P\) : « si \(v\) figure dans \(t\), alors \(v\) figure dans \(t[g..d]\) ».

• Initialisation : \(t[0..n-1] = t\). Vrai.
• Conservation : supposons \(t[m] < v\). Comme \(t\) est triee, pour tout \(i \le m\) on a \(t[i] \le t[m] < v\), donc \(t[i] \ne v\). Aucun indice de \([g, m]\) ne convient : si \(v\) est dans \(t[g..d]\), il est dans \(t[m+1..d]\), ce qui est exactement le nouvel intervalle. Le cas \(t[m] > v\) est symetrique.
• Exploitation : deux sorties possibles. Si \(t[m] = v\), on renvoie \(m\) : correct. Si \(g > d\), l'intervalle est vide ; l'invariant dit que si \(v\) etait present, il serait dans un intervalle vide, ce qui est absurde : \(v\) est absent, et \(-1\) est correct.

L'hypothese de tri intervient uniquement dans la conservation, pour affirmer que tous les elements a gauche de \(m\) sont \(\le t[m]\). Sans elle, l'invariant n'est pas preserve et l'algorithme peut conclure a tort a l'absence (voir chapitre 13, exercice 2).

4. Avec g = m, prenons \(g = 0\) et \(d = 1\) avec \(t[0] < v\). Alors \(m = \lfloor 1/2 \rfloor = 0\), et l'on pose \(g = m = 0\) : l'etat \((g,d) = (0,1)\) est inchange. Le variant \(d - g + 1 = 2\) ne decroit pas : la boucle est infinie. C'est le bug le plus frequent dans une dichotomie ecrite a la main, et il n'est visible que sur les intervalles de taille 2.

def dichotomie_buguee(t, v, max_tours=20):
    g, d, tours = 0, len(t) - 1, 0
    while g <= d and tours < max_tours:
        tours += 1
        m = (g + d) // 2
        if t[m] == v: return m, tours
        if t[m] < v: g = m          # BUG
        else: d = m - 1
    return -1, tours

print(dichotomie_buguee([1, 3], 3))    # (-1, 20) : le garde-fou a du intervenir

1. Puissance rapide.

def puissance(x, n):
    if n == 0: return 1
    if n % 2 == 0:
        y = puissance(x, n // 2)
        return y * y
    return x * puissance(x, n - 1)

Terminaison : variant \(n \in \mathbb{N}\). Cas pair : l'appel porte sur \(n/2 < n\) (car \(n \ge 2\)). Cas impair : sur \(n - 1 < n\). Le cas de base \(n=0\) est atteint.

Correction : recurrence forte sur \(n\). Base : \(n=0\) renvoie \(1 = x^0\). Heredite : soit \(n \ge 1\) ; si \(n = 2p\), l'hypothese donne \(y = x^p\) et la fonction renvoie \(y^2 = x^{2p} = x^n\) ; si \(n\) est impair, elle renvoie \(x \cdot x^{n-1} = x^n\).

2. Tri fusion.

Terminaison : variant \(\mathrm{len}(t)\). Pour \(\mathrm{len}(t) \ge 2\), on a \(m = \lfloor \mathrm{len}(t)/2 \rfloor\) avec \(1 \le m < \mathrm{len}(t)\), donc les deux tranches sont strictement plus courtes et non vides. Le cas de base \(\mathrm{len}(t) \le 1\) est atteint.

Correction : recurrence forte sur \(\mathrm{len}(t)\). Base : une liste de 0 ou 1 element est triee. Heredite : par hypothese, les deux appels renvoient des listes triees contenant respectivement les elements de \(t[:m]\) et \(t[m:]\) ; on a prouve (chapitre 12) que fusion renvoie une liste triee contenant exactement leurs elements reunis. C'est donc une permutation triee de \(t\).

3. Hanoi. Terminaison : variant \(n\), qui decroit de 1 a chaque appel ; base \(n = 0\).

Nombre de deplacements : \(T(n) = 2T(n-1) + 1\), \(T(0)=0\), d'ou \(T(n) = 2^n-1\) (voir chapitre 14).

Validite : par recurrence forte sur \(n\). On montre la propriete plus forte : « l'appel hanoi(n, a, c, b) transfere les \(n\) plus petits disques de \(a\) vers \(c\), sans jamais poser un disque sur un plus petit, en supposant que \(a\), \(b\), \(c\) ne contiennent que des disques plus grands que ces \(n\)-la ». Base \(n=0\) : rien a faire. Heredite : le premier appel transfere les \(n-1\) plus petits de \(a\) vers \(b\) (hypothese applicable car ils sont tous plus petits que le \(n\)-ieme, qui n'a pas bouge) ; le \(n\)-ieme disque va alors sur \(c\), qui ne contient que des disques plus grands ; le second appel ramene les \(n-1\) de \(b\) vers \(c\), au-dessus du \(n\)-ieme qui est plus grand. Aucune regle n'est violee.

4. Sans cas de base, la recursion est infinie : Python leve RecursionError apres 1000 appels. Plus subtil : un cas de base incomplet (par exemple if n == 0 pour une fonction appelee avec \(n\) decroissant de 2 en 2 depuis un impair) provoque la meme erreur, mais seulement pour certaines entrees — bug bien plus difficile a detecter. C'est pourquoi on ecrit if n <= 0 plutot que if n == 0 chaque fois que c'est semantiquement acceptable.

a) Renversement. Invariant : « \(t[0..g-1]\) et \(t[d+1..n-1]\) sont deja echanges (ils contiennent respectivement la fin et le debut de la liste initiale, dans le bon ordre), et \(t[g..d]\) est inchangee ; de plus \(g + d = n - 1\) ».

A la sortie, \(g \ge d\), donc la zone centrale contient au plus un element (qui est son propre symetrique) : la liste entiere est renversee. Variant : \(d - g\), qui decroit de 2.

b) Comptage. Invariant : « \(c = \mathrm{card}\{k < i \mid t[k] = v\}\) et \(0 \le i \le n\) ».

• Initialisation : \(i = 0\), \(c = 0\), l'ensemble est vide. Vrai.
• Conservation : le corps incremente \(c\) exactement lorsque \(t[i] = v\), c'est-a-dire lorsque l'ensemble gagne l'element \(i\).
• Exploitation : \(i = n\), donc \(c\) compte toutes les occurrences.

c) Horner. Notons \(P = [a_0, \dots, a_n]\) et indexons les tours par \(k = n, n-1, \dots, 0\) (les coefficients sont parcourus a l'envers). Invariant apres traitement de \(a_k\) : « \(v = \sum_{i=k}^{n} a_i x^{i-k}\) ».

• Initialisation : avant le premier tour, \(v = 0\), somme vide. Vrai (avec \(k = n+1\)).
• Conservation : le tour calcule \(v' = vx + a_k\), soit \(v' = x\sum_{i=k+1}^{n} a_i x^{i-k-1} + a_k = \sum_{i=k+1}^{n} a_i x^{i-k} + a_k = \sum_{i=k}^{n} a_i x^{i-k}\). Preserve.
• Exploitation : apres le dernier tour \(k = 0\), donc \(v = \sum_{i=0}^{n} a_i x^{i} = P(x)\).

Le schema de Horner effectue \(n\) multiplications et \(n\) additions, ce qui est optimal.

d) Kadane. Invariant avant le tour \(j\) : « \(m = \max_{i \le j-1} \sum_{k=i}^{j-1} t_k\) (meilleure somme d'un segment finissant en \(j-1\)) et \(M = \max_{i \le l \le j-1} \sum_{k=i}^{l} t_k\) (meilleure somme d'un segment inclus dans \([0, j-1]\)) ».

• Initialisation : \(j = 1\), \(m = M = t_0\). Les deux maxima sur les segments inclus dans \([0,0]\) valent \(t_0\). Vrai.
• Conservation : un segment finissant en \(j\) est soit \(\{j\}\) seul, soit un segment finissant en \(j-1\) prolonge. D'ou \(m' = t_j + \max(0, m)\), qui est bien le nouveau \(m\). Puis \(M' = \max(M, m')\) etend le maximum aux segments finissant en \(j\).
• Exploitation : \(j = n\), donc \(M\) est le maximum sur tous les segments non vides.

Complexite \(\Theta(n)\) en temps, \(\Theta(1)\) en espace : optimal.

2. Calculs exacts.

Pour (b) : \(\displaystyle\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}\).

Pour (e), le nombre d'executions est le nombre de triplets \((i,j,k)\) avec \(0 \le i \le j \le k \le n-1\), c'est-a-dire le nombre de combinaisons avec repetition de 3 elements parmi \(n\) : \[ \binom{n+2}{3} = \frac{n(n+1)(n+2)}{6} = \Theta(n^3). \]

def compte_e(n):
    x = 0
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                x += 1
    return x

from math import comb
for n in range(1, 30):
    assert compte_e(n) == comb(n + 2, 3)
print("formule verifiee")

3. Classement croissant :

\[ \underbrace{\Theta(\log n)}_{(c)} \;<\; \underbrace{\Theta(n\log n)}_{(d)} \;<\; \underbrace{\Theta(n^2)}_{(a),(b)} \;<\; \underbrace{\Theta(n^3)}_{(e)} \;<\; \underbrace{\Theta(2^n)}_{(f)}. \]

Noter que (a) et (b) sont dans la meme classe \(\Theta(n^2)\) bien que (b) fasse deux fois moins de travail : la notation \(\Theta\) ignore les constantes multiplicatives. C'est une information a ne pas negliger en pratique, mais qui ne change pas l'ordre de grandeur.

1. Specification de partition.

• Precondition : \(0 \le g \le d < \mathrm{len}(u)\).
• Postcondition : renvoie \(p \in [g, d]\) tel que, apres l'appel, \(u[i] \le u[p]\) pour tout \(i \in [g, p]\) et \(u[i] > u[p]\) pour tout \(i \in [p+1, d]\) ; de plus \(u[g..d]\) est une permutation de sa valeur d'entree et \(u\) est inchangee hors de \([g,d]\).

import random

def partition(u, g, d):
    """Schema de Lomuto avec pivot aleatoire."""
    r = random.randint(g, d)
    u[r], u[d] = u[d], u[r]
    pivot = u[d]
    i = g
    for j in range(g, d):
        if u[j] <= pivot:
            u[i], u[j] = u[j], u[i]
            i += 1
    u[i], u[d] = u[d], u[i]
    return i

Invariant de la boucle \(j\) : « \(u[g..i-1] \le \text{pivot}\), \(u[i..j-1] > \text{pivot}\), \(u[d] = \text{pivot}\), et \(u[g..d]\) est une permutation de sa valeur initiale ».

• Initialisation : \(i = j = g\), les deux zones sont vides. Vrai.
• Conservation : si \(u[j] \le \text{pivot}\), on echange \(u[i]\) et \(u[j]\) : la valeur \(u[j]\) rejoint la zone des « \(\le\) » qui s'agrandit, et l'ancienne \(u[i]\) (qui etait \(>\) pivot, ou est \(u[j]\) si \(i=j\)) rejoint la zone des « \(>\) ». Sinon on ne fait rien et la zone des « \(>\) » s'agrandit d'elle-meme. Dans les deux cas les echanges sont des transpositions, donc la permutation est preservee.
• Exploitation : \(j = d\), donc \(u[g..i-1] \le \text{pivot} < u[i..d-1]\). L'echange final place le pivot en position \(i\), ce qui etablit la postcondition avec \(p = i\).

Complexite : \(\Theta(d - g)\) comparaisons.

2. Terminaison de selection. Variant \(V = d - g\), entier positif tant que \(g < d\). Apres un tour, soit on renvoie, soit :

• \(d \leftarrow p - 1\) avec \(p \ge g\), donc \(V' = p-1-g \le d-1-g < V\) ;
• \(g \leftarrow p + 1\) avec \(p \le d\), donc \(V' = d-p-1 \le d-g-1 < V\).

Decroissance stricte : la boucle termine.

3. Invariant. \(P\) : « \(0 \le g \le k \le d < \mathrm{len}(u)\), et le \(k\)-ieme plus petit element de \(u\) (tout entier) se trouve dans \(u[g..d]\) ; plus precisement, \(\mathrm{sorted}(u)[k] = \mathrm{sorted}(u[g..d])[k-g]\) ».

• Initialisation : \(g=0\), \(d=n-1\), la propriete est triviale.
• Conservation : apres partition, on sait que \(u[p]\) est a sa place definitive dans le tri de \(u[g..d]\) : tous les elements a sa gauche lui sont inferieurs ou egaux, tous ceux a sa droite lui sont superieurs. Donc :
  • si \(k = p\), \(u[p]\) est le \(k\)-ieme plus petit : on renvoie, correct ;
  • si \(k < p\), le \(k\)-ieme plus petit est parmi \(u[g..p-1]\) (il y a exactement \(p-g\) elements \(\le u[p]\) a gauche), donc \(d \leftarrow p-1\) preserve \(P\) ;
  • si \(k > p\), symetriquement, \(g \leftarrow p+1\) preserve \(P\).
• Exploitation : a la sortie de boucle \(g = d\), et \(P\) impose \(g \le k \le d\), donc \(k = g\) : l'unique element de l'intervalle est le \(k\)-ieme plus petit. On renvoie \(u[g]\) : correct.

4. Complexite en moyenne. Le pivot etant choisi uniformement, sa position \(p\) est uniforme sur \([g,d]\). Avec probabilite \(1/2\), le pivot tombe dans le « quartile central », auquel cas le sous-intervalle conserve a une taille \(\le 3m/4\) ou \(m = d-g+1\). L'esperance du cout verifie donc \[ T(m) \le T\!\left(\tfrac{3m}{4}\right) + \Theta(m), \] d'ou, en deroulant, \(T(m) = \Theta\!\bigl(m\sum_{i\ge0}(3/4)^i\bigr) = \Theta(m)\) : la serie geometrique converge et le cout est lineaire en moyenne.

Au pire (pivots systematiquement extremaux), \(T(n) = n + (n-1) + \cdots = \Theta(n^2)\), mais avec un pivot aleatoire la probabilite d'un tel scenario est de l'ordre de \(1/n!\).

Il existe un algorithme deterministe en \(\Theta(n)\) au pire (mediane des medianes, Blum-Floyd-Pratt-Rivest-Tarjan, 1973), fonde sur le choix d'un pivot garantissant une partition au moins 30/70 ; sa constante est toutefois si grande qu'il est rarement utilise en pratique.