proiectarea algoritmilor

Upload: andrei-dolhescu

Post on 08-Oct-2015

102 views

Category:

Documents


1 download

DESCRIPTION

prezentare

TRANSCRIPT

  • 111

    Lect. univ. dr. Adrian Runceanu

    PROIECTAREA

    ALGORITMILOR

    Universitatea Constantin Brncui din Trgu-JiuFacultatea de Inginerie

    Departamentul de Automatic, Energie i Mediu

  • 122Proiectarea Algoritmilor - curs

    Cteva precizri

    Structura cursului

    2 ore curs titular curs Lector dr. Adrian Runceanu

    2 ore laborator titular aplicaii practice Lector dr. Adrian Runceanu

  • 133Proiectarea Algoritmilor - curs

    Cteva precizri

    Forme de examinare:

    Examen final 60% Evaluare pe parcursul

    semestrului a activitii de laborator 30%

    Prezen curs i laborator 10%

  • 144Proiectarea Algoritmilor - curs

    Cteva precizri

    Bibliografia necesar cursului:

    1. Dogaru, O., Tehnici de programare, Editura MIRTON, Timioara, 2002, 2004

    2. Creu, V., Structuri de date i algoritmi, vol.1 Structuri de date fundamentale, Editura Orizonturi Universitare, Timioara, 2000

    3. Livovschi, L.,Georgescu, H., Sinteza i Analiza algoritmilor, Editura tiinific i Enciclopedic, Bucureti, 1986

    4. Wirth, N., Algorithms and Data Structures, Prentice Hall,

    Inc.,Englewood, New Jersey, 1986

    5. Dr. Kris Jamsa & Lars Klander, Totul despre C si C++ - Manualul

    fundamental de programare n C si C++, ed. Teora, 1999-2006

  • 155Proiectarea Algoritmilor - curs

    Cteva precizri

    Bibliografia necesar cursului:

    6. Liviu Negrescu, Limbajele C si C++ pentru nceptori, vol. II, Limbajul C++, ed. MicroInformatica, 1995

    7. A.Runceanu, Metode si tehnici de programare indrumar de laborator, Editura Academica Brancusi Targu-Jiu, 2003

    8. Horia Ciocrlie, Tehnici fundamentale de programare, Ed. Orizonturi Universitare, 2002

    9. Pagina web pentru curs:

    http://www.runceanu.ro/adrian

  • 166Proiectarea Algoritmilor - curs

    Cteva precizri

    Referinele bibliografice nr. 1 i 7 se pot mprumuta de la Biblioteca Facultii de Inginerie, Str. Geneva nr.3, Etaj I lng Decanat.

    1. Suport curs - varianta electronic disponibil pe siteul:

    http://www.runceanu.ro/adrian

    2. ndrumar de laborator - varianta electronic disponibil pe site pentru fiecare lucrare de laborator.

    Not: Actualizarea site-ului se face sptmnal.

  • 177Proiectarea Algoritmilor - curs

    Coninutul cursului

    n cadrul acestui curs se vor studia metode i tehnici de programare pentru elaborarea eficient a algoritmilor.

    Exemplificrile de la curs i implementrile de la laborator se vor efectua cu ajutorul

    limbajului de programare - C++.

    Mediul de dezvoltare utilizat la aplicatiile practice este MinGW.

  • 188Proiectarea Algoritmilor - curs

    Capitolele cursului

    1. Recursivitate

    2. Alocarea dinamic de memorie n C++3. Liste simplu i dublu nlnuite4. Elemente de teoria grafurilor

    5. Algoritmi pentru prelucrarea grafurilor

    6. Arbori. Arbori binari

    7. Metoda Greedy de elaborare a algoritmilor

    8. Metoda Divide et Impera de elaborare a

    algoritmilor

    9. Metoda Backtracking de elaborare a algoritmilor

    10. Combinatoric

  • 199Proiectarea Algoritmilor - curs

    Curs 1

    Recursivitate

  • 11010

    Coninutul cursului

    1. Conceptul de recursivitate

    2. Recursivitate direct

    3. Recursivitate indirect

    4. Relaia dintre recursivitate i iteraie

    5. Exemple de programe recursive

    Proiectarea Algoritmilor - curs

  • 11111

    1. Conceptul de recursivitate

    Un obiect sau un fenomen este definit n modrecursiv dac n definitia sa se face referire la elnsusi.

    Conceptul de recursivitate ofer posibilitateadefinirii unei infinitti de obiecte printr-un numrfinit de relatii.

    O functie este recursiv atunci cnd executareaei implic cel putin nc un apel ctre ea nssi.

    Proiectarea Algoritmilor - curs

  • 11212

    1. Conceptul de recursivitate

    Tipuri de recursivitate:

    1.Recursivitate direct apelul recursiv se face chiar din functia invocat.

    2.Recursivitate indirect (mutual) apelul recursiv se realizeaz prin intermediul mai multor functii care se apeleaz circular.

    Proiectarea Algoritmilor - curs

  • 11313

    Exemplul 1

    Definirea numerelor naturale:

    1 este numr natural

    succesorul unui numr natural este un numrnatural

    Se presupune cunoscut definiiasuccesorului unui numr: acel numr obinut dinnumrul dat prin adugarea unei uniti.

    Proiectarea Algoritmilor - curs

  • 11414

    Exemplul 2

    Algoritm de calcul pentru factorialul unui

    numr n. (notatie n!):

    dac n = 0 atunci n! = 1

    dac n > 0 atunci n! = n * (n-1)!

    Astfel spus, factorialul unui numr n > 0 se obineprin nmulirea numrului cu factorialulpredecesorului.

    Proiectarea Algoritmilor - curs

  • 11515

    Coninutul cursului

    1. Conceptul de recursivitate

    2. Recursivitate direct

    3. Recursivitate indirect

    4. Relatia dintre recursivitate si iteratie

    5. Exemple de programe recursive

    Proiectarea Algoritmilor - curs

  • 11616

    Recursivitate direct

    n limbajul C++ functiile se pot apela peele nsele, adic sunt direct recursive.

    Pentru o functionare corect (din punct devedere logic), apelul recursiv trebuie s fieconditionat de o decizie care, la un moment

    dat n cursul executiei, s mpiedicecontinuarea apelurilor recursive si s permitastfel revenirea din sirul de apeluri.

    Proiectarea Algoritmilor - curs

  • 11717

    Recursivitate direct

    Lipsa acestei conditii sau programarea ei

    gresit va conduce la executarea unui sir deapeluri a crui terminare nu mai este controlatprin program si care, la epuizarea resurselor

    sistemului, va provoca o eroare de executie:

    Depsirea stivei de date.

    Proiectarea Algoritmilor - curs

  • 11818

    Exempluvoid p (list de parametri){lista variabile locale

    ...

    p(list de parametri);}

    Conditia care trebuie testat este specific problemei de rezolvat.

    Programatorul trebuie s o identifice n fiecare situatie concret si, pe baza ei, s redacteze corect apelul recursiv.

    Revenirea din apeluri se face n ordine invers.

    if (cond) p(list de parametri) ... sau:while (cond) { ...p(list de parametri) } sau:do ... p(list de parametri)... while (cond)

  • 11919

    Coninutul cursului

    1. Conceptul de recursivitate

    2. Recursivitate direct

    3. Recursivitate indirect

    4. Relatia dintre recursivitate si iteratie

    5. Exemple de programe recursive

    Proiectarea Algoritmilor - curs

  • 12020

    Recursivitate indirect

    Un subprogram S, n corpul cruia apar apeluri la S (la el nsui) se numete subprogram direct recursiv iar un subprogram P, pentru care exist un subprogram Q, astfel nct P face apeluri la Q, iar Q conine apelul la P se numete subprogram indirect recursiv.

    n acest ultim caz, subprogramele P i Q se mai numesc i mutual recursive.

    Proiectarea Algoritmilor - curs

  • 12121

    Recursivitate indirect

    Funcie direct recursiv

    functia S;

    {

    S; // apel la functia S

    }

    Funcii mutual recursivefunctia P;

    {

    Q ; // apel la functia Q

    }

    functia Q;

    {

    P ; // apelul functiei P

    }

    Proiectarea Algoritmilor - curs

  • 12222

    Coninutul cursului

    1. Conceptul de recursivitate

    2. Recursivitate direct

    3. Recursivitate indirect

    4. Relatia dintre recursivitate si iteratie

    5. Exemple de programe recursive

    Proiectarea Algoritmilor - curs

  • 12323

    Relaia dintre recursivitate iiteraie - Comparaie

    Iteraia

    executia repetat a uneisecvente de instructiuni

    o nou iteratie se execut doarn urma evalurii unei conditii(la nceput sau sfrsit)

    fiecare iteratie se execut pnla capt si apoi se trece,eventual, la o nou iteratie

    se recomand atunci cndalgoritmul de calcul esteexprimat printr-o formuliterativ

    Recursivitatea

    executia repetat a unei functii

    un nou apel recursiv se execut tot n urma evalurii unei conditii (pe parcurs)

    functia recursiv se apeleazdin nou, nainte de terminareaapelului precedent

    se recomand doar atunci cndproblema este prin definitie

    recursiv (recursivitateaconsum resurse n exces)

    Proiectarea Algoritmilor - curs

  • 12424

    Coninutul cursului

    1. Conceptul de recursivitate

    2. Recursivitate direct

    3. Recursivitate indirect

    4. Relatia dintre recursivitate si iteratie

    5. Exemple de programe recursive

    Proiectarea Algoritmilor - curs

  • 12525

    Probleme rezolvate

    1. Se dau doua numere intregi a si b si se cere sa se calculeze cel mai mare divizor comun. (Algoritmul lui EUCLID prin mpriri repetate).

    Formularea recursiv, n cuvinte, a algoritmului:

    Dac unul dintre numere este zero, c.m.m.d.c. al lor este cellalt numr.

    Dac nici unul dintre numere nu este zero, atuncic.m.m.d.c. nu se modific dac se nlocuieste unul dintre numere cu restul mprtirii sale cu cellalt.

    Proiectarea Algoritmilor - curs

  • 12626

    Probleme rezolvate

    Algoritmul poate fi implementat sub forma

    urmtoarei functii recursive:

    int cmmdc (int n, int m)

    {

    if (n==0) return m;

    else return cmmdc(n, m % n);

    }

    Proiectarea Algoritmilor - curs

  • 12727

    Probleme rezolvate

    Codul sursa al implementarii (varianta prin scaderi succesive) este urmatorul:

    #include

    int cmmdc(int a,int b)

    {

    if(a==b) return a;

    else if(a>b) return cmmdc(a-b, b);

    else return cmmdc(a, b-a);

    }

    Proiectarea Algoritmilor - curs

  • 12828

    int main(void)

    {

    int a, b;

    char c;

    do

    {

    couta;

    coutb;

    cout

  • 12929

    Executia programului pentru cateva date de test:

    Proiectarea Algoritmilor - curs

  • 13030

    Probleme rezolvate

    2. S se calculeze suma primelor n numerenaturale.

    Soluia este dat de relaia de recuren:

    suma(1, 2, . . . , n) =

    suma(n, suma(1, 2, . . . , n-1))

    Proiectarea Algoritmilor - curs

  • 13131

    #include

    long int suma(long int i)

    {

    if(i==1) return 1;

    else return suma(i-1)+i;

    }

    int main(void)

    {

    long int n;

    coutn;

    cout

  • 13232

    Executia programului pentru o valoare de test:

    Proiectarea Algoritmilor - curs

  • 13333

    Probleme rezolvate

    3. S se afle elementul maxim dintr-un vector dat.

    Soluia este dat de relaia de recuren:

    maxim(a1, a2 , . . . ,an) =

    maxim(an, maxim(a1, a2, . . . , an-1))

    Proiectarea Algoritmilor - curs

  • 13434

    #include

    int a[100],n,i;

    int max(int x, int y)

    {

    if(x > y) return x;

    else return y;

    }

    int maxim(int a[ ],int n)

    {

    if(n==1) return a[1];

    else return max(a[n],maxim(a,n-1));

    }

    int main(void)

    {

    coutn;

    for(i=1;i

  • 13535

    Executia programului pentru cateva valori de test:

    Proiectarea Algoritmilor - curs

  • 13636

    Probleme rezolvate

    4. Sa se transforme un numar n, dat in baza

    10, intr-o alta baza b (2

  • 13737

    #include

    int n,b;

    void baza(int n)

    {

    if(n

  • 13838

    Executia programului pentru cateva valori de test:

    Proiectarea Algoritmilor - curs

  • 13939

    Probleme rezolvate

    5. Se citeste un numar intreg ca un sir de

    caractere cu cel mult 255 cifre.

    Sa se afiseze numarul cu cifrele in ordine

    inversa.

    Proiectarea Algoritmilor - curs

  • 14040

    #include

    #include

    char n[255],i,l;

    void invers(int i)

    {

    if(i

  • 14141

    Executia programului pentru o valoare de test:

    Proiectarea Algoritmilor - curs

  • 14242

    Probleme rezolvate

    6. Suma puterilor rdcinilor

    Fie ecuaia x2 - Sx + P = 0 cu S, P R si x1, x2 rdcinile ecuaiei.

    S se calculeze Sn= x1n + x2

    n , n N.

    Proiectarea Algoritmilor - curs

  • 14343

    Cutm relaia de recuren pentru Sn, tiind c x1, respectiv x2 sunt rdcinile ecuaiei date i deci ndeplinesc relaiile:

    x12 - Sx1 + P = 0 | * x1

    n-2

    x22 - Sx2 + P = 0 | * x2

    n-2

    nmulim aceste relaii cu x1n-2 i x2

    n-2 i adunm relaiile obinute i rezult:

    Sn = x1n + x2

    n =

    = S * (x1n-1 + x2

    n-1 ) P * (x1n-2 + x2

    n-2 ) =

    = S * Sn-1 - P * Sn-2

    Proiectarea Algoritmilor - curs

  • 14444

    Astfel am obinut o relaie de recuren:

    S0 = x11 + x2

    1 = 1 + 1 = 2, pentru n=0

    S1 = x11 + x2

    1 = S, pentru n=1

    Sn = S * Sn-1 - P * Sn-2, pentru n 2

    Proiectarea Algoritmilor - curs

  • 14545

    #include

    int n;

    float s,p,r;

    float suma(int n)

    {

    if(n==0) return 2;

    else if(n==1) return s;

    else return(s*suma(n-1)-p*suma(n-2));

    }

    int main(void)

    {

    cout

  • 14646

    Executia programului pentru un set de valori de test:

    Proiectarea Algoritmilor - curs

  • 14747

    Probleme propuse spre rezolvare

    1. S se scrie un program care s calculeze al n-lea termen din irul lui Fibonacci, care este definit recursiv astfel:

    fib[1]=0

    fib[2]=1

    fib[n]=fib[n-1] + fib[n-2], pentru n>2

    2. S se caute o soluie nerecursiv pentru irul lui Fibonacci.

    Proiectarea Algoritmilor - curs

  • 14848Proiectarea Algoritmilor - curs

    ntrebri?