+ All Categories
Home > Documents > Pc_Cap2 2.4 ; 2.5 - Timpul de Executie

Pc_Cap2 2.4 ; 2.5 - Timpul de Executie

Date post: 16-Nov-2015
Category:
Upload: bogdan-mihai-dumitru
View: 230 times
Download: 1 times
Share this document with a friend
30
2. Algoritmi După cum s-a specificat în paragraful 1.3, etapa preliminară scrierii unui algoritm de rezolvare a unei probleme este analiza acesteia, în cadrul căreia trebuie determinate mărimile de intrare, cele de ieşire, precum si relaţiile ce conduc la obţinerea marimilor de ieşire. În cadrul etapei de descriere a algoritmului de rezolvare a problemei, trebuie descrisă de fapt succesiunea operaţiilor care realizează relaţiile determinate anterior. Un algoritm care nu este precedat de o analiză corectă a problemei de rezolvat este de cele mai multe ori un algoritm eronat sau neperformant. 2.1. Definirea şi proprietăţile algoritmilor Noţiunea de algoritm se referă în mod uzual la o metodă de descriere a rezolvării unor probleme. Mai exact, un algoritm reprezintă o multime finită de operaţii care se aplică asupra unor mărimi de intrare ale unei probleme pentru a obţine rezultatele sau mărimile de ieşire ale acesteia. Principalele noţiuni implicate sunt descrierea unui algoritm si execuţia algoritmului. Pentru a descrie corect un algoritm, trebuie ales un limbaj adecvat de descriere, cu o suficientă putere expresivă, care să poată descrie operaţiile (din cadrul domeniului din care face parte problema respectivă) ce se pot efectua asupra datelor probl emei. Execuţia unui algoritm se referă la componenta pragmatică a limbajului de descriere; în mod uzual un algoritm trebuie să poată fi executat de către o persoană care are cunostinţe din domeniul problemei de rezolvat, folosind doar creionul si hârtia. Unul dintre primele limbaje de descriere a algoritmilor a fost limbajul natural. Acesta are o mare flexibilitate şi permite descrierea multor tipuri de operaţii. În mod uzual, se folosesc propoziţii pentru a descrie fiecare operaţie din cadrul algoritmilor. Pentru a evidenţia succesiunea operaţiilor, acestea se numerotează cu numere crescătoare. O asemenea operaţie descrisă printr-o propoziţie numerotată se mai numeşte pas. În acest mod, un algoritm este reprezentat de o secvenţă de paşi. Exemplul 2.1. Să se determine cel mai mare divior comun a două mumere întregi folosind algoritmul lui Euclid. Analiza problemei. Vom nota cu m şi n numerele pentru care trebuie determinat cel mai mare divizor comun. Astfel, variabilele m şi n reprezintă variabile de intrare pentru problemă. Algoritmul lui Euclid presupune efectuarea repetată a unor operaţii de împărţire cu rest, până când se obţine un rest zero. Fie de exemplu: m=8, n=12: 8=0*12+8 (r 1 =8) 12=1*8+4 (r 2 =4) 8=2*4+0 (r 3 =0) Ultimul rest nenul (r 2 =4) va fi solutia problemei.
Transcript
  • 2. Algoritmi

    Dup cum s-a specificat n paragraful 1.3, etapa preliminar scrierii unui algoritm de

    rezolvare a unei probleme este analiza acesteia, n cadrul creia trebuie determinate mrimile

    de intrare, cele de ieire, precum si relaiile ce conduc la obinerea marimilor de ieire. n

    cadrul etapei de descriere a algoritmului de rezolvare a problemei, trebuie descris de fapt

    succesiunea operaiilor care realizeaz relaiile determinate anterior. Un algoritm care nu este

    precedat de o analiz corect a problemei de rezolvat este de cele mai multe ori un algoritm

    eronat sau neperformant.

    2.1. Definirea i proprietile algoritmilor

    Noiunea de algoritm se refer n mod uzual la o metod de descriere a rezolvrii unor

    probleme. Mai exact, un algoritm reprezint o multime finit de operaii care se aplic asupra

    unor mrimi de intrare ale unei probleme pentru a obine rezultatele sau mrimile de ieire

    ale acesteia.

    Principalele noiuni implicate sunt descrierea unui algoritm si execuia algoritmului.

    Pentru a descrie corect un algoritm, trebuie ales un limbaj adecvat de descriere, cu o

    suficient putere expresiv, care s poat descrie operaiile (din cadrul domeniului din care

    face parte problema respectiv) ce se pot efectua asupra datelor problemei. Execuia unui

    algoritm se refer la componenta pragmatic a limbajului de descriere; n mod uzual un

    algoritm trebuie s poat fi executat de ctre o persoan care are cunostine din domeniul

    problemei de rezolvat, folosind doar creionul si hrtia.

    Unul dintre primele limbaje de descriere a algoritmilor a fost limbajul natural. Acesta

    are o mare flexibilitate i permite descrierea multor tipuri de operaii. n mod uzual, se

    folosesc propoziii pentru a descrie fiecare operaie din cadrul algoritmilor. Pentru a evidenia

    succesiunea operaiilor, acestea se numeroteaz cu numere cresctoare. O asemenea operaie

    descris printr-o propoziie numerotat se mai numete pas. n acest mod, un algoritm este

    reprezentat de o secven de pai.

    Exemplul 2.1. S se determine cel mai mare divior comun a dou mumere ntregi folosind

    algoritmul lui Euclid.

    Analiza problemei.

    Vom nota cu m i n numerele pentru care trebuie determinat cel mai mare divizor

    comun. Astfel, variabilele m i n reprezint variabile de intrare pentru problem. Algoritmul

    lui Euclid presupune efectuarea repetat a unor operaii de mprire cu rest, pn cnd se

    obine un rest zero. Fie de exemplu: m=8, n=12:

    8=0*12+8 (r1=8)

    12=1*8+4 (r2=4)

    8=2*4+0 (r3=0)

    Ultimul rest nenul (r2=4) va fi solutia problemei.

  • Vom utiliza urmtoarele variabile: m pentru desemnarea dempritului, n pentru desemnarea

    mpritorului i r pentru desemnarea restului (ctul nu intervine n algoritm). Se observ

    faptul c la fiecare pas (n afar de primul), valorile lui m si n se determin din valorile

    pasului precedent: noua valoare a lui m este vechea valoare a lui n i noua valoare a lui n este

    vechea valoare a lui r. Astfel, ultimul rest nenul va fi memorat n variabila n, care devine si o

    variabil de ieire.

    Descrierea algoritmului:

    1. Se citesc de la intrare valori pentru m i n. 2. Se mparte m la n i se obine un rest r. 3. Dac r=0, atunci scrie la ieire n i algoritmul se termin.

    4. Dac r0, atunci se atribuie: m=n, n=r i se face salt la pasul 2.

    Se observ c algoritmul din exemplul precedent se termin la pasul 3. O prim ntrebare se

    refe la faptul dac dup un numr finit de pai, restul devine zero pentru ca algoritmul s se

    termine. O argumentare la aceast ntrebare este urmtoarea afirmaie: irul de resturi: r1, r2,

    r3, ..., este un ir descresctor de numere ntregi pozitive i care ajunge n zero.

    Pe baza examinrii algoritmului precedent, se pot descrie principalele caracteristici ale unui

    algoritm:

    1. Generalitatea unui algoritm, se refer la faptul c n mod uzual algoritmii descriu rezolvarea unor categorii de probleme, nu a unor probleme singulare. n exemplul

    precedent, algoritmul descrie determinarea celui mai mare divizor comun a oricror

    numere ntregi, nu numai a numerelor 8 i 12.

    2. Intrarea n algoritm, este reprezentat de zero sau mai multe mrimi care trebuie specificate algoritmului, pantru ca el s poat fi executat. n mod uzual intrarea n

    algoritm se face prin intarmediul unor varabile de intrare, care la nceputul execuiei

    algoritmului vor fi iniializate cu valorile de intrare curente.

    3. Ieirea din algoritm, const n una sau mai multe mrimi care sunt determinate de ctre algoritm ce reprezint rezultatele problemei aferente algoritmului. Ieirea se

    realizeaz n mod uzual prin intermediul unor variabile de ieire. Dac este posibil

    algoritmii s nu aibe mrimi de intrare, ei trebuie obligatoriu s aibe mrimi de ieire,

    pentru c acestea reprezint soluiile problemelor aferente.

    4. Cracterul finit al algoritmului, reprezint cerina ca numrul de operaii efectuate pentru determinarea mrimilor de ieire s fie finit, altfel algoritmul nu poate s

    determine soluiile problemei aferente.

    5. Claritatea algoritmului, se refer la cerina ca operaiile din algoritm s fie clar i concis specificate, fiind astfel nlturate nedeterminismul i ambiguitile anumitor

    operaii.

    Cu excepia ultimei caracteristici, toate celelelte caracteristici sunt verificate de algoritmul

    din exemplul 1. Ambiguitile care pot apare se refer la semnificaia operaiilor efectuate n

    algoritm: nu se specific dac valorile variabilelor m i n sunt ntregi sau reale. n cazul n

    care valorile sunt reale, nu are sens efectuarea unor operaii cu rest.

    n general, limbajul natural nu permite eliminarea complet a ambiguitilor

    operaiilor. Din acest motiv, pentru specificarea algoritmilor se utilizeaz limbaje de

    descriere cu o semantic mai puternic.

  • 2.2 Limbajul algoritmic

    Limbajul algoritmic (sau limbajul pseudocod) reprezint o metod uzual de specificare a

    algoritmilor, mai formalizat dect limbajul natural. Avantajul const n faptul c descrierea

    operaiilor unui algoritm poate fi fcut mai clar i cu mai puine ambiguiti dect n cazul

    utilizrii limbajului natural.

    2.2.1 Elemente de gramatic

    Este necesar prezentarea unui set minim de reguli pentru a putea defini sintaxa acestui

    limbaj.

    Majoritatea propoziiilor din limbaj sunt propoziii imperative (instruciuni), fiecare

    avnd o semnificaie foarte clar i desemnnd operaii precise. Puinele propoziii

    declarative au doar rolul de a delimita din punct de vedere sintactic algoritmii, sau de a

    specifica n cazul funciilor i procedurilor modul n care se face transferul de informaie ntre

    funcia/procedura apelat i algoritmul apelant.

    n afara acestor propoziii, n cadrul algoritmilor pot apare propoziii dintr-o categorie

    aparte, numite comentarii. Comentariile nu sunt luate n considerare la execuia algoritmilor,

    ele avnd doar un rol de explicare a anumitor operaii din cadrul acestora. Un comentariu

    ncepe cu irul de caractere // i se termin la sfritul liniei curente.

    Desemnarea aciunilor din cadrul instruciunilor se face prin intermediul unuia sau a

    mai multor cuvinte cheie. Acestea sunt cuvinte rezervate i nu pot fi utilizate de ctre

    programator n alte scopuri. A doua categorie important de cuvinte sunt cuvintele utilizator,

    numite i identificatori, care sunt nume date de programatori anumitor obiecte din algoritm.

    Pentru a deosebi cuvintele din cele dou categorii, cuvintele cheie sunt subliniate.

    Identificatorii sunt iruri de caractere alfabetice, care ncep ntotdeauna cu o liter.

    n mod uzual, identificatorii desemneaz nume de variabile. ntruct o mare parte a

    problemelor a cror rezolvare poate fi descris algoritmic sunt de natur tiinific, o parte a

    noiunilor i conceptelor din matematic au fost preluate n limbajul algoritmic. Astfel,

    noiunea de variabil reprezint o entitate cu dou atribute: numele variabilei (care este un

    identificator) i valoarea sa curent sau instantanee. n timpul execuiei unui algoritm,

    valoarea curent a unei variabil se poate modifica. Aciunea prin care unei variabile i se

    asociaz o valoare curent se numete asignarea variabilei respective.

    O alt noiune utilizat este cea de expresie. O expresie este format din operanzi,

    operatori i perechi de paranteze rotunde. Operanzii pot fi constante, variabile i apeluri de

    funcii. Operatorii reprezint operaiile elementare ce se pot efectua asupra operanzilor.

    Evaluarea unei expresii presupune aplicarea operatorilor asupra operanzilor ntr-o anumit

    ordine, pentru obinerea rezultatului final. Schimbarea ordinii de evaluare se realizeaz prin

    utilizarea parantezelor rotunde.

    Pentru a nu formaliza excesiv acest limbaj, anumite noiuni din limbajele de

    programare de nivel nalt nu sunt luate n considerare. De exemplu, noiunea de tip de date

    este utilizat n mod implicit. Tipul de date al unei variabile reprezint mulimea valorilor pe

    care variabila le poate lua n timpul execuiei unui algoritm. Se subnelege faptul c o

    variabil nu poate lua valori diferite n timpul execuiei unui algoritm (valori ntregi i valori

    logice de exemplu).

  • 2.2.2 Instruciunile limbajului

    Descrierea unui algoritm se face ntre dou propoziii declarative, formate fiecare dintr-un

    singur cuvnt cheie:

    start sfarsit

    ntre cele dou cuvinte se specific secvena de instruciuni ce formeaz descrierea rezolvrii

    problemei asociate. O secven de instruciuni reprezint un ir de instruciuni, scrise n mod

    uzual unele sub altele, care se execut secvenial (una dup alta).

    Cele mai utilizate instruciuni sunt cele de citire i scriere a datelor, de atribuire, de

    selecie i instruciunile repetitive.

    Corespunztor intrrii i ieirii unui algoritm, limbajul algoritmic posed dou

    instruciuni, numite instruciunea de citire, respectiv instruciunea de scriere. Prima este

    folosit pentru citirea din afara algoritmului a datelor de intrare n algoritm, iar a doua pentru

    scrierea n afara algoritmului a datelor de ieire (a rezultatelor).

    Instruciunea de citire are urmtoarea form sintactic:

    citeste lista variabile

    unde lista variabile reprezint o list de una sau mai multe variabile de intrare ale

    algoritmului, separate prin virgul dac sunt mai multe.

    Observaie. Cracterele i nu fac parte din sintaxa limbajului algoritmic, ci din cea a

    limbajului de descriere. ntre cele dou caractere se specific o categorie sintactic, adic o

    mulime de construcii sintactice grupate mpreun.

    Exemple de instruciuni de citire: citeste x citeste a, b, c

    Execuia unei astfel de instruciuni realizeaz urmtoarele aciuni:

    - se introduc din afara algoritmului a unui numr de constante egal cu numrul de variabile din instruciune;

    - se asigneaz pe rnd variabilele din instruciune cu constantele corespunztoare.

    Observaie. Instruciunea de citire este o modalitate prin care se pot asigna valori

    variabilelor. Dup ce o constant se asigneaz la o variabil n acest fel, variabila i va pstra

    valoarea curent pn la prima instruciune care o va modifica.

    Instruciunea de scriere are urmtoarea form sintactic:

    scrie lista parametri

    unde lista parametri reprezint o list de unul sau mai muli parametri separai prin

    virgul.

    Exist dou categorii de parametri: de tip mesaj i de tip expresie. Parametrii de tip

    mesaj sunt iruri de caractere cuprinse ntre dou apostrofuri i sunt utilizai pentru

  • tranmiterea unor mesaje n exteriorul algoritmilor. Valoarea unui astfel de parametru este

    chiar irul de caractere. Prametrii de tip expreise sunt expresii care se pot evalua. Valoarea

    unui astfel de parametru este cea rezultat n urma evalurii.

    Exemple de instruciuni de scriere: scrie x

    scrie Acesta este un mesaj

    scrie x=, x

    Execuia unei asemenea instruciuni decurge astfel:

    - se evalueaz parametrii care apar n instruciune; - se afieaz n afara algoritmului secvenia valorile rezultate.

    Presupunnd c variabila x are asignat valoarea 7 n momentul execuiei secvenei

    anterioare, n afara algoritmului se va afia: 7

    Acesta este un mesaj

    x=7

    Exemplul 2.2. S se scrie un algoritm care determin suma i produsul a dou numere date.

    Descrierea algoritmului

    Notnd cu x i y variabilele de intrare corespunztoare valorilor de intrare, algoritmul

    se poate descrie astfe:

    start citeste x, y

    scrie suma=, x+y, produsul=, x*y

    sfarsit

    Una dintre cele mai utilizate instruciuni, att n limbajul algoritmic, ct i n limbajele de

    programare, este instruciunea de atribuire. Aceasta reprezint cel de-al doilea mod prin care

    se pot asigna valori variabilelor. Definiia sintactic a instruciunii este:

    atribuie variabila expresie

    unde variabila este numele unei variabile a algoritmului, iar expresie este o

    expresie compatibil cu variabila. Cracterul reprezint operatorul de atribuire i are

    rolul de a indica sensul de transfer al informaiei. ntruct operatorul de atribuire identific

    exact instruciunea de atribuire, cuvntul cheie atribuie se poate omite, rezultnd o form

    simplificat de scriere:

    variabila expresie

    Exemple de instruciuni de atribuire:

    x 5

    y (sin(a)+b)/(sin(b)+a)

    n n+1

    n mod uzual, operatorii care apar n cadrul expresiilor sunt preluai din matematic,

    reprezentnd principalele operaii, dar mulimea acestora poate fi extins pentru a cuprinde

    operaii din diferite domenii. Dei nu se specific n mod formal, urmtoarele categorii de

    operatori sunt mai des utilizai:

    - operatori aritmetici: - +, -, *, /: reprezint operaiile algebrice elementare;

  • - div, mod: reprezint operaiile de determinare a ctului i restului mpririi a

    doua numere ntregi;

    - operatori de comparare (de relaie): , , =, ;

    - operatori logici: (i logic), (sau logic), (negaia logic).

    Execuia instruciunii de atribuire se realizeaz n dou etape distincte:

    - evaluarea expresiei din stnga operatorului de atribuire, n urma creia rezult o valoare;

    - atribuirea valorii rezultate variabilei din stnga.

    n acest fel, numele unei variabile poate apare att n stnga, ct i n dreapta operatorului de

    atribuire. Cele dou valori ale variabilei se numesc: valoare veche (cea din stnga) i valoare

    nou (cea din dreapta).

    Instruciunea de selecie cea mai utilizat este instruciunea de decizie. Ea este o

    instruciune compus, a crei execuie presupune execuia unei secvene de instruciuni din

    maxim dou posibile, n funcie de o anumit condiie. Definiia sintactic a instruciunii este

    urmtoarea:

    daca expresie atunci

    secventa 1

    altfel

    secventa 2

    unde expresie reprezint o expresie logic, iar secventa 1 i secventa 2

    reprezint dou secvene de instruciuni.

    Pentru execuia instruciunii se execut urmtoarele aciuni:

    - se evalueaz expresia logic; - dac aceasta este adevrat, se execut secvena 1 de instruciuni; - dac expresia este fals, se execut secvena 2 de instruciuni.

    Obesrvaie. Caracterul grafic are rolul de a delimita ultima secven intern de

    instruciuni de instruciunea imediat urmtoare celei de decizie.

    Principalii operatori care apar n cadrul expresiilor logice sunt operatorii logici i

    operatorii de comparare (de relaie). Operatorii logici corespund principalelor operaii

    logice: sau logic (), i logic () i negaia logic (). Operatorii de relaie (, , =,

    ) compar valoarea a doi operanzi, genernd tot un rezultat logic.

    Sunt cazuri n care este util selecia unei secvene de instruciuni din mai multe

    alternative posibile. n aceste cazuri se poate utiliza o form extins a instruciunii de decizie,

    care devine o instruciune de selecie. Forma sintactic a acesteia este urmtoarea:

    daca expresie 1 atunci

    secventa 1

    altfel daca expresie 2 atunci

    secventa 2

    ...

  • altfel daca expresie n atunci

    secventa n

    altfel

    secventa n+1

    Exemplul 2.3. S se determine valoarea funciei:

    -2*x2-x+2, dac x(-, -2)

    f(x)= x-2, dac x[-2, -1)

    (2-x)/(x+2) , dac x(-1, 1)

    (2*x2+x-2)/(2*x+1), dac x[1, )

    ntr-un punct x dat.

    Descrierea algoritmului.

    Pentru c instruciunea de decizie selecteaz pentru execuie o secven din maxim

    dou posibile, n cadrul algoritmului se vor folosi o instructiune de decizie extins, cte o

    alternativ pentru fiecare ramur a funciei; prima decizie determin complet doar intervalul

    (-, -2), urmnd ca n cazul intervalului [-2, ) s se considere urmtorul punct de decizie, -

    1, .a.m.d.

    start citeste x

    daca x

  • Exemplul 2.4. S relum exemplul precedent, dar folosind doar instruciuni de decizie cu

    form scurt: pentru fiecare ramur a funciei se va considera o singur instruciune de

    decizie.

    start citeste x

    daca x

  • De exemplu, s considerm urmtoarea secven de instruciuni:

    x 5 cat timp x

  • O alt deosebire fa de instruciunea precedent const n faptul c n cazul instruciunii

    repretitive cu test final, secvena intern de instruciuni se execut cel puin o dat, indiferent

    de valoarea iniial a expresiei logice.

    Exemplul 2.6. Se consider un ir de numere terminat cu numrul zero. S se determine cte

    numere pozitive sunt n ir.

    Analiza problemei.

    Se va utiliza o variabil de intrare, notat cu x, prin intermediul creia se vor citi

    valorile din ir. Variabila de ieire, notat cu np, va memora numrul de numere pozitive din

    ir. Iniial np va fi iniializat la zero; de fiecare dat cnd se citete un numr, se compar

    acesta cu zero: dac numrul curent este pozitiv, variabila np va fi incrementat cu 1.

    Iteraiile se termin cnd se citete o valoare zero.

    Descrierea algoritmului.

    start

    np 0 repeta

    citeste x

    daca x>0 atunci

    np np+1

    cat timp x0 scrie np

    sfarsit

    n cazul precedentelor dou instruciuni repetitive, numrul de iteraii este greu de estimat n

    faza de proiectare a algoritmului. Sunt ns situaii n care acesta poate fi estimat relativ uor.

    n aceste cazuri este probabil preferabil utilizarea instruciunii repetitive cu numr

    cunoscut de iteraii.

    De data aceasta gestionarea numrului de iteraii se realizeaz cu ajutorul unei

    variabile numite variabila de control a instruciunii. Aceasta va primi n timpul execuiei

    instruciunii repetitive valori succesive dintr-un ir de valori monoton, mrginit de dou

    valori distincte numite valoare iniial, respectiv valoare final. Valoarea iniial este chiar

    prima valoare din sir, pe cnd valoarea final este doar o margine a irului de valori (margine

    superioar n cazul unui ir cresctor, sau margine inferioar n cazul unui ir descresctor).

    irul valorilor variabilei de control are proprietatea c diferena ntre oricare dou

    valori consecutive este constant. Aceast constant se numete pas de incrementare. Astfel,

    irul valorilor unei variabile de control se poate determina dac se cunosc valoarea iniial,

    limita final i pasul de incrementare.

    Notnd cu vi, vf i p valoarea iniial, limita final, respectiv pasul de incrementare, iat

    cteva exemple de iruri de valori pentru variabila v:

    a) vi=2, vf=9, p=2 v{2, 4, 6, 8}

    b) vi=9, vf=2, p=-2 v{9, 7, 5, 3}

    c) vi=2, vf=2, p=3 v{2}

    d) vi=2, vf=9, p=0 v{2, 2, 2, ...} Se observ faptul c ntre valoarea iniial vi, limita final vf i pasul de incrementare p

    trebuie s existe anumite relaii:

  • - dac vi0; - dac vi>vf, atunci trebuie ca p0,

  • S0=0.

    Se observ astfel c Sn=S, suma ce trebuie determinat.

    Se va utiliza proprietatea instruciunii de atribuire, n care o variabil poate apare n ambele

    pri ale operatorului de atribuire, astfel nct instruciunea:

    S S + i3,

    reprezint chiar relaia (1) la iteraia I.

    Folosind aceast observaie, se va utiliza variabila S pentru stocarea valorilor Si la diferitele

    iteraii (adic va memora pe rnd valorile S0, S1, ..., Sn). Variabila va fi iniializat cu

    valoarea 0, iar dup ultima iteraie va memora chiar valoarea dorit.

    Descrierea algoritmului.

    start citeste n

    s 0

    pentru k1 la n executa

    s s+k3

    scrie s

    sfarsit

    2.3 Metoda rafinrilor succesive

    n cazul problememor complexe este dificil descrierea rezolvrilor acestora direct, folosind

    doar instruciuni executabile ale limbajului algoritmic. n mod uzual, problema iniial va

    trebui descompus ntr-un amumit numr de subprobleme, a cror rezolvare trebuie descris

    separat.

    O metod des utilizat n acest caz este metoda rafinrilor succesive. n cadrul

    acesteia se face distincie ntre enunarea unei subprobleme i descrierea rezolvrii ei. Pentru

    a specifica o anumit subproblem n cadrul unui algoritm, limbajul algoritmic trebuie extins

    cu o nou clas de propoziii, numite propoziii nestandard. Acestea sunt specificate n

    limbajul natural i ncadrate ntre dou caractere *. Descrierea rezolvrii unei subprobleme

    asociate unei propoziii nestandard se numete rafinarea propoziiei; rafinarea propoziiilor

    nestandard se va face dup descrierea algoritmului principal al problemei iniiale.

    Exemplul 2.8. S se calculeze madia aritmetic a unui sir de numere.

    Analiza problemei.

    n cadrul acestei probleme (simple i a crei rezolvare nu necesit descompunerea n

    subprobleme) se pot pune n eviden dou subprobleme: citirea irului de numere i

    determinarea mediei aritmetice. Principalele variabile folosite n algoritm sunt:

    - n, care specific numrul de elemente din ir,

    - x, care reprezint un vector de numere cu componentele: x1, x2, ..., xn,

    - medie, care reprezint madia aritmetic a sirului de numere.

    Descrierea algoritmului.

    Algoritmul principal se poate descrie astfel:

    start

  • citeste n

    * citirea sirului de numere x1, x2, ..., xn *

    * calculul mediei aritmetice:medie=(x1+ x2+ ...+ xn)/n *

    scrie med

    sfarsit

    Urmeaz rafinrile celor dou propoziii nestandard:

    * citirea sirului de numere x1, x2, ..., xn *

    pentru i 1 la n executa

    citeste xi

    Sfarsit

    * calculul mediei aritmetice:medie=(x1+ x2+ ...+ xn)/n *

    s 0

    pentru i 1 la n executa

    s s+xi

    medie s/n sfarsit

    Se observ faptul c rafinarea unei propoziii nestandard conine trei elemente: enunul

    propoziiei, secvena de instruciuni ce formeaz descrierea rezolvrii problemei aferente si

    cuvntul cheie sfarsit, care are rolul de a delimita rafinarea propoziiei curente.

    n cazul n care anumite subprobleme sunt de asemenea complexe, procesul de

    mprire n subprobleme poate continua. Rezult astfel o descriere a algoritmului pe nivele:

    - pe nivelul 0 se afl algoritmul principal al problemei; - pe nivelul 1 se afl refinrile propoziiilor nestandard de pe nivelul 0; - n general, pe nivelul k se afl refinrile propoziiilor nestandard de pe nivelul k-1.

    Operaia de rafinare succesiv continu pn la un nivel n care rafinrile tuturor propoziiilor

    conin doar instruciuni standard ale limbajului algoritmic.

    Exemplul 2.9. Dndu-se un numr natural k i o matrice ptrat A de dimensiune nn, s se

    determine matricea B=Ak.

    Analiza problemei.

    Conform definiiei puterii unei matrici:

    A0=I, A

    k=A

    k-1*A, pentru k>0,

    se poate descrie algoritmul de rezolvare dup ablonul problemei redus la numere reale:

    Dndu-se un numr natural k i un numr real a, s se determine numrul b=ak.

    Un algoritm pentru acesta este:

    start citeste k

    citeste a

    b 1

    pentru p 1 la k executa

    c b*a

    b c

  • scrie b

    sfarsit

    Descrierea algoritmului.

    Subproblemele puse n eviden corespund celor citirii matricii A i scrierii matricii B,

    instruciunii de atribuire, precum i intruciunii repetitive. Nivelul 0 este:

    start citeste k

    * citeste matricea A *

    * atribuie mtricial B I * * determina matricea: B=A

    k *

    * scrie matricea B *

    sfarsit

    Nivelul 1 conine rafinrile propoziiilor de pe nivelul 0:

    * citeste matricea A *

    pentru i 1 la n executa

    pentru j 1 la n executa

    citeste aij

    sfarsit

    * atribuie mtricial B I *

    pentru i 1 la n executa

    pentru j 1 la n executa

    daca i=j atunci

    bij 1

    altfel

    bij 0

    sfarsit

    * determina matricea: B=Ak *

    pentru p 1 la k executa

    * determina matricea: C = B*A *

    * atribuie matricial: B C *

    sfarsit

    * scrie matricea B *

    pentru i 1 la n executa

    pentru j 1 la n executa

    scrie bij

    sfarsit

  • ntruct pe nivelul 1 exist n continuare doua propoziii nestandard, algoritmul va conine i

    nivelul 2:

    * determina matricea C=B*A *

    pentru i 1 la n executa

    pentru j 1 la n executa

    cij 0

    pentru s 1 la n executa

    cij cij+aik*bkj

    sfarsit

    * atribuie matricial: B C *

    pentru i 1 la n executa

    pentru j 1 la n executa

    scrie bij cij

    sfarsit

    Execuia algoritmilor descrii prin metoda rafinarilor succesive nu este direct. nainte de

    execuia propriu-zis, va trebui ca un asemenea algoritm s fie transformat ntr-un algoritm

    echivalent din punct de vedere paragmatic, dar care nu contine dect instruciuni standard ale

    limbajului. Notnd cu n numrul nivelulu maxim, operaia de transformare a algoritmului se

    poate descrie astfel:

    pentru k n-1 la 0 pas -1 executa

    pentru *fiecare rafinare r de pe nivelul k* executa

    pentru *fiecare propozitie nestandard p din rafinarea r* executa

    *inlocuieste propozitia p cu rafinarea sa de pe nivelul k+1*

    Cu alte cuvinte, ncepnd de la penultimul nivel, se vor substitui toate propoziiile nestandard

    cu rafinrile lor aflate pe nivelul imediat urmtor. Se asigur n acest mod apariia doar a

    instruciunilor standard ale limbajului.

    n exemplul anterior, se vor substitui nti propoziiile nestandard: *determina

    matricea:C=B*A* i *atribuie matricial:BC* n propoziia *determina matricea:B=Ak *. La pasul urmtor se vor substitui cele patru propoziii nestandard din algoritmul principal cu

    rafinrile lor, rezultnd un algoritm direct executabil:

    start citeste k

    pentru i 1 la n executa

    pentru j 1 la n executa

    citeste aij

  • pentru i 1 la n executa

    pentru j 1 la n executa

    daca i=j atunci

    bij 1

    altfel

    bij 0

    pentru p 1 la k executa

    pentru i 1 la n executa

    pentru j 1 la n executa

    cij 0

    pentru s 1 la n executa

    cij cij+aik*bkj

    pentru i 1 la n executa

    pentru j 1 la n executa

    cij bij

    pentru i 1 la n executa

    pentru j 1 la n executa

    scrie bij

    sfarsit

    Metoda rafinrilor succesive se mai numete metoda top-down de proiectare a algoritmilor

    (de sus n jos).

    2. 4 Funcii i proceduri n limbajul algoritmic

    Prncipalul dezavantaj al metodei rafinrilor succesive se refer la execuia algoritmilor. Dei

    exist o mare flexibilitate n ceea ce privete descrierea algoritmilor compleci, execuia unui

    algoritm descris prin metoda rafinrilor succesive presupune operaii repetate de modificare a

    algoritmului iniial prin substituirea propoziiilor nestandard cu rafinrile lor, pn cnd

    acesta ajunge s conin doar instruciuni care pot fi executate direct.

    O variant des utilizat, att n cazul folosirii limbajului algoritmic, ct mai ales n

    cazul codificrii algoritmilor n limbaje de programare, o constituie utilizarea funciilor i

    procedurilor. Procedurile i funciile permit descrierea unor clase de subprobleme, avnd

    ns un caracter mai mare de generalitate dect propoziiile nestandard. Spre deosebire de

    propoziile nestandard, care sunt legate strict de descrierea unui anumit algoritm, funciile si

    procedurile pot fi independente de algoritmii n care se folosesc, comunicarea cu algoritmii

    fcndu-se prin intermediul unor parametri formali.

  • Exemplul 2.10. Pentru exemplificare, se va relua problema determinrii mediei aritmetice a

    unui ir de numere reale. Subproblemele puse n eviden constau n citirea elementelor

    irului i determinarea mediei aritmetice. Pentru prima subproblem se va folosi o procedur,

    numit CitireElementeSir, , iar pentru a doua se va folosi o funcie numit

    CalculMedieAritmetica, care va determina o valoare reprezentnd media aritmetic a

    valorilor elementelor irului.

    start citeste n

    CitireElementeSir(n,x)

    medie CalculMedieAritmetica(n,x) scrie medie

    sfarsit

    Definirea procedurii CitireElementeSir presupune specificarea operaiilor de citire a tuturor

    celor n valori ale elementelor irului:

    procedura CitireElementeSir(intrare nr, iesire v)

    pentru i 1 la nr executa

    citeste vi

    sfarsit

    Funcia CalculMedieAritmetica determin nti suma valorilor elementelor irului i o

    mparte la numrul elementelor:

    functia CalculMedieAritmetica(intrare nr, v)

    s 0

    pentru i 1 la nr executa

    s s+vi

    returneaza s/nr

    sfarsit

    Descrierea algortimului n forma prezentat mai sus are avantajul execuiei directe a acestuia

    prin apelul procedurii CitireElementeSir i a funciei CalculMedieAritmetica.

    Deosebirea ntre funcii i proceduri se refer la rezultatul determinat de acestea.

    Funciile sunt folosite n cazul n care subprobleme aferente au drept scop principal

    determinarea unei valori simple, pe cnd procedurile au drept scop principal efectuarea

    anumitor operaii. Distincia ntre acestea nu este ns foarte clar, pentru c i funciile pot

    avea mai multe mrimi de ieire transmise prin parametri.

    Se observ dublul avantaj al folosirii funciilor i procedurilor:

    a) descrierea subproblememelor folosind un nalt grad de generalitate; b) modul simplu de execuie al algoritmilor, ntruct funciile i procedurile reprezint

    elemente executabile i care pot fi apelate.

    Din acest motiv, se va analiza distinct att operaia de definire a funciilor i procedurilor,

    precum i operaia de apel a acestora.

  • 2.4.1 Definirea funciilor i procedurilor

    Se observ din exemplul anterior c definirea unei funcii sau a unei proceduri presupune

    specificarea a dou elemente distincte: antetul i corpul funciei sau procedurii. Antetul

    definete elementele de interaciune ale funciei/procedurii cu exteriorul, pe cnd corpul

    specific aciunile care trebuie ndeplinite pentru rezolvarea subproblemei asociate.

    Specificarea terminrii descrierii funciei/procedurii se face prin intermediul cuvntului cheie

    sfrit.

    Sintaxa de definire a unei funcii i a unei proceduri este:

    functia identificator ( [parametri formali] )

    secventa instructiuni sfarsit

    procedura identificator ( [parametri formali] )

    secventa instructiuni sfarsit

    Observaie. Caracterele [ i ] nu fac parte din sintaxa limbajului algoritmic, ci din cea a

    limbajului de descriere. ntre dou paranteze drepte se specific n mod uzual o categorie

    sintactic opional (care poate sau nu s apar mtr-un algoritm).

    Antetul unei funcii sau proceduri conine un cuvnt cheie specificnd tipul acesteia (funcie

    sau procedur), un identificator reprezentnd numele asociat ei, precum i parametrii formali

    ai acesteia.

    Parametri formali ai unei funcii sau proceduri sunt opionali i reprezint modul prin

    care funcia/procedura interacioneaz cu exteriorul, specificnd mrimile de intrare i de

    ieire. O funcie sau o procedur fiind de fapt un algoritm ce descrie modul de rezolvare al

    unei subprobleme, ea poate primi la intrare valorile care sunt necesare pentru execuia

    algoritmului (care sunt parametri formali de intrare ai funciei/procedurii respective) i

    trebuie s determine mrimile de ieire ale acesteia (care sunt parametri formali de ieire).

    Aceti parametri pot fi considerai drept variabile locale funciei/procedurii, care nu au

    semnificaie n afara corpului acesteia.

    Specificarea parametrilor de intrare se face cu ajutorul cuvntului cheie intrare,

    iar a celor de ieire cu ajutorul cuvntului cheie ieire. n exemplul anterior parametrul nr

    (specificnd numrul de elemente al irului) reprezint un parametru de intrare att n cazul

    funciei ct i al procedurii, iar v (specificnd vectorul ce conine elementele irului) este un

    parametru de ieire n cazul procedurii i unul de intrare n cazul funciei.

    Observaie. Nu exist o distincie formal ntre subproblemele a cror rezolvare se descrie cu

    ajutorul funciilor i cele care se descriu cu ajutorul procedurilor, acest lucru rmnnd la

    latitudinea programatorului. O regul care se poate folosi sugereaz c funciile se pot folosi

    pentru acele subprobleme a cror scop este determinarea unor mrimi simple scalare.

    Corpul funciilor i procedurilor conine o secven de instruciuni care descriu rezolvarea

    subproblemei aferente. Exist o instruciune care se poate utiliza n carpul corpurilor

    funciilor/procedurilor, dar nu se poate utiliza ntr-un algoritm principal, numit instruciune

    de ntoarcere, a crei sintax este:

  • returneaza [expresie]

    unde returneaz este un cuvnt cheie, specificnd locul unde execuia procedurii sau a

    funciei se ncheie, revenindu-se n algoritmul care a apelat-o. Categoria sintactic

    expresie reprezint o expresie opional, folosit doar n cadrul funciilor. n acest caz,

    valoarea expresisei reprezint chiar valoarea pe care funcia respectiv trebuie s o determine

    i care trebuie returnat algoritmului apelant. n cazul n care expresia lipsete, instruciunea

    se utilizeaz n corpul procedurilor, n caz contrar ea utilizndu-se n corpul funciilor. n

    exemplul anterior, instruciunea de ntoarcere este folosit doar n cadrul funciei

    CalculMedieAritmetica, expresia s/nr reprezentnd media aritmetic pe care funcia trebuie

    s o calculeze.

    Observaie. n corpul unei proceduri instruciunea de ntoarcere este opional; n cazul n

    care instruciunea de ntoarcere lipsete, execuie procedurii se termin dup execuia ultimei

    instruciuni din corpul ei. n corpul unei funcii trebuie s existe cel puin o instruciune de

    ntoarcere, pentru c o funcie ntotdeauna returneaz o valoare.

    Operaia de definire a funciilor i procedurilor reprezint componenta declarativ a

    subproblemelor descrise, pe cnd execuia lor reprezint o component pragmatic,

    specificnd momentul i modul de execuia a acestora.

    2.4.2 Apelul i execuia funciilor i procedurilor

    n cazul n care se folosesc funcii sau proceduri pentru descrierea unui algoritm, trebuie

    realizate dou operaii distincte: definirea funciilor i/sau procedurilor folosite, precum i

    apelul acestora n cadrul algoritmului. Din punct de vedere sintactic, apelul indic numele

    funciei/procedurii apelate, precum i parametrii de apel, specificai ntre paranteze rotunde:

    identificator ([lista parametri de apel])

    n exemplul precedent, parametrii de apel n ambele cazuri au fost variabilele n i x.

    Observaie. Exist o deosebire important ntre apelul unei funcii i apelul unei proceduri:

    apelul unei funcii se poate face doar n cadrul unor expresii, n acele locuri din algoritm unde

    este permis utilizarea unor expresii (de exemplu, n cadrul instruciunilor de atribuire), pe

    cnd apelul unei proceduri este de sine stttor, fiind considerat ca o instruciune distinct,

    numit instruciunea de apel de procedur.

    Parametri de apel se mai numesc parametri actuali, iar mpreun cu parametrii formali ai

    funciei/procedurii apelate formeaz suportul pentru mecanismul de transfer a informaiei

    ntre procedura/funcia apelat i algoritmul apelant. ntre parametri formali i parametri

    actuali trebuie s existe anumite concordane:

    a) numrul parametrilor acuali i al parametrilor formali trebuie s fie acelai; b) tipul de date al fiecrui parametru actual trebuie s corespund tipului de date al

    parametrului formal de pe aceiai poziie (n exempul precedent, parametrul actual n

    este un ntreg i corespunde parametrului formal nr, iar parametrul actual x este un

    vector de numere reale care corespunde parametrului formal v).

  • Apelul unei funcii sau proceduri presupune efectuarea mai multor etape:

    1) suspendarea execuiei elgoritmului apelant n locul apelului respectiv; 2) transferul informaiei dinspre algoritmul apelant spre procedura/funcia apelat; 3) execuia funciei/prodedurii apenate; 4) transferul informaiei dinspre funcia/procedura apelat spre algoritmul apelant; 5) reluarea execuiei algoritmului apelant din locul imediat urmtor apelului.

    Execuia funciei/procedurii apelate se realizeaz secvenial ncepnd cu prima instruciune

    din corpul acesteia. Execuia se termin fie la ntlnirea primei instruciuni de ntoarcere, iar

    dac aceasta nu exist (n cazul procedurilor), dup ultima instruciune.

    Exemplul 2.11 Considerndu-se un ir de numere reale, s se determine poziia primului

    element negativ din ir. Se va folosi o funcie care primete ca parametri de intrare numrul

    de elemente precun i vectorul elementelor. Funcia va returna poziia primului elment

    negativ din ir, iar n cazul n care irul nu conine elemente negative, se va returna numrul

    0.

    start citeste n

    CitireElementeSir(n,x)

    k DeterminaPozitia(n,x) daca k > 0 atunci

    scrie k altfel

    scrie Nu sunt elemete negative

    sfarsit

    functia DeterminaPozitia(intrare dim, v)

    pentru i 1 la dim executa

    daca vi < 0 atunci

    returneaza i

    returneaza 0

    sfarsit

    Funcia CitireElementeSir a fost definit anterior, n exemplul 2.10. Execuia funciei

    DeterminaPozitia se ncheie cnd se ntlnete primul element negativ din ir, intruciunea

    repretitiv cu numr cunoscut de iteraii ncheindu-se forat n acest caz (aceasta este ieirea

    normal din funcie). Dac dup parcurgerea tuturor elementelor irului nu s-a determinat

    nici unul cu valoare negativ, execuia funciei ajunge la intruciunea: returneaza 0, care

    reprezint a doua variant de terminare a funciei.

    Transferul informaiei ntre algoritmul apelant i funcia sau procedura apelat se

    realizeaz ptin intermediul parametrilor actuali i a celor formali. Parametri formali de

    intrare se comport asemenea unor variabile locale, care la nceputul execuiei

    funciei/procedurii sunt iniializate cu mrimile de intrare ale acesteia. Din acest motiv,

    parametri actuali corespunztori parametrilor formali de intrare trebuie s fie expresii care se

    pot evalua, valorile rezultate dup evaluare reprezentnd mrimile de intrare ale

    funciei/procedurii apelate.

  • Etapa a doua din cadrul unui apel realizeaz urmtoarele operaii:

    a) evaluarea expresiilor (n cadrul algoritmului apelant) reprezentnd parametri actuali ai funciei/procedurii apelate;

    b) iniializarea parametrilor formali din cadrul funciei/procedurii apelate cu valorile rezulate la pasul a).

    La nceputul execuiei funciei DeterminaPozitia din exemplul 2, parametrul formal dim se

    iniializeaz la valoarea variabilei n din algoritmul principal.

    Dup execuia funciei/procedurii apelate, trebuie realizat trensferul invers al

    informaiei, dinspre funcie/procedur spre algoritmul apelant: valorile parametrilor formali

    de ieire se vor transmite spre parametri actuali corespunztori din algoritmul apelant. Pentru

    aceasta, parametrii actuali corespunztori parametrilor formali de ieire trebuie s fie

    variabile: n acest mod, variabilele ce reprezint parametri actuali pot fi asignate cu valorile

    de ieire corespunztoare ale funciei/procedurii apelate.

    Acesat etap din cadrul unui apel realizeaz urmtoarele operaii:

    a) determinarea valorilor parametrilor formali din cadrul funciei/procedurii apelate; b) asignarea variabilelor reprezentnd parametrii actuali corespunztori parametrilor

    formali de ieire cu valorile rezulate anterior.

    n cadrul procedurii de citire a elementelor unui ir de numere din exemplul 1, dup execuia

    procedurii, valoarea parametrului de ieire v (reprezentnd un vector de numere) este

    transmis variabilei x din algoritmului principal.

    n cazul apelului unei funcii exist o etap suplimentar la execuia acesteia. n acest

    caz, numele unei funcii reprezint el nsui un parametru de ieire, iar dup execuia funciei

    aceast valoare trebuie transmis spre exterior. Modalitatea de transfer este asemntoare

    evalurii expresiilor algebrice: dup transferul parametrilor de ieire spre algoritmul apelant,

    apelul funciei din cadrul expresiei apelante se nlocuiete cu valoarea returnat de aceasta.

    De exemplu, n cadrul instruciunii de atribuire din algoritmul din exemplul 2.11:

    k DeterminaPozitia(n,x)

    expresia din partea dreapt a operatorului de atribuire conine doar un apel de funcie, iar

    evaluarea expresiei se reduce la nlocuirea apelului: DeterminaPozitia(n,x) cu

    valoarea returnat de execuia funciei respective.

    Exist cazuri n care pentru o anumit funcie sau procedur, anumii pararmetri pot fi att de

    intrare ct i de ieire, n sensul c la nceputul execuiei funciei/procedurii intr cu anumite

    valori, iar la sfritul execuiei se ntorc n algoritmul apelant cu valorile modificate. Acetia

    formeaz o categorie aparte: parametri de intrare i ieire, specificai de cuvntul cheie

    intrare-iesire. Ei se comport la fel cu parametrii de intrare la etapa a doua a apelului

    i la fel cu parametrii de ieire la etapa a patra a apelului. Exemplul urmtor utilizeaz

    parametri de intrare-ieire.

    Exemplul 2.12 S se determine derivata de ordinul k a unui polinom.

    Analiza problemei.

    Fie polinomul:

    P = a0 + a1X + ... + anXn,

    care va fi specificat prin gradul su i vectorul coeficienilor.

  • Pentru a determina polinomul de ieire:

    Q = b0 + b1X + ... + bmXm

    , unde m=n-k,

    se va repeta de k ori operaia de derivare a polinomului iniial, la fiecare derivare gradul

    polinomului scznd cu 1.

    S considerm prima derivat a polinomului P:

    D = d0 + d1X + ... + dn-1Xn-1

    , unde:

    d0=a1, d1=2*a2, ..., dn-1=n*an. Se observ faptul c n momentul calculului coeficientului dk,

    valorile coeficienilor a0, ..., ak nu mai sunt necesare. Aceast observaie permite o economie

    de variabie: utilizarea vectorului (a0, ..., an-1) n locul vectorului (d0, ..., dn-1). Cu alte cuvinte

    se vor determina valorile:

    a0=a1, a1=2*a2, ..., an-1=n*an.

    Descrierea algoritmului.

    Algoritmul urmtor apeleaz de k ori procedura DerivataPolinom; ambii parametri

    formali, dim i a sunt parametri de intrare-ieire.

    start citeste n, k

    CitesteCoeficienti(n,a)

    pentru i 1 la k executa

    DerivataPolinom(n,a)

    ScrieCoeficienti(n,a)

    sfarsit

    procedura CitesteCoeficienti(intrare dim, iesire a)

    pentru i 0 la dim executa

    citeste ai

    sfarsit

    procedura ScrieCoeficienti(intrare dim, a)

    pentru i 0 la dim executa

    scrie ai

    sfarsit

    procedura DerivataPolinom(intrare-iesire dim, a)

    pentru i 0 la dim-1 executa

    ai (i+1)*ai+1

    dim dim-1 sfarsit

    n cazul n care o funcie sau o procedur are mai multe tipuri de parametri formali, n mod

    uzual se declar nti parametrii de intrare, apoi parametrii de intrare-ieire i parametrii de

    ieire.

  • 2.5 Analiza algoritmilor

    Analiza algoritmilor este o operaie important n programarea calculatoarelor, deoarece

    pentru anumite aplicaii particulare exist mai muli algoritmi disponibili i trebuie

    determinai algoritmii care sunt mai performani.

    n mod uzual, performana algoritmilor este dat de complexitatea acestora. Din acest

    motiv, analiza complexittii unui algoritm are ca scop estimarea volumului de resurse de

    calcul necesare pentru execuia algoritmului. Prin resurse vom nelege:

    Volumul de memorie necesar pentru stocarea datelor pe care le prelucreaz algoritmul

    Timpul necesar pentru execuia tuturor prelucrrilor specificate n algoritm n mod uzual, un algoritm A este mai performat dect alt algoritm B, dac volumul de resurse

    necesar execuiei lui A este mai mic dect cel al execuiei lui B.

    n general, volumul resurselor necesare execuiei unui algoritm depinde de

    dimensiunea problemei de rezolvat. Aceasta este determinat, in general, de:

    Volumul datelor de intrare

    Modul de reprezentare al datelor Volumul datelor de intrare nu influeneaz n mod diferit, diferii algoritmi care rezolv

    aceeai problem. De exemplu: toi algoritmii care determin valoarea minim a unui ir de

    numere , vor avea acelai volum de date de intrare, dat de numrul elementelor irului.

    ns modul de reprezentare al datelor n cadrul algoritmilor poate diferenia

    algoritmii. De exemplu: reprezentarea intern a unei matrici rare poate fi fcut n cadrul

    unui algoritm:

    1. Alocnd spaiu de memorie pentru toate elementele matricii 2. Alocnd spaiu de memorie doar pentru elementele nenule

    n primul caz, algoritmul este mai ineficient dect n al doilea caz, deoarece memoreaz mai

    multe informaii (memoreaz n plus toate elementele nule ale matricii), pe cnd n cazul al

    doilea se vor memora doar elementele nenule (mpreun cu indicii corespunztori acestora).

    Dintre cele dou resurse de calcul (spaiu i timp), resursa critic pentru evaluarea

    complexitii unui algoritm este cea a timpului de execuie. n continuare vom disuta doar

    problema estimrii timpului de execuie al unui algoritm. Acesta depinde de mrimile de

    intrare. De exemplu:

    T(n) reprezint timpul de execuie al unui algoritm care are n ca mrime de intrare,

    T(n, m) reprezint timpul de execuie al unui algoritm care are n i m ca mrimi de intrare.

    Estimarea timpului de execuie al unui algoritm se face pe baza unor presupuneri, care

    definesc un model de calcul i o unitate de msur:

    Prelucrrile din algoritmi se efectueaz n mod secvenial (maina de tip von Newman este baza sistemelor de calcul actuale)

    Operaiile elementare sunt efectuate n timp constant, indiferent de valoarea operanzilor

    Timpul de acces la informaiile din algoritm nu depind de poziia acestora (nu exist diferene ntre prelucrarea diferitelor elemente dintr-un tablou)

    n concluzie, timpul de execuie al unui algoritm se exprim n numrul de operaii

    elemenate pe care algoritmul le execut. Sunt considerate operaii elementare:

    Instruciunile simple de atribuire

  • Evaluarea expresiilor logice sau de relatie din cadrul instruciunilor de decizie sau repetitive

    Evaluarea expresiilor aritmetice din cadrul instruciunii repetitive cu numr cunoscut de pai

    Considernd c toate operaiile elementare au acelai cost de execuie (presupus, n general,

    egal cu 1), timpul de execuie se obine prin nsumarea costurilor prelucrrilor din algoritm.

    S exemplificm operaia de analiz pe urmtorul algoritm tipic:

    Exemplul 2.13 S se determine valoarea maxim a unui ir de numere, precum i poziia din

    ir a valorii maxime. n cazul n care sunt mai multe valori maxime, s se determine ultima

    valoare. Descrierea formal este urmtoarea:

    Dndu-se n elemente, x1, x2, ..., xn, s se determine m i j astfel nct:

    m=xj=max(x1, x2, ..., xn),

    pentru care j este cel mai mare posibil.

    Analiza problemei.

    Se vor utiliza urmtoarele variabile de ieire:

    - m, pentru memorarea valorii maxime pn la valoarea curent care se testeaz; - j, pentru memorarea indicelui valorii maxime.

    Iniial, valoarea maxim se consider x1. Se vor parcurge pe rnd elementele irului de

    numere; dac elementul curent xi este mai mare dect valoarea maxim curent, acesta va

    deveni noua valoare maxim.

    Descrierea algoritmului.

    start

    1 citeste n

    2 pentru k 1 la n executa

    2.1 citeste xk

    3 m x1

    4 j 1

    5 pentru k 2 la n executa

    5.1 daca xk>m atunci

    5.1.1 m xk

    5.1.2 j k

    6 scrie m,j sfarsit

    Pentru a putea fi identificate, s-au notat instruciunile cu numere. Instruciunile interne unor

    instruciuni compuse s-au notat cu mai multe numere. De exemplu, instruciunea 5.1 este

    instruciunea de decizie intern instruciunii repetitive 5. n general, numrul de numere cu

    care este etichetat o instruciune indic nivelul de indentare al acesteia (nivelul de

    includere).

    Analiza algoritmului.

    A. Timpul de execuie

  • Pentru analiza algoritmului, trebuie precizate cteva elemente privind timpul de execuie al

    instruciunilor limbajului algoritmic:

    a) toate instruciunile simple au un timp egal de execuie (presupus egal cu 1); b) timpul de execuie al instruciunii de decizie este egal cu timpul de execuie al uneia

    dintre secvenele interne de instruciuni (acea care se va executa) plus timpul de

    evaluare al expresiei logice (presupus egal cu 1);

    c) timpul de execuie al instruciunilor repetitive cu test iniial i final se calculeaz dup urmtoarea formul:

    t = n*(t1+1) ,

    unde t1 reprezint timpul de execuie al instruciunilor din secvena intern, n numrul

    de iteraii al instruciunii; constanta 1 provine de la evaluarea expresiei logice la

    fiecare iteraie;

    d) timpul de execuie al instruciunii repetitive cu numr cunoscut de iteraii se calculeaz dup urmtoarea formul:

    t = 1+n*(t1+2) ,

    unde t1 reprezint timpul de execuie al instruciunilor din secvena intern, n numrul

    de iteraii al instruciunii; constanta 2 provine de la operaia de determinare a valorii

    curente a variabilei de control a instruciunii i de la evaluarea expresiei logice la

    fiecare iteraie, iar constanta 1 de la operaia de iniializare a variabilei de control.

    Se observ faptul c pentru determinarea timpului de execuie al unei instruciuni compuse,

    este necesar s se determine timpul de execuie al unei secvene de instruciuni. Acesta este

    egal cu suma timpilor de execuie al instruciunilor ce compun secvena.

    Se poate estima acum timpul de execuie:

    t = t1+t2+t3+t4+t5+t6,

    unde:

    t1 = t3 = t4 = t6 = 1,

    t2 = 1+n*(t2.1+2) = 1+n*3, pentru c t2.1 = 1,

    Rezult:

    t = 2+3*n+*t.

    Estimarea timpului t depinde de estimarea timpului de execuie a instruciunii 5.1. Aceasta

    este o instruciune scurt de decizie: din cele (n-1) apeluri ale sale, o parte execut

    instruciunile 5.1.1 i 5.1.2 (precum i evaluarea expresiei logice), iar cealalt doar evaluarea

    expresiei logice. Notnd cu a numrul de execuii ale secvenei interne, timpul de execuie al

    instruciunii 5 se poate scrie astfel:

    t5 = 1 + 2*(n-1) + a*3 + (n-1-a)*1

    Timpul total de execuie al algoritmului va fi:

    t = 5+3*n+t5 = 3+6*n+2*a.

    Singura valoare necunoscut este a, care reprezint numrul de modificri ale valorii maxime

    curente. Acest numr depinde de distribuia valorilor din ir, deci de execuia algoritmului i

    nu poate fi determinat exact n etapa de proiectare a acestuia.

    n mod uzual, timpul de execuie al unui algoritm nu poate fi determinat exact. Din

    acest motiv, analiza unui algoritm presupune determinarea unuia dintre urmtorii timpi de

    execuie (sau mai muli dintre acetia):

    - timpul maxim de execuie; - timpul minim de execuie; - timpul mediu de execuie.

  • n cazul algoritmului precedent, vor trebui determinate: valoarea minim, valoarea maxim i

    cea media a lui a.

    Valoarea minim a lui a este zero. Aceasta se ntmpl cnd irul este ordonat cresctor:

    x1 ... >xn. n

    acest caz, timpul maxim al algoritmului este:

    tmin = 1+8*n.

    Valoarea medie a lui a este cuprins ntre 0 i n-1, dar este mai greu de estimat. Pentru

    determinarea valorii medii, vor trebui fcute anumite presupuneri asupra caracteristicilor

    probabile pentru datele de intrare.

    Pentru algoritmul precedent vom considera c elementele xk sunt distincte i c

    fiecare din cele n! permutri ale acestora sunt echiprobabile. Aceast presupunere este uzual

    pentru cele mai multe situaii, dar analiza poate fi efectuat si pe baza altor presupuneri.

    Pentru cazul particular n=3, de exemplu, presupunem c urmtoarele ase situaii sunt

    la fel de probabile (alturat sunt specificate valorile lui a pentru cazul respectiv):

    - x1

  • Deoarece c1 = c2 = ... =cn = (n-1)!, rezult c:

    - Probabilitatea ca xn s aiba valoarea n este P(xn=n) = (n-1)! / n! = 1/n,

    - Probabilitatea ca xn sa aiba o alt valoare dect n (adic 1, 2,..., sau n-1) este

    P(xnn) = (n-1)*(n-1)! / n! = (n-1)/n,

    Din aceste observaii rezult o relaie de recuten pentru pnk:

    (2) pnk = 1/n*p(n-1)k+(n-1)/n*p(n-1)(k-1)

    n plus se pot determina valori iniiale pentru acest ir de probabiliti:

    (3a) p1k = 0k (adic p10=1 i p1k=0 pentru k0).

    Alte valori limit sunt pentru cazul n care kn:

    (3b) pnk = 0, dac kn.

    Funciile generatoare sunt utilizate pentru a obine informaii despre cantitile pnk.

    Considernd prin extensie pnk=0 pentru k>n, conform relaiei (3b), se poate considera funcia

    generatoare ca o serie infinit:

    (4) Gn(z) = pn0+pn1*z+pn2*z2+ ... = k(pnk*z

    k)

    Folosind condiiile (3a), se poate calcula G1(z):

    G1(z) = p10+p11*z+ ... = p10 + 0 = 1.

    Utiliznd relaiile de recuren (2), se poate determina i o relaie de recuren pentru funcia

    generatoare Gn:

    (5) Gn(z) = k0(pnk*zk) = k0((1/n*p(n-1)k+(n-1)/n*p(n-1)(k-1)) * z

    k) =

    = (1/n)*k0(p(n-1)k*zk) + (z*(n-1)/n)*k0(p(n-1)(k-1)*z

    k-1) =

    = (1/n)*Gn-1(z) + (z*(n-1)/n)*Gn-1(z)

    Prima derivat a funciei Gn se poate determina uor din relaia (4):

    (6) Gn1(z) = k(k*pnk*z

    k-1)

    Din relaiile (1), (6) i (3b) rezult:

    an = Gn1(1) =

    1

    0

    *n

    k

    nkpk

    n concluzie, pentru determinarea timpului mediu de execuie, trebuie determinat valoarea

    Gn1(1). Pentru determinarea lui Gn

    1(1) se deriveaz i relaia (5):

    Gn1(z) = 1/n* Gn-1(z)+z/n* Gn-1

    1(z)+(n-1)/n* Gn-1

    1(z)

    Gn1(z) = 1/n* Gn-1

    1(z) + (n-1)/n* Gn-1(z) + z*(n-1)/n* Gn-1

    1(z)

    Rezult:

    (7) Gn1(1) = 1/n* Gn-1

    1(1) + (n-1)/n* Gn-1(1) + (n-1)/n* Gn-1

    1(1) =

    = Gn-11(1) + (n-1)/n* Gn-1(1).

    Pe de alt parte, din relaiile (3) avem:

    G11(1) = p11+2*p12+3*p13 + ... = 0,

    iar, pentru orice numr n, rezult:

    Gn(1) = pn0 + pn1 + pn2 + ... + pnn + pn(n+1) + ... = 1 + 0 = 1.

    Calculul termenilor irului definit de relaia de recuren (7) se poate determina astfel:

    G21(1) = G1

    1(1) + 1/2*G1(1) = 0 + 1/2*1 = 1/2,

    G31(1) = G2

    1(1) + 2/3*G2(1) = 1/2 + 2/3*1 = 1/2 + 2/3,

    G41(1) = G3

    1(1) + 3/4*G3(1) = 1/2 + 2/3 + 3/4*1 = 1/2 + 2/3 + 3/4,

    ...

    Gn1(1) = 1/2 + 2/3 + 3/4 + ... + (n-1)/n.

    Rezult n final:

    an = Gn1(1) = 1/2 + 2/3 + 3/4 + ... + (n-1)/n

    Notnd cu Hn seria dat de relaia

  • (8) Hn = 1/2 + 2/3 + 3/4 + ... + (n-1)/n,

    rezult c timpul mediu de execuie al algoritmului este:

    (9) tmed = 3+6*n+2*a = 3+6*n+2*(Hn-1) = 1 + 6*n + 2*Hn.

    B. Notaia asimptotic

    O notaie convenabil pentru specificarea aproximaiilor este notaia O. Ea descrie pe scurt

    conceptul de aproximare i suprim informaia detaliat, care nu este n mod uzual

    revelatoare.

    Fie f i g dou funcii reale de variabil ntreag i pozitiv:

    f, g: NR+,

    Se spune c f(n) aproximeaz g(n) i se noteaz g(n)O(f(n)), dac exist o constant

    pozitiv M i un numr n0N, astfel nct: |g(n)| M*|f(n)|, pentru orice n n0.

    n general, pentru o funcie g: NR+, O(g(n)) reprezint mulimea de funcii:

    O(g(n)) = {f: NR+ | MR+, n0N, a.. 0 f(n) M*g(n), nn0}

    Intuitiv, faptul c f(n)O(g(n)) nseamn c f(n) crete asimptotic cel mult la fel de repede ca g(n).

    Prin abuz de limbaj, notaia g(n)O(f(n)) se scrie g(n)=O(f(n)).

    De exemplu, se poate scrie:

    12+2

    2+ ... +n

    2 = O(n

    3),

    ntr-adevr, avem:

    g(n) = 12+2

    2+ ... +n

    2 = n*(n+1)*(2*n+1)/6 = n

    3/3+n

    2/2+n/6.

    Considernd f(n)=n3, trebuie determinat M astfel nct |n

    3/3+n

    2/2+n/6| M*n

    3. Dar M poate

    fi ales astfel: M=1/3+1/2+1/6 i n0=1.

    n general, dac P(n) este un polinom de grad cel mult m, atunci:

    (10) O(P(n)) = O(a0+a1*n+ ... +am*nm

    ) = O(nm

    ).

    Cteva proprieti ale notaiei O:

    f(n)O(f(n)) - reflexivitate

    dac f(n)O(g(n)) i g(n)O(h(n)), atunci f(n)O(h(n)) tranzitivitate

    O(f(n)+g(n)) = O(max{f(n),g(n)})

    O(loga(n)) = O(logb(n)), pentru orice valori reale pozitive diferite, a i b.

    Primele dou proprieti permit notaiei O s defineasc clase de echivalen: f(n) i g(n)

    sunt echivalente dac f(n)O(g(n)). Clasele de echivalen corespunztoare se numesc clase

    de complexitate. Principalele clase de complexitate sunt urmtoarele:

    Complexitate logaritmic, O(lg(n)); de exemplu: cutarea binar

    Complexitate liniar, O(n); de exemplu: cutarea secvenial

    Complexitate ptraticic, O(n2); de exemplu: sortarea prin inserie

    Complexitate cubic, O(n3); de exemplu: produsul a dou matrici

    Complexitate exponenial, O(2n); de exemplu: prelucrarea tuturor submulimilor unei mulimi de n elemente

    Complexitate factorial, O(n!); de exemplu: prelucrarea tuturor permutrilor unei mulimi de n elemente

    Cu ajutorul acestei notaii, timpul minim i maxim de execuie al algoritmului precedent

    poate fi descris astfel:

  • tmin = 1+6*n = O(n),

    tmax = 1+8*n = O(n).

    Pentru exprimarea timpului mediu, se poate utiliza urmtoarea relaie:

    (11) 2*Hn = 2*(1 + 1/2 + ... + (n-1)/n) < 2*(n-1)

    Deoarece timpul mediu de execuie dat de relaia (9) este:

    tmed = 1+6*n+2*Hn,

    rezult din relaia (11):

    (12) tmed = 1+6*n+2*Hn 1+6*n+2*(n-1) = 8*n - 1.

    Folosind notaia asimptotic, din relaiile (9) i (12), rezult c i timpul mediu de execuie al

    algoritmului este:

    tmed = O(n).

    2.6 Probleme

    2.1. S se demonstreze matematic caracterul finit al algoritmului lui Euclid din exemplul 2.1.

    2.2. S se scrie algoritmul care determin valoarea: y = arcsin(x2+1), pentru un numr x dat, folosind doar funciile trigonometrice uzuale: sin, cos i arctg.

    2.3. Pentru o valoare ntrag n dat, s se scrie un algoritm care determin valorile urmtoarelor expresii:

    e1 = 2n+2

    -n

    e2 = 1/2+2/3+ ... +n/(n+1)

    e3 = (sin(1))/(n2+1)+(sin(2))/(n

    2+2)+ ... +(sin(n))/(n

    2+n)

    2.4. Se consider un punct n plan P(x0, y0) i o dreapt de ecuaie: f(x, y) = a*x+b*y+c = 0. S se scrie un algoritm care determin poziia punctului P fa de dreapt:

    a) pe dreapt, b) n semiplanul ce conine originea O(0, 0), c) n semiplanul ce nu conine originea O(0, 0).

    2.5. S se scrie un algoritm care determin dac un numr ntreg n este prim.

    2.6. S se scrie un algoritm care determin valoarea y = n x , pentru un numr real pozitiv x

    i un numr ntreg pozitiv n, efectund un numr minim de operaii de nmulire i

    extragere a rdcinii ptrate.

    Indicaie. Se vor determina cifrele numrului fracionar 1/n n baza 2 i se va utiliza

    forma polinomial a numrului 1/n.

    2.6. Se consider c o mulime este specificat prin numrul de elemente i vectorul ce conine elementele sale. S se scrie un algoritm care determin, intersecia, reuniunea

    i diferena a dou mulimi de numere date.

    2.7. Se consider o mulime finit A = {a1, a2, , an} i relaie binar R A A. Relaia

    se poate reprezenta printr-o matrice M, astfel: mij = 1, dac (aI, aj) R i mij = 0 altfel.

    Pentru o asemenea relaie binar, s se scrie un algoritm care determin dac ea este:

    - simetric,

  • - reflexiv, - tranzitiv.

    2.8. S se scrie un algoritm care determin polinomul sum i polinomul produs a dou polinoame cu coeficieni reali. Polinoamele sunt specificate prin gradele lor i vectorii

    coeficienilor.

    2.9. Se consider dou iruri de numere: x1, , xn i y1, , ym. S se scrie un algoritm care determin dac irul al doilea este un subir al primului (adic este format din elemente

    consecutive ale primului ir: exist un indice k astfel nct xk+i = yi, pentru i=1, 2, ,

    m).

    2.10. Se consider sistemul biel-manivel din figura alturat. n lungul axei Ox se mic o

    culis, iar manivela OA se mic n sens trigonometric cu viteza unghiular constant . S se scrie un algoritm care determin poziia i viteza punctului C situat la jumtatea

    distanei AB (adic valorile x, y, vx, vy ale acestuia), n puncte succesive pentru intervalul

    de timp [0, tmax], cu un pas de incrementare dt pentru variabila t. Se cunoate: tmax, , dt,

    |OA| = r, |AB| = l.

    2.11. Se consider n plan n puncte de coordonate: (x1, y1), (x2, y2), ..., (xn, yn). S se scrie un algoritm care determin dac poligonul cu vrfurile n punctele date este convex sau

    nu;

    2.12. S se determine timpul de execuie al algoritmului din exemplul 2.7.

    2.13. S se determine timpul minim, maxim i mediu de execuie al algoritmului din exemplul 2.6. Se va considera c irul de intrare conine n valori nenule.

    2.14. S se determine timpul minim, maxim i mediu de execuie al algoritmului din problema 2.6.

    2.15. S se determine timpul minim, maxim i mediu de execuie al algoritmului din problema 2.10.

    y

    x

    O

    A

    B

    C


Recommended