Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» Notiunea de algoritm. Analiza algoritmilor


Notiunea de algoritm. Analiza algoritmilor


Notiunea de algoritm. Analiza algoritmilor

1. Notiunea de algoritm

Termenul algoritm isi are sorgintea in numele autorului persan Abu Ja'far Mohamed Ibn Musa Al Khowarismi care in anul 825 i.e.n. a redactat un tratat de matematica in care prezenta pentru prima data metode de rezolvare generice pentru anumite categorii de probleme.



In activitatea de programare vom conveni ca prin algoritm sa intelegem o 'modalitate de rezolvare a unei probleme utilizand un sistem de calcul'

Un algoritm este de fapt o metoda sau o reteta pentru a obtine un rezultat dorit.

Un algoritm consta din:

Un set de date initiale care abstractizeaza contextul problemei de rezolvat

Un set de relatii de transformare care sunt operate pe baza unor reguli al caror continut si a caror succesiune reprezinta insasi substanta algoritmului

Un set de rezultate preconizate sau informatii finale, care se obtin trecand de regula printr-un sir de informatii (rezultate) intermediare.

Un algoritm se bucura de urmatoarele proprietati:

(1) Generalitate - un algoritm nu rezolva doar o anume problema ci o clasa generica de probleme de acelasi tip;

(2) Finitudine - informatia finala se obtine din cea initiala trecand printr-un numar finit de transformari;

(3) Unicitate - transformarile si ordinea in care ele se aplica sunt univoc determinate de regulile algoritmului. Ori de cate ori se aplica acelasi algoritm asupra aceluiasi set de date initiale se obtin aceleasi rezultate.

Scopul capitolului analiza performantei algoritmilor.

Analiza algoritmilor

La ce serveste analiza algoritmilor ?

(1) Permite precizarea predictiva a comportamentului algoritmului;

(2) Prin analiza pot fi comparati diferiti algoritmi si poate fi astfel ierarhizata experienta si indemanarea diversilor producatori [HS78].

Analiza algoritmilor se bazeaza de regula pe doua ipoteze

(1) Sistemele de calcul sunt considerate conventionale adica ele executa cate o singura instructie la un moment dat

(2) Timpul total de executie al algoritmului rezulta din insumarea timpilor instructiilor individuale componente.

Desigur aceasta ipoteza nu este valabila la sistemele de calcul paralelele si distribuite.

In astfel de cazuri aprecierea performantelor se realizeaza de regula prin masuratori experimentale si metode statistice.

In general, analiza unui algoritm se desfasoara in doua etape:

(1) Analiza apriorica

Consta in aprecierea din punct de vedere temporal a operatiilor care se utilizeaza si a costului lor relativ.

Conduce de regula la stabilirea expresiei unei functii care margineste timpul de executie al algoritmului

(2) Testul ulterior

Consta in stabilirea unui numar suficient de seturi de date initiale care sa acopere practic toate posibilitatile de comportament ale algoritmului

Testarea comportamentul algoritmului pentru fiecare set in parte

Se finalizeaza prin culegerea unor date in baza carora pot fi elaborate o serie de statistici referitoare la consumul de timp specific executiei algoritmului in cauza (profilul algoritmului).

Concluzie

Analiza apriorica are drept scop principal determinarea teoretica a ordinului de marime al timpului de executie al unui algoritm

Testul ulterior are ca scop principal determinarea efectiva a acestui ordin prin stabilirea profilului algoritmului

3. Notatii asimptotice

  • Ordinul de marime al timpului de executie al unui algoritm:
    • Reprezinta o masura a eficientei algoritmului
    • Permite compararea relativa a variantelor de algoritmi.
  • Studiul eficientei asimptotice a unui algoritm, se realizeaza utilizand marimi de intrare cu dimensiuni suficient de mari pentru a face relevant numai ordinul de marime al timpului de executie al algoritmului.
  • Intereseaza cu precadere limita la care tinde timpul de executie al algoritmului odata cu cresterea nelimitata a dimensiunii intrarii.
  • De regula, un algoritm care este "asimptotic mai eficient" decat altii, va constitui cea mai buna alegere si pentru intrari de dimensiuni mici si foarte mici.

