Search:


| Hemorrhoid pain relief


Algoritmi.

Algoritmi.


Despre algoritmi.

    Recursivitatea, folosita cu multa eficienta in matematica, s-a impus in programare, odata cu aparitia unor limbaje de nivel inalt, ce permit scrierea de module ce se autoapeleaza (PASCAL,LISP,ADA,ALGOL,C sint limbaje recursive, spre deosebire de FORTRAN,BASIC,COBOL, nerecursive).Recursivitatea e strins legata de iteratie, dar daca iteratia e executia repetata a unei portiuni de program, pina la indeplinirea unei conditii (while, repeat, for din PASCAL), recursivitatea presupune executia repetata a unui modul, insa in cursul executiei lui (si nu la sfirsit, ca in cazul iteratiei), se verifica o conditie a carei nesatisfacere, implica reluarea executiei modulului de la inceputul sau. Atunci un program recursiv poate fi exprimat: P=M(Si,P) , unde M este multimea ce contine instructiunile Si si pe P insusi.

    Structurile de program necesare si suficiente in exprimarea recursivitatii sint procedurile si subrutinele ce pot fi apelate prin nume. Recursivitatea poate fi directa - un modul P contine o referinta la el insusi, sau indirecta - un modul P contine o referinta la un modul Q ce include o referinta la P.

    1.1. Parametrii-valoare si parametrii-variabila. >>>
    Discutia se face pentru cazul implementarii recursivitatii in PASCAL, dar lucrurile sint similare pentru limbajul C. In PASCAL, exista doua tipuri de parametri formali (ce apar in antetul unei proceduri sau functii) : valoare si variabila (ultimii au numele precedat de cuvintul cheie var).

    Apelul recursiv al unei proceduri (functii) face ca pentru toti parametrii-valoare sa se creeze copii locale apelului curent (in stiva) , acestea fiind referite si asupra lor facindu-se modificarile in timpul executiei curente a procedurii (functiei). Cind executia procedurii (functiei) se termina, copiile sint extrase din stiva, astfel incit modificarile operate asupra parametrilor-valoare nu afecteaza parametrii efectivi de apel, corespunzatori.De asemenea pentru toate variabilele locale se rezerva spatiu la fiecare apel recursiv.In cazul parametrilor-variabila, nu se creaza copii locale, ci operarea se face direct asupra spatiului de memorie afectat parametrilor efectivi, de apel.

    Concluzie:

      * Pentru fiecare apel recursiv al unei proceduri (functii) se creaza copii locale ale parametrilor valoare si variabilelor locale, ceea ce poate duce la risipa de memorie;
      * Orice parametru-variabila poate fi suprimat prin referirea directa in procedura (functie) a variabilei ce figura ca parametru de apel.

    O metoda grafica de reprezentare a unui algoritm.

    1.2. Verificarea si simularea programelor recursive. >>>
    Se face ca in cazul celor nerecursive, printr-o demonstratie formala, sau testind toate cazurile posibile.Se verifica intii daca toate cazurile particulare (ce se executa cind se indeplineste conditia de terminare a apelului recursiv) functioneaza corect.Se face apoi o verificare formala a procedurii (functiei) recursive, pentru restul cazurilor, presupunind ca toate componentele din codul procedurii (functiei) functioneaza corect.Verificarea e deci inductiva.Acesta e un avantaj al programelor recursive, ce permite demonstrarea corectitudinii lor simplu si clar.

    Un exemplu de functie recursiva implementata in cod Pascal:

    function fact(n:integer):integer;
    begin
      if n=1 then fact:=1
      else fact:=n*fact(n-1)
    end;

    Demonstrarea corectitudinii cuprinde doi pasi:

      * Pentru n=1 valoarea 1 ce se atribuie factorialului este corecta;
      * Pentru n>1, presupunind corecta valoarea calculata pentru predecesorul lui n de fact(n-1), prin inmultirea acesteia cu n se obtine valoarea corecta a factorialului lui n.

    1.3. Tehnica eliminarii recursivitatii. >>>
    Orice program recursiv poate fi transformat in unul iterativ, dar algoritmul sau poate deveni mai complicat si mai greu de inteles. De multe ori, solutia unei probleme poate fi elaborata mult mai usor, mai clar si mai simplu de verificat, printr-un algoritm recursiv.

    Dar pentru implementare, poate fi necesara transformarea algoritmului recursiv in unul nerecursiv, in situatiile:

      * Solutia problemei trebuie scrisa intr-un limbaj nerecursiv; un caz particular sint compilatoarele ce "traduc" un program recursiv dintr-un limbaj de nivel inalt in cod masina (nerecursiv);
      * Varianta recursiva ar duce la o viteza de executie si spatiu de memorie prea mari, transformarea in una nerecursiva, eliminind dezavantajele.

    In continuare se va prezenta una din metodele de eliminare a recursivitatii ce foloseste o structura de date de tip stiva.In scrierea unei varianta nerecursive, trebuie parcursi toti pasii implicati in varianta recursiva, prin tehnici nerecursive.Recursivitatea implica folosirea a cel putin unei stive. La fiecare apel recursiv sint depuse in stiva niste date, care sint extrase la revenirea din acel apel. E simplu daca datele pentru un apel se organizeaza intr-un record, un apel insemnind introducerea in stiva a unui record, revenirea, extragerea lui.

    Se prezinta eliminarea recursivitatii pentru un program simplu, care citeste caracterele tastate pe o linie, tiparindu-le apoi in ordine inversa.

    program var_recursiva;
       procedure prel_car;
      var car:char;
      begin
        read(car);
        if not eoln then prel_car;
        write(car)
      end;
      begin
        prel_car
      end.
    program var_nerecursiva;
      begin
        *initializeaza stiva
        while not eoln do
          begin
            read(car);
            push(car)
          end;
      while not stiva_goala do
        begin
          pop(car);
          write(car)
        end
      end.


    2. Exemple de algoritmi recursivi.

    2.1. Algoritmi de traversare si inversare a unei structuri. >>>
    Traversarea si inversarea unei structuri inseamna efectuarea unor operatii oarecare asupra tuturor elementelor unei structuri in ordine directa, respectiv in ordine inversa.Desi mai uzuale sint variantele iterative, caz in care inversarea echivaleaza cu doua traversari directe (o salvare in stiva urmata de parcurgerea stivei), variantele recursive sint mai elegante si concise. Se pot aplica structurilor de tip tablou, lista, fisier si pot fi o solutie pentru diverse probleme (transformarea unui intreg dintr-o baza in alta, etc).

    Intr-o forma generala, algoritmii se pot scrie:

    procedure traversare(element:tip_element);  {apel initial}
      {al procedurii se face cu primul element al structurii}
      begin
        prelucrare(element);
        if element <> ultimul_din_structura then
          traversare(element_urmator)
      end;
    procedure inversare(element:tip_element);   {apelul initial}
      {al procedurii se face cu primul element al structurii}
      begin
        if element <> ultimul_din_structura then
          traversare(element_urmator);
        prelucrare(element)
      end;

    De observat importanta ca parametrul formal al celor doua proceduri sa fie de tip valoare, pentru a nu fi alterat de apelul recursiv.

    2.2. Algoritmi care implementeaza definitii recursive. >>>
    O definitie recursiva e cea in care un obiect se defineste prin el insusi. Definitia contine o conditie de terminare, indicind modul de parasire a definitiei si o parte ce precizeaza definirea recursiva propriu-zisa.Ca exemple: algoritmul lui Euclid de aflare a c.m.m.d.c., factorialul, ridicarea la o putere intrega (prin inmultiri repetate), definirea recursiva a unei expresii aritmetice, curbele recursive, un mod de a privi permutarile, etc.

    2.3. Algoritmi de divizare. >>>
    Tehnica divizarii ("divide and conquer"), fundamentala in elaborarea algoritmilor, consta in descompunerea unei probleme complexe in mai multe subprobleme a caror rezolvare e mai simpla si din solutiile carora se poate determina solutia problemei initiale (exemple: gasirea minimului si maximului valorilor elementelor unui tablou, cautarea binara, sortarea rapida (quicksort), turnurile din Hanoi).

    Un algoritm de divizare general s-ar putea scrie:

    procedure rezolva(x:problema);
      begin
        if {x e divizibil in subprobleme} then
          begin
            {divide pe x in parti x1,...,xk}
            rezolva(x1); {...} rezolva(xk);
            {combina solutiile partiale intr-o}
          {solutie pentru x}
        end
        else {rezolva pe x direct}
      end;

    2.4. Algoritmi cu revenire (backtracking). >>>
    Metoda se aplica problemelor in care solutia se poate reprezenta sub forma unui vector x=(x1,x2,...xn) c S=S1 x S2 x...x Sn, unde multimile Si sint finite, S numindu-se spatiul solutiilor posibile. In particular, Si sint identice avind acelasi numar M de elemente. Pentru fiecare problema concreta sint date anumite relatii intre componentele vectorului x, numite conditii interne.Determinarea tuturor solutiilor rezultat se poate face generind toate solutiile posibile si verificind apoi care satisfac conditiile interne. Dar timpul de calcul ar fi foarte mare (daca multimile Si ar avea numai cite 2 elemente, timpul ar fi proportional cu 2**n).

    Metoda backtracking urmareste evitarea genararii tuturor solutiilor. Elementele vectorului x primesc valori pe rind, lui x1 i se atribuie valori, doar daca x1,x2,...,xi-1 au primit deja, valorile atribuite trebuind sa verifice conditiile de continuitate referitoare la x1,x2,...,xi. Doar apoi se trece la calculul lui xi+1. In cazul neindeplinirii conditiilor de continuitate, se alege urmatoarea valoare posibila pentru xi, daca Si a fost epuizat, se micsoreaza i, incercind o alta alegere pentru xi-1.

    procedure backtracking(i:integer); {gaseste valoarea lui xi}
      var posibilitate:integer; {pentru toate valorile}
      {posibile ale lui xi}
      begin
        for posibilitate:=1 to M do
        begin
          if acceptabila then
          begin
            inregisteaza_posibilitatea;
            if i < n then backtracking(i+1)
            else afiseaza_solutia:
            sterge_inregistrarea
          end
          end
        end;

    Pe acesta metoda se bazeaza rezolvarea unor probleme clasice ca: "opt regine", a "relatiilor stabile", colorarea unei harti, taierea unui fir de lungime l in parti de lungimi date, etc.O varianta a acestei metode este cea in care, pentru un xi c vector solutie , xi+1 poate fi ales dintr-un numar M de posibilitati:

    procedure back1(i:posibilitate);
    begin
      if acceptabila then
      begin
        inregistreaza;
        if solutie_incompleta then for k:=1 to M
          do back1(posibilitate_k)
        else tipareste_solutia;
        sterge_inregistrarea
      end
    end;

    Aceasta varianta se foloseste la rezolvarea problemelor: "saritura calului", iesirea dint-un labirint, etc. Se preteaza atunci cind pasul initial este definit si/sau numarul de pasi ai solutie nu este cunoscut.

    3. Timpul de executie al unui algoritm. >>>

    De multe ori, pentru rezolvarea unei probleme, trebuie ales un algoritm dintre mai multi posibili, doua criterii principale de alegere fiind contradictorii:

      * Algoritmul sa fie simplu de inteles, de codificat si de depanat;
      * Algoritmul sa foloseasca eficient resursele calculatorului, sa aiba un timp de executie redus.


    Daca programul care se scrie trebuie rulat de un numar mic de ori, prima cerinta este mai importanta; in aceasta situatie, timpul de punere la punct a programului e mai important decit timpul lui de rulare, deci trebuie aleasa varianta cea mai simpla a programului.Daca programul urmeaza a fi rulat de un numar mare de ori, avind si un numar mare de date de prelucrat, trebuie ales algoritmul care duce la o executie mai rapida. Chiar in aceasta situatie, ar trebui implementat mai inainte algoritmul mai simplu si calculata reducerea de timp de executie pe care ar aduce-o implementarea algoritmului complex.

    Timpul de rulare al unui program depinde de urmatorii factori:

      * Datele de intrare;
      * Calitatea codului generat de compilator
      * Natura si viteza de executie a instructiunilor programului
      * Complexitatea algoritmului care sta la baza programului.

    Deci timpul de rulare e o functie de intrarea sa, de cele mai multe ori, nedepinzind de valorile de la intrare, ci de numarul de date.

    Se noteaza cu T(n) timpul de rulare al unui program, ale carui date de intrare au dimensiunea n. De exemplu T(n) poate fi cn^2, unde c este o constanta.Daca timpul de rulare depinde de valorile datelor de la intrare, in calculul lui T(n) se va lua in considerarea situatia cea mai defavorabila, cea care duce la timpul cel mai mare.Cum timpul de rulare depinde nu numai de intrare (n) si de algoritm, ci si de performantele calculatorului pe care se executa programul, T(n) se apreciaza ca fiind proportional cu o anumita functie de n si nu se exprima in unitati reale de timp, deci T(n)=cf(n).

    Timpul T(n) de rulare al unui program, poate fi apreciat printr-o functie O(f(n)), daca exista constantele pozitive c si n0, astfel incit T(n)<=cf(n), oricare ar fi n>=n0. Functia O(f(n)) reprezinta aproximarea limitei superioare a lui T(n) si se spune ca T(n) este O(f(n)), iar f(n) se numeste limita superioara a ratei de crestere a lui T(n).

    Exemplul 1: T(n)=3n^3+2n^2 este O(n^3), pentru ca 3n^3+2n^2<=5n^3, pentru orice n>=0.

    Pentru specificarea limitei inferioare a ratei de crestere a lui T(n), se foloseste functia @(g(n)) si se spune T(n) este @(g(n)), insemnind ca exista constanta pozitiva c, astfel incit T(n)>=cg(n), pentru o infinitate de valori ale lui n.

    Exemplul 2: T(n)=n^3+2n^2 este @(n^3), pentru ca pentru c=1, T(n)=n^3+2n^2>=n^3, pentru o infinitate de valori ale lui n, cele n>=0.

    In comparatia intre timpii de rulare ai diferitelor programe (sau a diferitelor variante ale aceluiasi program), constantele de proportionalitate nu pot fi intotdeauna neglijate. Spre exemplu, s-ar putea spune ca un program avind O(n^2) este mai rapid decit unul cu O(n^3), dar, in cazul cind constantele ar fi 100, respectiv 5, al doilea program este mai rapid pentru n < 20.

    Exista urmatoarele cazuri cind rata de crestere a timpului de executie, nu e cel mai bun criteriu de apreciere a performantelor unui algoritm:

      * Daca un program se ruleaza de putine ori, se alege algoritmul cel mai usor de implementat;
      * Daca intretinerea trebuie facuta de o alta persoana decit cea care l-a scris, un algoritm simplu,chiar mai putin eficient, e de preferat unuia performant, dar foarte complex si greu de inteles;
      * Exista algoritmi foarte eficienti, dar care necesita un spatiu de memorie foarte mare, astfel incit folosirea memoriei externe, le diminueaza foarte mult performantele.

    Inainte de prezentarea citorva reguli pentru determinarea timpului de executie al unui program, se dau cele referitoare la suma si produsul functiei O:

    A: Daca T1(n) si T2(n) sint timpii de executie a doua secvente de program P1 si P2, T1(n) fiind O(f(n)), iar T2(n) fiind O(g(n)), atunci timpul de executie T1(n)+T2(n), al secventei P1 urmata de P2, va fi O(max(f(n),g(n))).Iata un exemplu:

      Exista c1 si n1 astfel incit T1(n)<=c1f(n), pentru orice n>=n1 si
      exista c2 si n2 astfel incit T2(n)<=c2g(n), pentru orice n>=n2.
      Notind n0=max(n1,n2), pentru n>=n0
      T1(n)+T2(n)<=c1f(n)+c2g(n)<=(c1+c2)max(f(n),g(n)).

    Exemplul 3: Avind trei secvente de program cu timpii O(n^3),O(n^2) si O(n*log n), conform regulii anterior prezentate, timpul total de executie a celor trei secvente va fi O(max(max(n^3,n^2),n*log n))= O(max(n^3,n*log n))=O(n^3).

    B: Daca T1(n) este O(f(n)) si T2(n) este O(g(n)),atunci T1(n)T2(n) este O(f(n)g(n)).

    Citeva reguli generale pentru evaluarea timpului de executie, functie de marimea n a datelor de intrare, sint:

      * Timpul de executie a unei instructiuni de asignare, citire sau scriere, este O(1);
      * Timpul de rulare a unei secvente de instructiuni e determinat de regula de insumare, fiind proportional cu cel mai lung timp din cei ai instructiunilor secventei;
      * Timpul de executie a unei instructiuni if-then-else este suma dintre timpul de evaluare a conditiei (O(1)) si cel mai mare dintre timpii de executie ai instructiunilor pentru conditie adevarata sau falsa;
      * Timpul de executie a unei instructiuni de ciclare este suma, pentru toate iteratiile, dintre timpul de executie a corpului instructiunii si cel de evaluare a conditiei de terminare (O(1));
      * Pentru evaluarea timpului de executie a unei proceduri recursive, se asociaza fiecarei proceduri recursive un timp necunoscut T(n), unde n masoara argumentele procedurii; se poate obtine o relatie recurenta pentru T(n), adica o ecuatie pentru T(n), in termeni T(k), pentru diferite valori ale lui k;
      * Timpul de executie poate fi analizat chiar pentru programele scrise in pseudocod; pentru secventele care cuprind operatii asupra unor TDA, se pot alege citeva implementari si astfel se poate face comparatie intre performantele implementarilor, in contextul aplicatiei respective.

    Exemplul 4: Mai jos se prezinta modul de evaluare a timpului de executie a procedurii de sortare a elementelor unui tablou de dimensiune n prin metoda "interclasarii":

    type int_array=array[1..n] of integer;
    procedure bubble(var a:int_array); {sortare crescatoare}
    var i,j,temp:integer;
    begin
      (1) for i:=1 to n-1 do
      (2) for j:=n downto i+1 do
      (3) if a[j-1]>a[j] then begin
      (4) temp:=a[j-1];
      (5) a[j-1]:=a[j];
      (6) a[j]:=temp
      end
    end; {bubble}

    Timpii de rulare pentru instructiunile de asignare (4),(5) si (6) sint O(1), deci pentru secventa (4)-(6), timpul este O(max(1,1,1))=O(1).

    Pentru instructiunea if-then (3), timpul este suma dintre cel pentru evaluarea conditiei, O(1) si cel al secventei ce se executa la conditie adevarata, tot O(1), calculat mai sus, deci O(1), acesta fiind deci si timpul pentru o iteratie a instructiunii for (2).

    Pentru cele n-i iteratii ale lui for (2), timpul de executie este O((n-i)*1)=O(n-i).

    Pentru instructiunea for (1), avind n-1 iteratii, timpul de executie este:

    S(i=1,n-1)(n-i)=(n-1)+(n-2)+...+(n-n+1)=n^2/2-n/2, deci este O(n^2).

    Exemplul 5: Modalitatea de evaluare a timpului de executie al unei proceduri recursive, este ilustrata prin cea a functiei de calcul al factorialului:

    function factorial(n:integer):integer;
    begin
      (1)  if n<=1 then
      (2)  factorial:=1
      else
      (3)  factorial:=n*factorial(n-1)
    end; {factorial}

    Dimensiunea intrarii este aici n, valoarea numarului al carui factorial se calculeaza si se noteaza cu T(n), timpul de rulare al functiei factorial(n).Timpul de rulare pentru liniile (1) si (2) este O(1), iar pentru linia (3) este O(1)+T(n-1), deci cu constantele c si d neprecizate:

    T(n)=c+T(n-1), pentru n>1 sau T(n)=d , pentru n<=1.

    Pentru n>2, expandind pe T(n-1), se obtine T(n)=2c+T(n-2), pentru n>2.

    Pentru n>3, expandind pe T(n-2), se obtine T(n)=3n+T(n-3), pentru n>3.

    Deci, in general

    T(n)=ic+T(n-i), pentru n>i.

    In final, cind i=n-1, se obtine T(n)=(n-1)c+T(1)=(n-1)c+d.

    Deci T(n) este O(n).

    4. Cele mai utilizate functii in analiza algoritmilor. >>>

    Aici este prezentata o lista a celor mai utilizate functii cu ajutarul carora se analizeaza algoritmii.Toate aceste functii cresc de la numarul n< catre infinit.Primele functii prezentate sunt functiile care cresc mai greu de la n catre infinit.numarul c este o constanta arbitrara.

    Notatia

    Numele

    Exemplu

    O(1)

    constanta

    Determina daca un numar este par sau impar

    O(log* n)

    algoritmii iterativi

    Algoritmul gaseste al lui Hopcroft si Ullman pentru datele partitionate.

    O(log n)

    logaritmica

    Gaseste un termen sortat intr-o lista sortata utilizand un arbore binar de cautare.

    O((log n)c)

    polilogaritmica

    Decide daca n este prim folosind un test de tip AKS

    O(nc),0

    putere fractionara

    Cauta intr-un arbore k-dimensionat

    O(n)

    liniara

    Gaseste un element intr-o lista nesortata.

    O(n log n)

    liniaritmica

    Sorteaza o lista folosind algoritmul de sortare prin ansamble

    O(n 2)

    patratica

    Sorteaza o lista cu metodasortarii prin insertie

    O(nc), c > 1

    polinomiala, cateodata numita algebrica

    Gaseste drumul intr-un arbore parcurs in adancime utilizand algoritmul lui Floyd-Warshall

    O(cn)

    exponentiala, cateodata denumita si geometrica

    Gaseste (fixeaza) solutia pentru "problema comisvoiajorului" (sub presupunearea ca P ≠ NP)

    O(n !)

    factoriala, cateodata mai este denumita si combinationala

    Determina daca doua functii logice sunt echivalente, solutioneaza problema comisvoiajorului.

    O(2cn)

    dublu exponentiala

    Gaseste un grup complet de date asociative-comutative uniform

Structuri de date abstracte | SDA Arbori | SDA Arbori Binari | SDA Arbori Multicai | SDA Arbori Optimi | SDA Graf | Traversarea grafurilor | SDA Graf Ponderat | SDA Graf Orientat | SDA Lista Inlantuita | SDA Tablou Asociat | Despre algoritmi. | Algoritmi de cautare neinformata, cautarea inforamata,cautarea in liste,in grafuri, in SQL-uri | Algoritmi de cautare liniara, binara, interpolare | Prezentare Algoritmi Sortare | Sortare Insertie cu Pas Variabil (Shellsort) | Sortarea Prin Ansamble (Heapsort) | Sortarea Prin Insertie (Insertionsort) | Sortarea Prin Interclasare (Mergesort) | Sortarea Prin Interschimbare (Bubblesort) | Sortarea Prin Selectie (Selectionsort) | Sortarea Rapida (Quicksort)

Inapoi la pagina principala



©2006-2007 frankeman Software - Timisoara. Toate drepturile sunt rezervate.