Proiectarea algoritmilor

1

1. Verificare. Corectitudine1.a. Algoritm- proprieti1.b. Verificarea algoritmului- Verificare experimental- Verificare analitic;1.c. Variabilele i strile unui program1.d. Metod formal de analiz a corectitudinii

AlgoritmGeneza cuvntului algoritm: Este legat de numele savantului AI-Khwarizmi (algoritmi) matematician, geograf, astronom i astrolog persan (780-850 d.Hr.), considerat i printele algebrei moderne.Proiectarea algoritmului const n dou etape: Descrierea algoritmului printr-un pseudolimbaj(schem logic, pseudocod); Demonstrarea corectitudinii rezultatelor n raport cu datele de intrare.Analiza algoritmului se refer la evaluarea performan-elor acestuia (timp de execuie, spaiu de memorie).

Algotirm definiii, caracteristiciAlgoritmul este o secven de operaii care transform mulimea datelor de intrare n date de ieire, sau ntr-o definiie mai exactEste un set de pai executabili, descrii fr echivoc, care definesc un proces finit.Caracteristici legate de definirea algoritmului:Finititudine; Generalitate;Corectitudine (determinism);Completitudine.

Proprietile algoritmuluiProprieti care definesc modalitatea de descriere a algoritmului:Concizia;Claritatea;Rigurozitatea;Proprieti legate de executare algoritm:Executabilitatea descrie prelucrrile numai prin intermediul unor operaii care pot fi executate n calculator;Eficiena Gradul n care executarea se reali- zeaz cu consum redus de resurse (timp, memorie, etc.)Verificarea corectitudinii algoritmuluiEtapele verificrii:I. Experimental Testarea algoritmuluipentru stri particulare aleproblemei;II. Analitic Demonstrarea riguroas, formal, a funcionrii corecte pentru oriceset de date de intrare;Etapele verificrii analiticeIdentificarea proprietilor datelor de intrare (precondiiile problemei).Identificarea proprietilor pe care trebuie s le satisfac rezultatul (postcondiiile problemei).Demonstrarea faptului c pornind de la precondiii i aplicnd prelucrrile specificate n algoritm se ajunge la satisfacerea postcondiiilor.

Variabilele i strile unui algoritm (program)

Prin examinarea unui algoritm codificat ntr-un limbaj de programare se identific dou aspecte: controlul execuiei instruciunilor (if-then, etc); execuia comenzilor (ca asignri de valori rezultate n urma unor evaluri).Pentru fiecare variabil a programului exist o stare care conine informaia curent la orice moment de timp.Aceast stare este identificat prin valoarea variabilei care poate fi schimbat prin execuia unei comenzi.

Starea unui programS presupunem c fiecrei variabile a unui program iasociem una din axe ntr-un spaiu cartezian multidimensional, care se va numi spaiul strilor unui program.Un punct n acest spaiu este o stare a programului.Execuia unei comenzi elementare este vizualizat n acestspaiu ca un segment ce leag starea programului nainte de execuie de cea de dup execuie.n acest context, spaiul strilor este o mulime a tuturor variabilelor programului.

Precondiii- PostcondiiiExpresia condiiilor care trebuie satisfcute, n spaiul strilor, pentru o execuie corect a programului, se numete precondiie.Specificaiile strilor la terminarea algoritmului (programului) se numesc postcondiii.Ideea verificrii este de a stabili care trebuie s fie starea la fiecare moment astfel nct n final s fie satisfcute postcondiiile. O dat stabilite strile intermediare este suficients se verifice c fiecare prelucrare asigur transformarea strii care o precede n cea care o succede.Starea algoritmului este modificat prin atribuiri de valori variabilelor.Metode de proiectare-verificare formaln conformitate cu Dijkstra, programatorii potutiliza trei modaliti de proiectare a algoritmilor:Enumerarea,Inducia matematicAbstractizarea.

EnumerareaInstrumentul mental al enumerrii este principala metod folosit de programatori. Utilizm gndirea enumerativ ori de cte orivrem s instruim pe cineva despre execuia mai multor activiti.