3.1. Notatia O (O mare)

Notatia O desemneaza marginea asimptotica superioara a unei functii. Pentru o functie data g(n), se defineste O(g(n)) ca si multimea de functii:

O(g(n)) = [3.a]

Notatia O se utilizeaza pentru a desemna o margine superioara a unei functii in interiorul unui factor constant.

Pentru toate valorile n superioare lui n0 , valoarea functiei f(n) este pe sau dedesubtul lui g(n) (fig.3.b ).


Fig.3.b. Reprezentarea lui f(n) = O(g(n))

In baza formulei 3.a], se poate demonstra faptul ca orice functie patratica a n  + b n + c , a > este O(n 2).

o      Pur si simplu se alege valoarea constantei c astfel incat sa fie mai mare decit a. Termenii de grad mai mic ca 2 se neglijeaza.

o      Este surprinzator faptul ca functia liniara a n  + b este de asemenea O(n 2), lucru usor de verificat in baza aceleasi formule 3.a], daca se alege c = a + | b | si n0 = 1.

Notatia O este de obicei cea mai utilizata in aprecierea timpului de executie al algoritmilor respectiv a performantei acestora.

Ea poate fi uneori apreciata direct din inspectarea structurii algoritmului, spre exemplu existenta unei bucle duble conduce imediat la o margine de ordinul O(n 2)

Deoarece notatia O descrie o margine superioara, cand este utilizata pentru a margini cazul cel mai defavorabil de executie al unui algoritm, prin implicatie ea margineste superior comportamentul algoritmului in aceeasi masura pentru orice intrare.

Cele mai obisnuite ordine de marime ale notatiei O se afla in relatiile de ordine prezentate in [3.c], iar reprezentarea lor grafica la scara logaritmica apare in fig.3.c.

O(1) < O(log  n) < O(n) < O(n log n) < O(n ) < O(n ) <
< O(2
n) < O(10 n) < O( n ! ) < O(n n)    [3.c]


Fig. 3.c. Ordine de marime ale notatiei O

In acelasi context in [3.d] se prezinta cateva sume intregi utile care sunt frecvent utilizate in calculul complexitatii algoritmilor.

[3.d]



3. Aritmetica ordinala a notatiei O

  • In vederea aprecierii complexitatii algoritmilor in raport cu notatia O, a fost dezvoltata o aritmetica ordinala specifica care se bazeaza pe o serie de reguli formale [De89].
  • Aceste reguli sunt prezentate in continuare.
    • Regula 1. O(k) < O(n) pentru k .
    • Regula Ignorarea constantelor: k f(n) O(f(n)) pentru k si f sau O( k f ) = O( f )
    • Regula 3. Tranzitivitate: daca f(n) O(g(n)) si g(n) O(h(n)) atunci f(n) O(h(n))

Demonstratie:

f(n) = O(g(n)) T c , n f(n) c1 g(n) pentru n > n

g(n) = O(h(n)) T c , n g(n) c2 h(n) pentru n > n

  • Se alege n3 = max .
  • In relatia f(n) c1 g(n) se inlocuieste     g(n) cu expresia de mai sus. Se obtine relatia:

