Projet : Écrire et prouver des algorithmes itératifs et récursifs

algorithme maximum_rec(T: [réel], n: entier) → entier:
    si n == 0:
        rendre 0
    sinon:
        x ← maximum_rec(T, n-1)
        si t[x] > t[n]:
            rendre x
        sinon:
            rendre n

Le paramètre n est un entier qui diminue strictement. Il sera donc à un moment égal à 0 ce qui stoppera la récursion.

La correction se fait par récurrence sur n allant de n = 0 à n = T.longueur - 1.

1. initialisation : pour n = 0, le résultat est clair.
2. hypothèse de récurrence : on suppose que l'algorithme fonctionne pour n - 1
3. preuve pour n - 1. Si l'algorithme fonctionne pour n - 1, x contient l'indice max des indices allant de 0 à n - 1 et on rend x si T[x] > T[n] et n sinon : on rend bien l'indice de la valeur maximale du tableau.

algorithme concaténation(début: [entier], fin: [entier]) → [entier]
    t ← tableau de taille début.longueur + fin.longueur
    i ← -1

    pour chaque j de [0, début.longueur[:
        i ← i + 1
        t[i] ← début[j]

    pour chaque j de [0, fin.longueur[:
        i ← i + 1
        t[i] ← fin[j]

    rendre t

La finitude est claire puisqu'il n'y a que deux boucles de type pour chaque.

On a deux boucles, il faut donc à priori 2 invariants, un pour chaque boucle. Ici il est clair que l'on va remplir tous les éléments des tableaux début et fin dans t. L'invariant peut être :

si $i_0$ est la valeur de $i$ à la ligne 5 (resp. 9) alors à chaque fin d'itération on a $t[i_0 + 1 + k] == \mbox{début}[k]$ (resp. fin) pour tout $0\leq k \leq j$.

Démontrons l'invariant rigoureusement pour la première boucle.

À la fin de la première itération, on a bien :

• $t[i_0 + 1] == \mbox{début}[0]$
• $j = 0$
• $i = i_0 + 1 + j$

Supposons la propriété vraie après une itération donnée. Après une itération supplémentaire, les variables $i$ et $j$ ont été modifiées telles que :

• $j' = j + 1$
• $i' = i + 1 = i_0 + 1 + j'$

L'hypothèse de l'invariant de boucle stipule que $t[i_0 + k] == \mbox{début}[k]$ pour tout $0\leq k \leq j = j'-1$ et comme la boucle a effectué l'affectation : t[i'] ← début[j'], l'invariant continue d'être vérifié. Ce qui conclut la preuve.

Il faut juste faire très attention à l'endroit on commence dans t. ici c'est Ok car avant la première boucle i = -1 et i = début.longueur - 1 au début de la seconde boucle. Les éléments de début et fin ne vont pas se chevaucher dans t et se suivre sans interruption.

algorithme intersection_non_vide(T1: [entier], T2: [entier]) → booléen
    pour chaque x de T1:
        pour chaque y de T2:
            si x == y:
                rendre Vrai
    rendre Faux

La boucle 3-5 va chercher à trouver x dans T2 : trouvé ne peut valoir Vrai que si c'est le cas. Si ce n'est pas le cas, x n'est pas dans T2 et il faut chercher une autre possibilité d'égalité.

Comme on répète cette boucle intérieure pour tout x de T1, l'algorithme ne peut arriver ligne 6 que si $x \not in T2$ pour tout $x \in T1$.

Prouver cet algorithme ne nécessite pas d'invariant de boucle formel.

algorithme égalité_valeurs(T1: [entier], T2: [entier]) → booléen
    pour chaque x de T1:
        trouvé ← Faux
        pour chaque y de T2:
            si x == y:
                trouvé ← Vrai
        si trouvé == Faux:
            rendre Faux

    rendre Vrai

Prouver cet algorithme ne nécessite pas d'invariant de boucle formel, mais il faut faire attention à sa construction.

La boucle 4-6 va chercher à trouver x dans T2 : trouvé ne peut valoir Vrai que si c'est le cas. Si ce n'est pas le cas, on peut sortir de l'algorithme (ligne 7-8) puisque x n'est pas dans T2.

Comme on répète cette boucle intérieure pour tout x de T1, l'algorithme est bien correct.

Il faut pouvoir trouver tous les éléments de $T$ dans $T'$. autant de fois qu'ils sont dans $T$. En utilisant nombre, on a l'algorithme suivant :

algorithme égalité(T1: [entier], T2: [entier]) → entier
    pour chaque x de T1:
        si nombre(T1, x) ≠ nombre(T2, x):
            rendre Faux
    rendre Vrai

On ne peut rendre Vrai que si tous les éléments de T1 sont dans T2 avec un même montant. Donc uniquement s'il existe une existe une permutation $\sigma$ de $[0, n-1]$ telle que $T[i] = T[\sigma(i)]$ pour tout $i \in [0, n-1]$.

Pour que l'algorithme fonctionne, il faut commencer par connaître la taille du tableau à créer et donc compter le nombre d’occurrences de v dans T. Ensuite, il sera possible de remplir le tableau.

algorithme supprime(T: [entier], v: entier) → [entier]
    T2 ← tableau de taille t.longueur - nombre(T, v)

    j ← 0
    pour tout i de [0, t.longueur[:
        si T[i] ≠ v:
            T2[j] ← t[i]
            j ← j + 1
    
    rendre T2

La finitude du programme est clair puisque l'on a que des boucles de type pour chaque.

On commence par créer un tableau permettant exactement de stocker tous les éléments de T différents de v. Ce que fera la boucle. On peut prouver celle-ci par l'invariant :

à la fin de chaque itération, T2 contient la restriction des i + 1 premiers éléments de T différents de v.

La preuve de l'invariant est évidente et permet de prouver l'algorithme en se plaçant à la fin de la dernière itération.

algorithme supprime_rec(t: [entier], v: entier) → [entier]
    si t.longueur == 0:
        rendre t

    t2 ← tableau de longueur t.longueur - 1
    pour i de [0, t2.longueur[:
        t2[i] ← t[i + 1]
    
    si t[0] == v:
        rendre concaténation([], supprime_rec(t2, v))
    sinon:
        rendre concaténation([t[0]], supprime_rec(t2, v))

Il n'y a qu'une seule récursion par algorithme et la taille du tableau passé en paramètre est strictement plus petite : il y a un nombre finie de récursion puisque la condition terminale est basée sur une taille nulle de tableau.

Pour la correction une récurrence immédiate sur la taille du tableau nous permet de conclure.

algorithme palindrome(T: [entier]) → booléen
    pour tout i de [0, T.longueur // 2[:
        si T[i] ≠ T[T.longueur - 1 - i]:
            rendre Faux
    rendre Vrai

algorithme palindrome_rec(T: [entier], i: entier) → booléen
    si T.longueur - 1 - i ≤ i:
        rendre Vrai
    si  T[i] ≠ T[T.longueur - 1 - i]:
        rendre Faux
    
    rendre palindrome_rec(T, i + 1)

La premiere condition est la condition d'arrêt de la récursion puisque dans ce cas là $i$ a dépassé la moitié du tableau.

Puis on utilise l'équation de récurrence :

palindrome(T) = (T[0] == T[-1]) et palindrome(T[1:-1])

algorithme maximum(T: [entier]) → entier
    rendre maximum_rec(t, T.longueur - 1)

algorithme retournement_indice(T: [entier], i: entier) → ∅
    si T.longueur - 1 - i > i:
        temp ← T[i]
        T[i] ← T[T.longueur - 1 - i]
        T[T.longueur - 1 - i] ← temp

        retournement_indice(T, i + 1)

Les lignes 3-5 permettent d'échanger les valeurs t[i] et t[t.longueur - 1 - i] du tableau. On peut aussi écrire t[i], t[t.longueur - 1 - i] ← t[t.longueur - 1 - i], t[i], comme on le ferait en python, si l'on autorise le fait d'affecter 2 valeurs en même temps.

Le finitude est claire puisque :

1. il n'y a qu'un appel récursif
2. chaque appel se rapproche strictement de la condition d'arrêt

La correction vient du fait que l'on échange bien des valeurs symétriques du tableau par rapport à l'indice du milieu du tableau qui est ici la partie entière de $t.\mbox{longueur} - 1/ 2$.

fonction retournement_indice(T: [entier], i: entier) → ∅
    ...  # code de la fonction récursive

algorithme retournement(T: [entier]) → ∅
    retournement_indice(T, 0)

algorithme palindrome_pas_rec(T: [entier], i: entier) → booléen
    tant que (T.longueur - 1 - i > i): 
        si  T[i] ≠ T[T.longueur - 1 - i]:
            rendre Faux
        i ← i + 1
    rendre Vrai

algorithme retournement_indice(t: [entier], i: entier) → ∅
    tant que (t.longueur - 1 - i > i):
        temp ← t[i]
        t[i] ← t[t.longueur - 1 - i]
        t[t.longueur - 1 - i] ← temp

        i ← i + 1

Et donc, en utilisant un petit abus de pseudocode :

algorithme retournement(t: [entier], i: entier) → ∅
    i ← 0
    tant que (t.longueur - 1 - i > i):
        t[i], t[t.longueur - 1 - i] ← t[t.longueur - 1 - i], t[i] 
        i ← i + 1

algorithme puissance_2(m: entier, n: entier) → entier:
    si 2 * m ≥ n:
        rendre m
    sinon:
        rendre f(2 * m, n)

C'est bien une récursion terminale puisque le code est équivalent à :

fonction c(m: entier, n: entier) → entier:
    rendre 2 * m ≥ n

fonction g(m: entier, n: entier) → entier:
    rendre m

algorithme puissance_2(m: entier, n: entier) → entier:
    si c(m, n) == Vrai:
        rendre g(m, n)
    sinon:
        rendre f(2 * m, n)

Avec le type A étant un couple d'entier et B le type entier.

Il est clairement sous la forme récursive terminale. Il fini car chaque récursion se rapproche strictement de la condition d'arrêt.

Enfin, acc va contenir la factorielle comme le prouve une récursion triviale sur $n$.

function u_n_term(n: entier, 
                 u0: entier, 
                 r: entier, 
                 acc: entier) → entier:
    si n == 0:
        rendre u0 + acc
    rendre u_n_term(n-1, u0, r, r + acc)


algorithme u_n(n : entier, 
               u0: entier, 
               r : entier
              ) → entier:
    rendre u_n_term(n, u0, r, 0)

Le but de la récursion terminale est de facile,ent transformer un algorithme récursif en un algorithme itératif cr la récursion est une boucle tant que.

algorithme u_n(n : entier, 
               u0: entier, 
               r : entier
              ) → entier:
    acc ← 0
    tant que n > 0:
        acc ← r + acc
        n ← n - 1
    
    rendre u0 + acc

algorithme pair(n: entier) → booléen
    si n == 0:
        rendre Vrai
    rendre non impair(n - 1)

algorithme impair(n: entier) → booléen
    si n == 0:
        rendre Faux
    rendre non pair(n - 1)

La finitude est claire puisque :

1. il n'y a qu'un appel récursif
2. chaque appel se rapproche strictement de la condition d'arrêt

La correction est évidente par définition de la parité.

algorithme M(n: entier) → entier:
    si n > 100:
        rendre n - 10
    sinon:
        x ← M(n + 11)
        rendre M(x)

Mais est-ce que ce programme se termine ? Rien n'est moins sur.

algorithme M(n: entier) → entier:
    c ← 1

    tant que c ≠ 0:
        si n > 100:
            n ← n - 10
            c ← c - 1
        sinon:
            n ← n + 11
            c ← c + 1
    rendre n

Comme on peut écrire cette fonction comme une recursion terminale, l'écriture iterative est aisée : Pour $90 \leq n < 101$, on a :

On arrive à ce résultat en 1 récursion : la ligne 5 de l'algorithme en pseudocode de la question précédente.

On a $M(91) = M(92) = \dots = M(101) = 91$ et pour tout $n < 90$ on il existera $k > 1$ et $91\leq n'< 101 tels que $M(n) = M^k(n') = 91$

Comme il faut un nombre fini d'itération pour passer de $M(n)$ à $M(n+1)$ on en déduit qu'il faut bien un nombre fini d'itération pour calculer $M(91)$ (disons $I$), et donc également pour calculer $M^k(91)$ quelque soit $k>0$ (il en faut $k\cdot I$).

algorithme M(n: entier) → entier:
    si n > 100:
        rendre n - 10
    sinon:
        rendre 91

Dans le même ordre d'idée que la fonction de Takeuchi, c'est un leurre.