Inducia matematicEste foarte utilizat pentru proiectarea i verificarea structurilor repetitive (cicluri).Inducia matematic este un proces mental natural ca i enumerarea.n general, principiile induciei pot fi definite astfel:1. Ba za induciei este de a stabili c un anumit element p al unui mulimi S satisface o relaie R.2. Pasul induciei este de a arta c un element generic y a lui S satisface R, adic exist T(y), unde T este orice fel de transformare n care alt element a lui S satisface R.3. Dac baza i pasul induciei sunt demonstrate, atunci orice element derivnd din p printr-un num r de aplica ii a le lui T, de asem enea satisface R.

Verificarea structurilor secveniale i repetitiven cazul prelucrrilor secveniale (succesiuni de atribuiri), verificarea este n general simpl constnd n a analiza succesiv efectul fiecrei atribuiri asupra strii algoritmului.Structurile repetitive reprezint principala surs de erori din cauz c se pot specifica greit iniializrile, prelucrrile din corpul ciclului sau condiia de oprire (continuare).Pentru a demonstra c o prelucrare repetitiv este corect se folosete adesea metoda induciei matematice.Exemplu:Minimum dintr-un ir finit de numereminim(n,a)min a[1]FOR i 2,n DOIF min > a[i] THENmin a[i]; RETURN min;Analiza algoritmului minim (n,a)Enunul problemei nu impune nici o restricieasupra tabloului a[1,..,n] deci setulde precondiii este constituit doar din n 1 (irul nu este vid). Postcondiia este min a[i] pentru oricei = 1,2,.., n. Rmne s artm c postcondiia rezult n urma aplicrii algoritmului.

Demonstrm prin inducie matematicdup variabila i c min a[i], i = 1,2,..,n.1.Cum min = a[1] i valoarea lui min este nlocuit doar cu una mai mic rezult c min a[1].2.Presupunem c min a[i] adevrat pentru orice i.Rmne s artm c min a[i+1].3.La pasul i al ciclului FOR valoarea lui min se modific astfel:Dac min a [i+1] atunci min rmne nemodificat.Dac min > a [i+1] atunci min se nlocuiete cu a [i+1].Astfel n oricare dintre variante se obine c min a[i+1].Conform metodei induciei matematice rezult c postcondiia este satisfcut, deci algoritmul este corect.

Dac algoritmul este:minim(n,a)min a[1];FOR i 1,n-1 DOIF a [i+1] > a [i] THENmin a[i];ELSEmin a[i+1];

RETURN min;n acest caz prelucrarea din corpul ciclului conduce la min = min {a[i], a[i+1]} astfel c nu se mai poate demonstra c pornind de la min = min{a[1],..,a[i]} c min = min{a[1],..,a[i+1]}.Contraexemplu - irul {2, 1, 3, 5, 4} pentru care algoritmul de mai sus nu funcioneaz corect.n schimb se poate demonstra c algoritmul returneaz min{a[n-1], a[n]}

Abstractizarea procedural- Metod formal de analiz a corectitudinii Ea const din abstractizarea unei piese din program(de regul nescris nc) prin substituirea n textul su a precondiiei i postcondiiei.Astfel intreaga structura a programului poate fi definita si se demonstreaza corectitudinea lui prin utilizarea unui text mai scurtMetod formal de analiz a corectitudiniiPe baza precondiiilor i postcondiiilor problemei se stabilesc aseriuni pentru fiecare prelucrare privind valorile datelor i relaiile dintre ele;Pentru fiecare prelucrare se demonstreaz c ea asigur satisfacerea aseriunii care o urmeaz, dac este satisfcut aseriunea care o precede. Notm cu P precondiiile problemei, cu A algoritmul i cu Q postcondiiile. Spunem c tripletul (P, A,Q) formeaz un algoritm corect, i notm , P AQDac urmtoarea afirmaie este adevrat:

