Discussion :

[caroline-bx1]

Salut! Est-ce que quelqu'un saurait donner l'invariant de boucle du programme suivant: (le programme teste si le mot est un palindrome)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
int i:=0;
int j:=n-1;
boolean ok := true;
while i<=j ET ok, do
    if a[i]=a[j]
    then
        i=i+1
        j=j-1
    else
      ok:=false
    endif
done

Merci beaucoup!!!!!!!

[Malinaka]

Dans de lointains souvenirs d'algo je penserai que l'invariant vaut a[i]=a[j] en notant que j=n-(i+1) ,histoire de symétrie. Donc la complexité dans le pire des cas est de O(n/2), le pire des cas étant que le mot sot un palindrome. Mais la preuve est à faire ...

[Franck Dernoncourt]

Dans de lointains souvenirs d'algo je penserai que l'invariant vaut a[i]=a[j] en notant que j=n-(i+1) ,histoire de symétrie. Donc la complexité dans le pire des cas est de O(n/2), le pire des cas étant que le mot sot un palindrome. Mais la preuve est à faire ...

Non, ce n'est pas ça.
L'invariant est quelque chose du genre "Les i premiers caractères de a sont les mêmes que les i derniers caractères de a". Je te laisse le soin de le formaliser

[Malinaka]

Je te crois sur parole, je me rapelle surtout de vagues formules mathématiques de mes cours d'algo... La seule chose qui m'ait marqué c'est la compléxité

[prgasp77]

Bonjour,
l'invariant de boucle n'est-il pas une propriété toujours vraie à chaque itération. ? Ici, pour une certaine fonction f, ce serait f(i,j)=0.

[Franck Dernoncourt]

heu pourquoi f(i,j)=0 et qui est f ? je ne vois pas ce que tu veux dire mais peut-être est-ce parce que ma journée a été longue

Sinon, pourquoi l'invariant "Les i premiers caractères de a sont les mêmes que les i derniers caractères de a". ne serait-il pas vrai à chaque itération de la boucle ?

[prgasp77]

Oula ... ma journée a été longue aussi

Ici, pour une certaine fonction f, ce serait f(i,j)=0.

J'utilisais une fonction non définie pour éviter de donner un résultat de but en blanc ; il s'agissait de l'addition tout simplement : i+j=n pour chaque itération.

pourquoi l'invariant "Les i premiers caractères de a sont les mêmes que les i derniers caractères de a". ne serait-il pas vrai à chaque itération de la boucle ?

C'est tout a fait vrai, et cet invariant a plus de porté que celui que je propose.

Si vous me cherchez, je serai dehors.

[ben51]

C'est que la distance entre i et le début du tableau est toujours égale à la distance entre j et la fin du tableau.

Par-contre tu es dans quel groupe ?