Bonjour,

Je dois rédiger un rapport assez complexe et dans une partie, il faut que je montre que l'algorithme est correcte, par récurrecence, invariant ou autre.

Voici l'algorithme :

Entier PLSCA(X, Y , m, n)
Debut
  Pour i := 0 a m faire
    L(i; 0) := 0;
  Fin
  Pour j := 0 a n faire
    L(0; j) := 0;
  Fin
  Pour i := 1 a m faire
    Pour j := 1 a n faire
      Si X[i] = Y [j] alors
        L(i, j) := L(i-1,j-1) + 1 ;
      Sinon
        L(i, j) := max {L(i, j-1),L(i-1, j)} ;
      Fin
    Fin
  Fin
  retourner L(m, n) ;
Fin

Il cherche la plus longue sous-séquence commune entre 2 chaines de caractère

J'ai commencer la preuve comme ceci :

invariant :
S(k): nous savons qu'a un certain moment nous nous trouvons a la ligne i et la colonne j. Si i+j=k et si L(i,j)=V, nous avons a cet endroit trouvé V éléments pour la plus longue sous-séquence commune.

Base :
Si k=0 alors i+j=0, ce qui veut dire que i=0 et j=0. Nous savons, conformément au théoreme que nous ne trouverons pas d'avantage d'élément pour la plus longue sous-séquence commune puisque L(0,0)=0, l'hypothese est donc vérifiée pour i+j=0

la réccurence :

La je bloque, je pense démarrer par "Si la proposition est vrai pour i+j=k alors elle l'est pour i+j=k+1" mais faut faire tout le traitement et la je ne vois pas du tout, si jamais quelqu'un peut m'aidé

merci