Onpeutre´sumerunprobl`emeenuneformelogique: E P S |{z} |{z} |{z} Logique du 1er ordre Programme Logique du 1er ordre Dela`,plusieursreglesagissentsurcesenonces: ` ´ ´
1.1R`eglesetaxiomes R´egledelapost-condition: EP S0;S0⇒S−7→EP S
Re´gledelapr´e-condition: E0P S;E0⇒E7−→EP S
R´egleduou: EP S;E0P S−→7(E∨E0)P S
Re´gledutextitet:
EP S;EP S07−→EP(S∧S0)
3
R`egledusi-sinon: (E∧B)P S; (E∧B)QS→7−E{Si B alors P sinon Q}S Remarque:L’e´valuationdeBnedoitpasmodifierE. Re`gledutant-que: (E∧B)P E;−7→E{tant que B f aire P}(E∧B)
Axiomes d’affectation : EP A;AQS→7−E{P;Q}S
Exemple ::trermeno´D EP S;E0P S07−→(E∧E0)P(S∨S0) 1.EP S 2.E0P S0 3.E∧E0⇒E 4. (E∧E0)P Ste1rusnoitidnocer´(P3) 5. (E∧E0)P S0oisnrue2e´ocdnti(Pr)t3 6. (E∧E0)P(S∧S0udeR()lge`ETsur 4 et 5) 7. (S∧S0)⇒(S∨S0) 8. (E∧E0)P(S∨S0) (Postcondition sur 7 et 8)
1.2 Construction de programmes sur invariant Construire un prog d´crit par l’invariant, c’est utiliser une proposition ramme e bool´eenneI(x1, x2,∙ ∙ ∙, xn), fonction de plusieurs variablesxitleprobluid´ecriq,e`em a`uninstantdonne´.Lorsquel’onveutfaireunalgorithmequire´soudEP Sas´ebsur un invariant, on doit donner plusieurs propositions : Invariant :selbD´ecritlaposiitnoudrpbo`lmeeenfonctiondevariaxi. Initialisation :Ce sont des conditions sur les variablesxi, tels que la proposition Eerv´itsoet´eifiI(xit´egalem)lesoine.t Conditiond’arrˆet:Ce sont des conditions sur les variablesxi, tels que la propo-sitionS´ifilee,ogprmmraa’dneˆrrtsetre´v.Leefi´ri´etvoisoitidnocaleuqsro e e doit avoir fini son traitement, etSe´fiirevt.ees Implications :Elles sont de la formeI(x1, x2,∙ ∙ ∙, xn)Vi(Pivraies)⇒I(x01, x02,∙ ∙ ∙, x03). Ou`Pisopisitnontdespropresentee´r Onende´duitl’expression: I(xi)T AN T QU EoC(ˆet)’arriondnditF AIRE PiI(xi)∧(oiodCndntieˆ)ta’rr
4
1.2.1Exemple:sommedese´le´mentsd’untableau Soitunprogrammere´alisantlasommedetousles´ele´mentsde0a`n−1 d’un tableauTutpnorrgmaemvPe´.Onveu:tnaviusl’ntfiari´encno´e n−1 (n >0)PS=XT[i]! i=0
En sortie du programme, on auraI(s, k)∧(k=n). La translation de cet algorithme enpseudolangageesttre`ssimple:
s <- 0 k <- 0 // Ici on a I(0,0) tant que (k != n) faire : s <- s + T[k] // Ici on a I(s,k+1) k <- k + 1 // Ici on a I(s,k) fin tant que // Ici on a I(s,n)
2.1Remarquessurl’e´valuationdecomplexite´d’un programme Dansceparagrapheetceuxquisuivront,nousallons´evaluerletempsd’e´xecution des programmes en fonction de la taillenargosemm,orlbdpu.Com`emer2prpare c’estcomparerlestempsd’e´xecutiondanslespiresdescasrespectifs.Lesconstantes de´pendentdelamachinequi´executeral’algorithme.
D´efinition:LesePecedtgorpmmar´eomplexitO(f(n)) s’il existeαetn0tels que : ∀n≥n0Tp(n)≤αf(n) O`uTp(nas.descpiresnelPeadarmmrpgoticuduond’psxe´eletnmeterperese´) Remarque :Si le programme P est enO(n), alors il est aussi enO(2n),O(n2) ou O(n2).
2.2 Recherche dichotomique Supposonsquel’onchercheun´ele´mentnot´eedans un tableauT. Le programme derecherchedichotomiquequenousallonsmettreaupointre´pond`al’´enonc´esui-vant : (T[0]≤e≤T[n−1])RD(T[k]≤e≤T[k+ 1]) Invariant :I(i, j)≡T[i]≤e≤T[j−1] Conditiond’arrˆet:j=i+ 2 Initialisation :(i= 0)∧(j=n)