Home
About

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

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

Nous y verrons divers moyens de triturer des tableaux de façon itérative et récursive.

À retenir

Une fois un algorithme créé, on le teste toujours sur de petites instances en se mettant à la place de l'ordinateur.

  • on numérote chaque ligne
  • on note sur une feuille les variables
  • on exécute ligne à ligne en notant les différents résultats
  • à la fin on vérifie que le retour de l'algorithme est bien correct

Maximum d'un tableau

On a déjà vue une version itérative de cet algorithme, voyons (ou plutôt voyez) comme en faire un version recursive :

Donnez et prouvez un algorithme récursif de signature :

maximum_rec(T: [réel], n: entier) → entier

Qui rend un indice $0 \leq j \leq n$ tel que $t[j] = \max({t[k] \vert 0\leq k \leq n})$.

corrigé

 
algorithme maximum_rec(T: [réel], n: entier) → entier:
    x := 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.

Concaténation

Donnez et prouvez un algorithme itératif de signature :

concaténation(début: [entier], fin: [entier]) → [entier]

Qui rend un nouveau tableau contenant la concaténation de début et de fin.

Vous utiliserez des invariants de boucle pour le prouver.

corrigé

 
algorithme concaténation(début: [entier], fin: [entier]) → [entier]
    t := [entier]{longueur: début.longueur + fin.longueur}
    (i := entier) ← -1

    pour chaque (j := entier) de [0 .. début.longueur[:
        i ← i + 1
        t[i] ← début[j]

    pour chaque (j := entier) 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 :

Invariant de boucle : 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.

La preuve de l'invariant dans le corrigé est formelle mais évidente. Il n'est pas nécessaire (et on ne le fera plus) d'être aussi rigoureux pour des boucles aussi simple :

Lorsque le résultat d'une boucle est évidente, il n'est n'est pas nécessaire de faire une preuve formelle (qui sera souvent lourde et inintéressante).

Dans ces cas, contentez vous de donner l'invariant ou le résultat de la boucle.

Égalité de tableaux

Intersection non vide

Écrivez un algorithme itératif de signature :

algorithme intersection_non_vide(T1: [entier], T2: [entier]) → booléen

Permettant de vérifier que deux tableaux d'entiers $T$ et $T'$ contiennent les mêmes valeurs.

Il faut vérifier qu'il existe $0\leq i < T.\text{\small longueur}$ et $0\leq i' < T'.\text{\small longueur}$ tels que $T[i] = T'[i']$.

corrigé

 
algorithme intersection_non_vide(T1: [entier], T2: [entier]) → booléen
    pour chaque (x := entier) de T1:
        pour chaque (y := entier) 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.

Mêmes valeurs

Écrivez un algorithme itératif de signature :

algorithme égalité_valeurs(T1: [entier], T2: [entier]) → booléen

Permettant de vérifier que deux tableaux d'entiers $T$ et $T'$ contiennent les mêmes valeurs.

Il faut vérifier que pour pour tout $0\leq i < T.\text{\small longueur}$ il existe $0\leq i' < T'.\text{\small longueur}$ tel que $T[i] = T'[i']$.

corrigé

 
algorithme égalité_valeurs(T1: [entier], T2: [entier]) → booléen
    trouvé := booléen
    pour chaque (x := entier) de T1:
        trouvé ← Faux
        pour chaque (y := entier) 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.

Permutations

Terminons cette partie avec l'algorithme suivant :

Écrivez un algorithme itératif de signature :

algorithme permutation(T1: [entier], T2: [entier]) → booléen

Permettant de vérifier que deux tableaux d'entiers $T$ et $T'$ contiennent les mêmes éléments (même valeurs répétées le même nombre de fois), c'est à dire de savoir s'il existe une permutation $\sigma$ de $[0, T.\mbox{\small longueur}[$ telle que $T1[i] = T2[\sigma(i)]$ pour tout $i \in [0, T.\mbox{\small longueur}[$ (on a pas besoin de la donner).

Vous pourrez utiliser l'algorithme nombre qu'on a déjà étudié.

corrigé

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 := entier) 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]$.

Suppression de valeurs

Donnez et prouvez un algorithme itératif de signature :

supprime(T: [entier], v: entier) → [entier]

Qui rend un nouveau tableau contenant la restriction de t aux valeurs différentes de v.

Vous pourrez la encore utiliser l'algorithme nombre.

corrigé

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 := [entier]{longueur: taille t.longueur - nombre(T, v)}

    (j := entier) ← 0
    pour chaque (i := entier) 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 :

Invariant de boucle : à 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.

Et maintenant la version récursive :

Donnez et prouvez un algorithme récursif de signature :

supprime_rec(T: [entier], v: entier) → [entier]

Qui rend un nouveau tableau contenant la restriction de T aux valeurs différentes de v.

Vous pourrez utiliser l'algorithme concaténation de la question précédente.

corrigé

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

    t2 := [entier]{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.

Retournement d'un tableau

Donnez et prouvez un algorithme récursif de signature :

retournement_indice(t: [entier], i: entier) → ∅

Qui modifie le tableau passé en entrée (il ne rend rien !) de telle sorte que les éléments $t[j]$ et $t[t.\mbox{longueur} - 1 - j]$ soient échangés pour tous $i \leq j < t.\mbox{longueur} - i$

corrigé

 
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$.

Lorsque l'on manipule des indices de tableau il faut toujours :

  1. attentivement vérifier que tout se passe bien.
  2. faire attention aux divisions entières.

Encapsulez la fonction récursive retournement_indice(t: [entier], i: entier) → ∅ pour qu'elle puisse retourner un tableau passer en paramètre.

corrigé

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

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

Fonction 91 de McCarty

Terminons cette partie par une bizarrerie algorithmique comme on les aime. Elle vient de John McCarty, informaticien de renom et créateur du langage Lisp en 1958. Lisp est le premier langage fonctionnel et a été le deuxième langage de programmation au monde, deux ans après le Fortran.

La fonction 91 de McCarty :

Définition :

$$ M(n) = \left\{ \begin{array}{ll} n-10 & \mbox{si } n > 100 \\ M(M(n + 11))& \mbox{sinon.} \end{array} \right. $$

Implémentez un algorithme récursif qui mime la définition.

corrigé

 
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.

Le programme de la question précédente n'est pas forcément un algorithme puisqu'on ne sait pas si les récursion vont s'arrêter. Avant de répondre à cette question, montrons que l'on peut transformer cet algorithme en un programme itératif en appliquant les techniques de la récursion terminale :

Montrez que $M^k(n) = g(n, k)$ avec :

$$ g(n, k) = \left\{ \begin{array}{ll} n & \mbox{si } c = 0 \\ g(n-10, c-1) & \mbox{si } n > 100 \mbox{ et } c \neq 0 \\ g(n+11, c+1)& \mbox{sinon.} \end{array} \right. $$

En déduire une version itérative pour résoudre McCarty.

corrigé

 
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

On est pas vraiment sur que cette fonction soit bien définie et donc que le programme ci-dessus soit un algorithme ! Montrons le.

Démontrez que pour tout entier $n$ tel que $90 \leq n < 101$, on a $M(n) = M(n+1)$ et que l'on arrive à cette égalité en un nombre fini de récursion.

corrigé

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

$$ \begin{array}{lcl} M(n) & = & M(M(n + 11))\\ & = & M((n + 11) - 10)\\ & = & M(n + 1) \end{array} $$

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

Déduire de l'exercice précédent que pour tout $n < 101$, il existe $k\geq 1$ et $90 \leq n' < 101$ tels que $M(n) = M^k(n')$.

corrigé
$$ \begin{array}{lclr} M(n) & = & M^{2}(n + 11)&\\ & = & M(M(n + 11))&\\ & = & M(M^{2}(n + 22))&\\ & = & M^{3}(n + 22)&\\ & = & \dots&\\ & = & M^{p}(n + (p-1) \cdot 11)&\\ & = & M^{k}(n') &\mbox{ avec $k$ le premier entier tel que } n+(k-1)\cdot 11 \geq 90\\ \end{array} $$

Donnez la valeur de $M(n)$ pour tout $n< 101$ et en déduire que la fonction de McCarty est bien définie pour tout entier positif (ie. le calcul se fait en un nombre fini de récursion).

corrigé

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$).

En déduire un algorithme itératif ultra simple pour la calculer.

corrigé

 
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.