f(n) c ( c h(n))

  • Alegand c3 = c1 c se obtine f(n) c3 h(n) pentru n > n deci f(n) = O(h(n)).
    • Regula 4 f(n) + g(n) = O( max
    • Regula 5 Daca f (n) = O( g  (n)) si f  (n) = O( g  (n))
      atunci f (n) f  (n) = O( g  (n) g  (n))
  • Utilizand aceste reguli se poate calcula o estimare a lui O pentru o expresie aritmetica data, fara a avea valori explicite pentru k si n.

Exemplul 3. Se considera expresia

8  n log(n) + 4  n

si se cere o estimare a sa in termenii notatiei O.

Se procedeaza dupa cum urmeaza:

o      log (n) = O(n1/ 2) deoarece logaritmul unui numar este mai mic decat orice putere pozitiva a numarului in baza urmatoarei teoreme:

o      Fie a > 0 si a 

o      Pentru exponent d > 0 exista un numar  N  astfel incat pentru x > N avem log a x < x d

o      n log(n) = O(n n  O(n 3/2) (Regula 5).

o      n log(n) = O(n 3/2) (Regula 2).

o      n  = O(n 3/2) (Regula 2).

o      n log(n) + n  = O(max ) =



O(max O(n 3/2) (Regula 4).

  • Rezulta in urma estimarii ca expresia 8 n log(n) + n  este O(n 3/2).

4. Aprecierea timpului de executie

Cu ajutorul notatiei O mare se poate aprecia timpul de executie al unui algoritm.

Se face sublinierea ca se poate aprecia timpul de executie al unui algoritm abstract si nu al unui program intrucat acesta din urma depinde de mai multi factori:

o      (1) Dimensiunea si natura datelor de intrare

o      (2) Caracteristicile sistemului de calcul pe care se ruleaza programul

o      (3) Eficienta codului produs de compilator.

Notatia O mare permite eliminarea factorilor care nu pot fi controlati (spre exemplu viteza sistemului de calcul) concentrandu-se asupra comportarii algoritmului independent de program.

o      In general un algoritm a carui complexitate temporala este O(n 2) va rula ca si program in O(n 2) unitati de timp indiferent de limbajul sau sistemul de calcul utilizat.

In aprecierea timpului de executie se porneste de la ipoteza simplificatoare deja enuntata, ca fiecare instructie utilizeaza in medie aceeasi cantitate de timp.

Instructiunile care nu pot fi incadrate in aceasta medie de timp sunt:

o      (1) Instructiunea IF

o      (2) Secventele repetitive (buclele)

o      (3) Apelurile de proceduri si functii.

Presupunand pentru moment ca apelurile de proceduri si functii se ignora, se adopta prin conventie urmatoarele simplificari:

o      (1) Se presupune ca o instructiune IF va consuma intotdeauna timpul necesar executiei ramurii celei mai lungi, daca nu exista ratiuni contrare justificate;

o      (2) Se presupune ca intotdeauna instructiunile din interiorul unei bucle se vor executa de numarul maxim de ori permis de conditia de control.

Exemplul 4.a.

Se considera o procedura care:

o      (1) Cauta intr-un tablou a cu n elemente, un element egal cu cheie

o      (2) Returneaza in variabila unde ultima locatie in care este gasita cheia sau zero in caz contrar [4.a].

PROCEDURE CautareLiniara(n,cheie: integer,   

a: TablouNumeric; VAR unde: integer);

VAR indice: integer;

BEGIN

unde: = 0

FOR indice:= 1 TO n DO

IF a[indice]= cheie THEN [4.a]

unde:= indice

END


Intrarea in procedura si initializarea O(1)

variabilei unde

Bucla FOR (n reluari)    O(1+n+1) = O(n)

Instructiunea IF si O(1) O(n*1) = O(n)

ramura sa

Revenirea din procedura O(1)

Fig. 4.a. Schema temporala a algoritmului [4.a]

In figura 4.a apare schema temporala a algoritmului impreuna cu estimarea O mare corespunzatoare.

In analiza au fost introduse si operatiile de intrare si revenire din procedura care nu apar ca parti explicite ale rutinei.

Pe viitor apelul si revenirea din procedura vor fi omise din analiza temporala deoarece ele contribuie cu un timp constant la executie si nu influenteaza estimarea O mare

Exemplul 4.b Se considera urmatoarea portiune de cod [4.b].

FUNCTION SumProd(n: integer): integer;

VAR rezultat,k,i: integer;

BEGIN

rezultat:= 0;

FOR k:= 1 TO n [4.b]

FOR i:= 1 TO k

rezultat:= rezultat+k*i;

SumProd:= rezultat

END;


initializare rezultat O(1)


bucla FOR (n reluari)

bucla FOR (n reluari)

O(n*1) = O(n) O(n*n) = O(n2) O(1+n2) = O(n2)

interior O(1)

Fig. 4.b. Schema temporala a algoritmului din secventa [4.b]

La analiza complexitatii temporale se face presupunerea ca ambele bucle se reiau de numarul maxim de ori posibil

o      In realitate acest lucru nu este adevarat deoarece bucla interioara se executa cu limita k n ( si nu cu limita n)

Se va demonstra ca prin aceasta simplificare estimarea temporala finala nu este afectata.

La o analiza mai aprofundata se tine cont de faptul ca bucla FOR interioara se executa prima oara o data, a doua oara de 2 ori s.a.m.d, a k-oara de k ori.

o      In consecinta numarul exact de reluari este cel precizat de expresia de mai jos si dupa cum se observa el este O(n2)



1 + 2 + 3 + + n = [4.c]

In mod analog in cadrul secventei [4.d] se ajunge la estimarea: O(n  n  n) = O(n3).

FOR i:= 1 TO n DO

FOR j:= 1 TO i DO

FOR k:= 1 TO i DO [4.d]

Secventa ;

  • Calculul exact al numarului de reluari conduce la valoarea precizata de relatia [4.e], tinand cont de faptul ca cele doua bucle interioare se executa de i2 ori la fiecare reluare a buclei exterioare FOR

12 + 22 + 32 + + n 2 = = O(n 3) [4.e]

5. Profilarea unui algoritm

Presupunem ca un algoritm a fost conceput, implementat, testat si depanat pe un sistem de calcul tinta

Ne intereseaza profilul performantei sale, adica timpii precisi de executie ai algoritmului pentru diferite seturi de date, eventual pe diferite sisteme tinta.

o      Pentru aceasta sistemul de calcul tinta trebuie sa fie dotat cu un ceas intern si cu functii sistem de acces la acest ceas.

Dupa cum s-a mai precizat, determinarea profilului performantei face parte din testul ulterior al unui algoritm si are drept scop determinarea precisa a ordinul de marime al timpului de executie al algoritmului.

o      Informatiile rezultate sunt utilizate de regula pentru a valida sau invalida, respectiv pentru a nuanta rezultatele estimarii apriorice.

Se presupune un algoritm implementat in forma unui program numit Algoritm(X: Intrare,Y: Iesire)unde X este intrarea iar Y iesirea.

Pentru a construi profilul algoritmului este necesar sa fie concepute:

o      Seturile de date de intrare a caror dimensiune creste intre anumite limite, pentru a studia comportamentul algoritmului in raport cu dimensiunea intrarii

o      Seturile de date care in principiu se refera la cazurile extreme de comportament.

o      O procedura cu ajutorul careia poate fi construit profilul algoritmului in baza seturilor de date anterior amintite.

procedure Profil;

begin

*initializeaza procedura Algoritm;

*afiseaza('Testul lui Algoritm. Timpii in milisecunde');

repeat

*citeste(SetDeDate);    [5.a]

*afiseaza('Un nou set de date:', SetDeDate);

*apel TIME(t);

*apel Algoritm(SetDeDate, Rezultate);

*apel TIME(t1);

*afiseaza('TimpExecutie=', t - t1);

until sfarsit(SetDeDate)

end

Procedura Profil poate fi utilizata in mai multe scopuri functie de obiectivele urmarite.

o      Evidentierea performantei intrinseci a unui algoritm precizat.

Pentru aceasta se aleg, asa cum s-a mai precizat, seturi de date cu dimensiuni din ce in ce mai mari.

Rezultatul va fi profilul algoritmului.

Pentru deplina conturare a profilului se testeaza de asemenea si cazurile de comportament extrem ale algoritmului respectiv cazul cel mai favorabil respectiv cazul cel mai defavorabil.

o      (2) Evidentierea performantei relative a doi sau mai multi algoritmi diferiti care indeplinesc aceeasi sarcina.

In acest scop se executa procedura Profil pentru fiecare din algoritmi in parte, cu aceleasi seturi de date intiale, pe un acelasi sistem de calcul.

Compararea profilelor rezultate permite ierarhizarea performantelor algoritmilor analizati.

    • (3) Evidentierea performantei relative a doua sau mai multe sisteme de calcul.
      • In acest scop se ruleaza procedura Profil pentru un acelasi algoritm, cu aceleasi date initiale pe sistemele de calcul tinta supuse analizei.
      • Compararea profilelor rezultate permite ierarhizarea performantelor sistemelor de calcul analizate.
      • De regula, pe piata sistemelor de calcul se utilizeaza in acest scop algoritmi consacrati, in anumite cazuri standardizati, cunoscuti sub denumirea de 'bench marks' in baza carora sunt evidentiate performantele diferitelor arhitecturi de sisteme de calcul.

Trebuie insa acordata o atentie speciala procedurii TIME a caror rezultate in anumite circumstante pot fi nerevelevante.

o      Astfel, in cazul sistemelor time-sharing, al sistemelor complexe care lucreaza cu intreruperi sau al sistemelor multi-procesor, timpul furnizat de aceasta functie poate fi complet needificator.

o      In astfel de cazuri, una din solutii este aceea de a executa programul de un numar suficient de ori si de a apela la metode statistice pentru evidentierea performantelor algoritmului testat.

6. Rezumat

Prin algoritm se intelege o modalitate de rezolvare a unei probleme utilizand un sistem de calcul. Un algoritm este de fapt o metoda sau o reteta pentru a obtine un rezultat dorit.

Din punct de vedere formal in definirea unui algoritm se porneste de la un set de date initiale care abstractizeaza contextul problemei de rezolvat, asupra caruia se aplica un set de relatii de transformare

Un algoritm se bucura de urmatoarele proprietati: generalitate, finitudine si unicitate 

Analiza unui algoritm se desfasoara in doua etape: (1) analiza apriorica care are drept scop principal determinarea teoretica a ordinului de marime al timpului de executie al unui algoritm si (2) testul posterior are ca scop principal stabilirea profilului algoritmului.

Pentru aprecierea ordinului de marime al timpului de executie al unui algoritm se utilizeaza notatiile asimptotice

Notatia O este o notatie asimptotica care desemneaza marginea asimptotica superioara a unei functii. Notatia O este utilizata in aprecierea timpului de executie al algoritmilor. Ea poate fi uneori apreciata din inspectarea structurii algoritmului. Pentru a simplifica aceasta activitate se utilizeaza regulile aritmeticii ordinale a notatiei O

Aprecierea timpului executie al unui algoritm se realizeaza de regula analizand schema sa temporala in termenii notatiei O.

Profilarea unui algoritm se realizeaza pe baza masurarii timpilor de executiei ai algoritmului pentru diverese seturi de date.

7. Exercitii

Definiti notiunea de algoritm. Care sunt elementele constitutive ale unui algoritm?

Care sunt proprietatile de care se bucura un algoritm?

La ce serveste analiza algoritmilor? Care sunt etapele analizei unui algoritm?

Cum se defineste notatia O?

Care este relatia de ordonare a celor mai obisnuite ordine de marime al e notatiei O?

Care sunt regulile aritmeticii ordinale a notatiei O?

Se cere sa se estimeze in termenii functiei O urmatoarea expresie: 3n2+5n+25n*log(n)

Se cere sa se estimeze in termenii notatiei O timpul de executie al algoritmuli de cautare liniara respectiv al algoritmului de cautare binara.

Ce este profilarea unui algoritm? Schitati o functie cu ajutorul careia se poate construi profilul unui algoritm oarecare. Care sunt etapele constructiei profilului unui algoritm?







Politica de confidentialitate





Copyright © 2024 - Toate drepturile rezervate