Recherche:

oui j ecris un algo et je dois prouver qu'il est correct.
c'est moi qui choisit de le prouver par les invariants de boucles.J'ai lu que c une methode pour demontrer qu'un algo est correct
Trouver...

mais la je crois que je n ai pas bien pigé ce que c est qu un invariant.
je viens de lire un exemple
l'algo d euclide
ils disent que a=B*Q+R est un invariant de boucle alors qu ici aussi a ne...

je vais modifier un truc dans mon algo encore

c:=b^t mod (p);
r=a^(t+1)/2 mod p;
Pour i=1 à s-1 faire
d=[(r^2)a^-1]^2^(s-i-1);
si d<>1 mod p faire
r:=r*c mod(p);
c:=c^2 mod p;
finsi

je veux trouver les racines de a mod p
est ce que je peux dire que a=r^2 est un invariant de boucle
je crois que ce doit etre verifier a chaque fois dans mon algo
quitte a le verifier je vais...

c est ceci pour etre bien precise
r=[a^((t+1)/2)]mod p

le 2 est dans la puissance


Ensuite ou se termine ta boucle Pour ? (je suppose juste avant le tant que mais suis pas sur)
Non tant...

cet algo je l'ai redigé suite a bcp d'autres questions precedentes
en supposant donc que je l'ai trouvé

c:=b^t mod (p);
r=a^(t+1)/2 mod p;
Pour i=1 à s-1 faire
d=[(r^2)a^-1]^2^(s-i-1);
...

moi jai un algo ou je dois je crois trouver l invariant de boucle et meme montrer qu il est invariant de boucle

est ce a dire que l'invariant de boucle est ce que je j'obtiens a la sortie de ma boucle.
Et s'il me faut verifier que certaines conditions sont des invariantes de boucles,je reprends juste le...

Saurait tu ce qu'on entend par invariant de boucle?
Serait ce les variables qui dans une boucle n evolue pas au fil des calculs ou bien quoi
merci

merci pour ton intervention
le probleme est juste poser prouver que cette algo est correct
je ne connais ces tests dont tu parles.
Je ne suis pas une informaticienne (Pvs,coq...je ne sais pas de...

Optimiser un algorithme !!
i.e. ameliorer veux tu dire?
merci

Que doit on faire exactement quand on doit montrer qu'un algo est correct?

Ce n'est pas quand même prendre un exemple, vérifier pour trouver le résultat!