Dac datele problemei satisfac precondiiile P atunci:A. rezultatul satisface postcondiiile Q;B. algoritmul A se termin dup un numr finit de pai.

Verificarea poate fi descompus la nivelul structurilor de prelucrare. Pentru fiecare dintre structurile de prelucrare exist reguli care uureaz verificarea.Vom stabili reguli pentru cele trei structuri fundamentale conform teoremei de structur: structura secvenial, structura alternativ i structura repetitiv.

I. Regula structurii secveniale Fie algoritmul A constituit din succesiunea de prelucrri (A1,A2,..,An).Notm cu Pi-1 i Pi starea algoritmului nainte i respectiv dup efectuarea prelucrrii Ai. Regula structurii secveniale poate fi enunat astfel:

Dac P P0, Pi1 A P pentru i=1,2,..,n iPn Q, atunci iP AQ

Exemplu

Fie n i m dou valori ntregi, iar x i y dou variabile ce conin valorile n i m. S seschimbe ntre ele valorile celor dou variabile.

Precondiiile problemei sunt:

{x = n, y = m},

Postcondiiile sunt {x = m, y = n}.

Consideram prelucrrilealgoritmului:

A1: aux xA2: x yA3: yaux P0 = {x = n, y = m} (nainte de A1) P1 = {aux = n, x = n, y = m} (dup A1) P2 = {aux = n, x = m, y = m} (dup A2) P3 = {aux = n, x = m, y = n} (dup A3)Este uor de remarcat c P = P0, P3 Q,pentru i=1,2,3.

Pi1

Ai PiDac ns algoritmul de maisus se nlocuiete cu:

A1:x yA2:y x Aseriunile corespunztoare sunt:

{x = m, y = m}, att dup A1 ct i dup A2.

n acest caz aseriunile A1 i A2 nuconduc la postcondiia Q.Aceeai problem poate fi rezolvat fr afolosi o variabil auxiliar efectund

prelucrrile:

A1: x x - y A2: y x + y A3: x y - xAseriunile privind strile algoritmului sunt : P0 = {x = n, y = m} (nainte de A1)P1 = {x = n - m, y = m} (dup A1)P2 = {x = n - m, y = n} (dup A2) P3 = {x = m, y = n} (dup A3)

i Este uor de remarcat c P = P0, P3 Q,pentru i=1,2,3. Pi1 Ai P

Reguli

a) ntrirea precondiiei Dac R P i P AQ

atunci , R AQ adic algoritmul rmne corect dacse particularizeaz datele de intrare.b) Slbirea postcondiiei Dac Q

R i

P AQ

atunci , P A R adic algoritmul rmne corect dacse reduc cerinele pentru datele de ieire.c) Proprieti nsoitoare

Dac 1212P AQ i P AQ atunci P1 P2 1 2AQ Q

Regula structurii alternative

Considerm stuctura:IF c THENA1ELSEA2 Dac P i Q sunt precondiiile, respectiv postcondiiile atunciregula poate fi enunat n modul urmtor: Dac c este bine definit (poate fi evaluat), atunci iP c A1 Q , P c A2 Q si deci P AQ

Regula sugereaz c trebuie verificat corectitudinea fiecrei ramuri (att cnd c este adevrat ct i n cazul n care este fals).Exemplu. Considerm problema determinrii

minimului dintre dou valori reale, distincte

IF a < b THENm aELSE

m b

Precondiiile sunt: a R, b R, a b Postcondiia este m = min{a, b}. Condiia c este a < b. Dac a < b atunci m = a < b deci m = min{a, b}. n caz contrar (a > b) iar prelucrarea de pe ramura ELSEconduce la m = b < a deci din nou m = min{a, b}.

Regula structurii repetitive

Deoarece toate structurile repetitive pot fi transformate ntr-o structur repetitiv cu test iniial o vom analiza doar pe aceasta. Fie structura:S: WHILE c DO A; Precondiia P i Postcondiia Q. Structura repetitiv este corect dac exist o aseriune I (numit invariant al prelucrrii repetitive) asociat strii algoritmului i o funcie t : N N (numit funcie de terminare i care depinde de numrul de ordine al iteraiei) care satisfac proprietile:

