algorithmique permutations (ADA)

[invite466d2360]

S.T(i) c'est quoi ? la valeur de l'entier à l'indice i dans la séquence S ???

Oui tout à fait...Enfin c'est ce qui est écrit dans mon cours...
S.T(i)=TdeS(i)= valeur de l'entier à l'indice i dans la séquence S
-----

[invite7a96054d]

OK, pour moi T était une permutation et je comprenais S[T[i]] ...

Ce que tu cherches prouver c'est qu'à la sortie de la boucle tu auras affiché tous les éléments de S et dans l'ordre. L'invariant va fortement ressembler à celui de la version avec permutation, avec quelques trucs à démontrer sur IPPS ...

[invite466d2360]

Franchement...Comment arrives-tu à trouver un truc pareil?

Inv(S,T,i, compteur) = (i=0 et compteur=LdeS) ou (i!=0 et S[T[i]] est le plus petit élément de S non encore affiché)

franchement je suis impressionné Je ne serais jamais capable de trouver des invariants si complexe ^^
Bon à démontrer une fois qu'on l'a c'est plus simple mais franchement pour sortir ça...

OK, pour moi T était une permutation et je comprenais S[T[i]] ...

Ah non c'est tableau de la séquence. Oui je trouve ça absurde comme notation ^^ T(i) ou à la rigueur S(i) porterait moins à confusion...

L'invariant va fortement ressembler à celui de la version avec permutation,

en fait il ne change pas vraiment non? C'est juste que comme ce que tu avais compris T comme permutation (ce qui était P pour moi) j'ai juste à faire:Inv(S,i, compteur) = (i=0 et compteur=LdeS) ou (i!=0 et S.T[i]] est le plus petit élément de S non encore affiché) non?

[invite7a96054d]

C'est ça. Mais en fait ce n'est pas si compliqué, il faut formaliser ce que tu cherches à démontrer, et à défaut un prédicat qui est suffisament fort pour prouver ce que tu veux.

[invite466d2360]

Merci pour tout kwariz
Je comprends beaucoup mieux les choses avec tes explications
Très bonne fin de week-end à toi!

Mägodeoz