Discussion :

[larchicha]

Bonjour à tous,

J'ai devant les yeux un algorithme itératif de tri (qui ressemble pas mal au tri-par-tas) et je me rends compte que théoriquement je sais comment le prouver mais à la pratique je tremblotte...

On a donc :

Code :

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

1
2
3
4
5
T : tableau de n*n initialisé avec des "-0-";
pour i de 1 à n² faire : 
              Insertion(T,T[i]);//insertion de T[i] dans le tableau T
pour i de 1 à n² faire :
              T[i] = ExtraireMin(T);//qui extrait la valeur la plus petite du tableau T

Pour la terminaison : Lorsque la variable i = n², les 2 boucles pour se terminent ainsi que l'algorithme. (c'est le cas d'arrêt).

Pour l'invariant de boucle, je bloque un peu : " Au k-ième tour de boucle, le tableau T, contenant k termes, est trié par ordre croissant ".

En effet, à l'état initial -avant le premier tour de boucle -, on a tableau vide donc trié par ordre croissant. (ça signifie quelque chose ça ?!)

Edit: Pas vide en fait, remplit de -0-... mais ça ne m'aide pas...Oo

Au premier tour de boucle, i = 1 et le tableau T contient 1 élément qui est donc trivialement trié.

Au dernier tour de boucle, i = n² et T contient n termes trié par ordre croissant . (on revient à la terminaison ?!).

Merci d'avance pour l'aide et les explications apportées.

[pseudocode]

insertion de T[i] dans le tableau T

Déjà, ca me semble curieux de mettre le i-ème élément de T dans le tableau T... vu qu'il est déjà dans T.

Je pense que ca sera plus clair avec un algo moins introspectif.

[larchicha]

euh à vrai dire, j'ai le choix de l'invariant, pas de l'algo...
Les commentaires (idiots) du code n'était pas forcément nécessaire je l'avoue...

Mais que pensez vous de l'invariant s'il vous plait ?

[Franck Dernoncourt]

Comme le souligne pseudocode, le code que tu donnes est assez véreux, mais si on en fait abstraction,

• pour la première boucle pas besoin d'invariant (ou sinon juste dire que le tableau est rempli de 0 donc trié),
• pour la seconde boucle l'invariant est comme tu le proposais " Au k-ième tour de boucle, le tableau T, contenant k termes, est trié par ordre croissant ".

[pseudocode]

euh à vrai dire, j'ai le choix de l'invariant, pas de l'algo...
Les commentaires (idiots) du code n'était pas forcément nécessaire je l'avoue...

C'est pas tant le commentaire que le nom de la variable 'T' qui devrait avoir un autre nom, genre 'Temp'.

pour la seconde boucle l'invariant est comme tu le proposais " Au k-ième tour de boucle, le tableau T, contenant k termes, est trié par ordre croissant ".[/LIST]

C'est même plus fort que cela.

Au k-ième tour de boucle: T[1],...,T[k] = Les k plus petits élements de T, triés par ordre croissant

[larchicha]

Merci de ces précisions messieurs...(ou mesdames).
Votre aide est grandement appréciée.