(a) Aseriunea I este adevrat la nceputulprelucrrii repetitive (P I).

(b) Aseriunea I este invariant: dac I este adevrat nainte de efectuarea lui A iar c este adevrat atunci I rmne adevrat idup efectuarea lui A ( I c A I )

(c) La sfritul structurii repetitive (cnd cdevine fals) postcondiia Q poate fi dedus

din ( I c AQ).

(d) Dup efectuarea prelucrrii A valoarea lui tdescretec t( p) k At( p 1) k

(e) Dac c este adevrat atunci t(p) 1 (mai exist cel puin o iteraie), iar cnd valoarea lui t este 0 condiia c devine fals (algoritmul setermin dup un numr finit de iteraii).

Elementul esenial n demonstrarea corectitudinii unei prelucrri repetitive l reprezint gsirea proprietii invariante.

Aceasta este o aseriune particular privind relaiile dintre variabilele algoritmului, care este adevrat nainte de intrarea n prelucrarea repetitiv, rmne adevrat dup fiecare iteraie iar cnd condiia c devine fals implic postcondiiile. Gsirea unui invariant elimin necesitatea demonstra-iei explicite prin inducie matematic.

Dac se demonstreaz doar faptul c algoritmul produce rezultatul dorit fr a se analiza i terminarea acestuia atunci despre algoritm se spune c este parial corect.

Un algoritm este considerat complet corect atunci cnd se justific i faptul c produce rezultatul dup un numr finit de operaii.

Exemplul 1.Relum problema determinrii minimului

dintr-un ir finit de valori

minim(n,a)A1: min a 1{min=a[1]} A2: i 2 {min=a[1], i=2} A3: WHILE i n DOA4: IF min > a[i] THENA5: min a[i] {min a[j], j=1,2,..,i} A6: i i+1 {min a[j], j=1,2,..,i-1} RETURN min {min a[j], j=1,2,..,n}

Precondiia este reprezentat de n 1,Postcondiia este min x[i] , i = 1,2,.., n.

Aseriunile marcate dup fiecare prelucrare sunt uor destabilit.Proprietatea invariant este min a[j], j =1,2,..,i-1. ntr-adevr, dup prelucrarea A2 proprietatea este satisfcut. Din aseriunea specificat dup A6 rezult c proprietatearmne adevrat dup fiecare iteraie.Condiia de oprire este i = n + 1 i se observ c atunci cnd este satisfcut, aseriunea final implic postcondiia.Funcia de terminare este t(p) = n + 1 -ip, unde ip este valoarea indicelui i corespunztor iteraiei p. Cum ip+1= ip +1 rezult c t(p + 1) < t(p), iar t(p) = 0 implici = n + 1 adic condiia de oprire a algoritmului.S considerm calculul sumei, S, a primelorn numere naturale (n 1).

Precondiia este P ={ n 1 } iar Postcondiia este Q = {S = 1 + 2 +...+ n}. ntruct suma va fi calculat adugnd succesiv termenulcurent, i, un invariant adecvat ar fi S = 1 + 2 + .. + i.

Pentru a asigura validitatea acestui invariant, termenul curent trebuie pregtit chiar nainte de a fi adugat. Pe de alt parte pentru a ne asigura c la finalul ciclului postcondiia este satisfcut rezult c la ieirea din ciclu variabila i trebuie s aib valoarea n. Astfel condiia de continuare a ciclului WHILE ar trebui sfie i < n.Toate aceste observaii conduc la

algoritmul:

Sum(n)

i 1

S 1

WHILE i < n DO

i i+1S S + i

RETURN S

Este uor de remarcat faptul c exist i alte variante corecte de calcul a sumei. Una dintre acestea este:

Sum(n)i 1S 0WHILE i n DOS S + ii i+1RETURN S Corectitudinea acestui algoritm poate fi demonstratfolosind invariantul:S = 1+2+...+(i-1).