Algorithme polynomial et preuve de programme
Bonjour , je viens de tomber sur deux exercices un sur algorithme polynomial et deuxiéme sur preuve de programme que je ne vois pas comment le faire , sachant que cé pas un devoir just je m'entraine pour mes examens .
Exercice 1:
proposer un algorithme polynomial (en fonction de la taille m) qui calcule l'expression ( a^b mod n) où a ,b et n sont trois grand nombres .Evaluer et justifier la compléxité de cet algorithme .
Illuster votre algorihme pour calculet (7^253 mod 9) .
Exercice 2:
donner la preuve de programme suivant:
On supose que A et B sont positifs :
Code:
1
2
3
4
5
6
7
8
| {T}
x<-A
y<-B
while x!= 0 do
x<- x-1
y<-y+1
end wihle
{(y = A +B ) /\ (x=0)} |
Merci pour votre réponse .
