Coordonator tiinific:

Conf. dr. CLIN ENCHESCUAbsolvent:

Farkas Sndor

INTRODUCEREAceast lucrare este un mediu educaional pentru cei

interesai de teoria algoritmilor, mai precis a unei pridin aceast materie, i anume: tehnici de programare. Scopul acestei lucrri este s prezinte, ntr-o manier

accesibil pentru utilizatorii tehnicii de calcul, cteva metode de programare cum ar fi: Backtracking, Divide et

Impera, Branch & Bound, Greedy i Programare dinamic).

Se au n vedere att aspectele teoretice ale problemelor,

ct i cele practice, fiecare capitol coninnd pe lng teorie, probleme rezolvate i probleme propuse.

Lucrarea poate fi folosit ca suport de curs i laborator, fiind gndit pentru un semestru de predare. Ea poate sluji la fel de bine ca suport de studiu individual.

Fiecare capitol este compus din patru pri:

Prima parte este teoria general, n care sunt descrise ideile generale a fiecrei metode de

programare

n partea a doua sunt descrise cteva exemple rezolvate, simulate prin Visual Caf.

Partea a treia conine problemele, care sunt propuse celor care au neles ideea tehnicilor i

stpnesc cel puin la nivel superficial, unul dintre limbajele de programare n care sunt realizate

implementrile.

Partea a patra este un test de verificare tip gril, pentru cei care doresc s-i verifice cunotinele.

Coninutul lucrrii:

I. Metoda Backtracking

II. Metoda Branch and Bound

III. Metoda Divide et Impera

IV. Metoda Greedy

V. Metoda Programrii dinamice

Capitolul I.Metoda Backtracking

Aceast metod de programare se foloseten cazul problemelor ce ndeplinesc simultanurmtoarele trei condiii:

- soluia lor poate fi pus sub forma de vectoriS = x1, x2, ... , xn, cu x1 aparinnd mulimii A1,x2 aparinnd mulimii A2, ..., xn aparinndmulimii An ;

- mulimile A1, A2, ... , An sunt mulimi finite, iarelementele lor se consider c se afl ntr-orelaie de ordine bine stabilit;

- nu se dispune de o alt soluie mai rapid.

Metoda Backtracking const n urmtoarele:

- se alege primul element, x1, ce aparine A1 ;

- presupunnd generate elementele x1, x2, ..., xk,aparinnd mulimilor A1, A2, ..., Ak, se alege(dac exist) xk+1, primul element disponibil dinmultimea Ak+1 care ndeplinete anumite condiiide continuare, aprnd astfel dou posibiliti:

a) elementul exist, se testeaz dac nus-a ajuns la o soluie, n caz afirmativaceasta se tiprete, n caz contrar seconsider generate x1, x2, ..., xk, xk+1;

b) elementul nu exist, situaie n care seconsider generate elementele x1, x2, ... ,xk-1, relundu-se cutarea de la elementulurmtor lui xk n multimea Ak ;

- algoritmul se ncheie cnd au fost luate nconsideraie toate elementele mulimii A1.

Ca aplicaii ale metodei Backtracking, am prezentat algoritmi pentru:

- generarea aranjamentelor- generarea combinrilor- generarea permutrilor- generarea partiiilor unei mulimi- problema plii unei sume s, utiliznd n tipuri

de metode

Acest capitol conine i un subcapitol care propune spre rezolvare cteva probleme, folosind metoda Backtracking.

Capitolul II.Metoda Branch and Bound

Metoda va folosi o list n care vor fi nscrisevrfuri ale arborelui spaiului de stri pentru a fiprelucrate la un moment ulterior, numite vrfuri active.

Dintre vrfurile active se alege cte un vrfpentru a fi prelucrat, care se numete vrf curent.

Cunoatem dou modaliti de parcurgere aarborilor care respect condiiile enunate i anumeparcurgere BF (n care lista vrfurilor active areorganizare de coad) i D (n care lista vrfurilor activeeste organizat ca stiv).

Acest capitol conine i un subcapitol care propune spre rezolvare cteva probleme, folosind metoda Branch and Bound.

Pentru nelegerea acestei metode se dau dou exemple, care aplic algoritmul Branch and Bound:

- lampa lui Dario Uri- problema macaralei

Pentru clarificarea metodei presupunem c sed un vector A=( a1, a2 , ..., aN) i c trebuieefectuat o prelucrare oarecare asupra elementelorsale. Mai mult, presupunem c pentru orice p, q

naturali cu 1 p < q N, exist m{p, ... , q-1}, astfelnct prelucrarea secvenei {ap, ... , aq} se poate faceprelucrnd secvenele {ap, ... , am} i {am+1, ... , aq}i apoi combinnd rezultatele pentru a obineprelucrarea dorit a ntregii secvene {ap, ... , aq}.

Capitolul III.

Metoda Divide et Impera

Pentru nelegerea acestei metode se dau cteva exemple, care aplic algoritmul Divide et Impera:

- problema turnurilor din Hanoi- sortarea rapid- sortarea prin interclasare

Acest capitol conine i un subcapitol care propune spre rezolvare cteva probleme, folosind metoda Divide et Impera.

Aceast tehnic se folosete n situaia n care estedat o mulime A cu n elemente de intrare i se cere sse gseasc o submulime B a sa, care sndeplineasc anumite condiii pentru a fi acceptat; -cum n general exist mai multe astfel de mulimi, semai d i un criteriu conform cruia dintre submulimileacceptabile (numite soluii posibile) s alegem unasingur(numit soluie optim). Soluiile posibile auurmtoarea proprietate: dac b este soluie posibil i Cinclus n B, atunci i n C este soluie posibil; vompresupune c este ntotdeauna soluie posibil.

Capitolul IV.

Metoda Greedy

Metoda Greedy trateaz acest tip de probleme n urmtoarele dou moduri, care urmeaz aceeai idee dar difer doar prin ordinea de efectuare a unor operaii

a) Algoritmul Greedy 1

Se pleac de la soluia vid, se alege pe rnd, ntr-un anumit fel, un element din A neales la paii precedeni. Dac adugarea lui la soluia parial anterior construit conduce la o soluie posibil, construim noua soluie posibil prin adugarea elementului ales.

b) Algoritmul Greedy 2

Se procedeaz similar, cu excepia faptului c se stabilete de la nceput ordinea n care trebuie considerate elementele.

Pentru o explicaie ct mai clar a acestei metode se dau cteva exemple, care aplic algoritmul Greedy:

- problema comis-voiajorului- algoritmul lui Prim- problema tetrix

Acest capitol conine i un subcapitol care propune spre rezolvare cteva probleme, folosind metoda Greedy.

Capitolul V.Metoda programrii dinamice

Programarea dinamic este o metod de proiectare a algoritmilor care poate fi utilizat n cazul n care soluia problemei poate fi privit ca rezultatul unei succesiuni de decizii. De remarcat faptul c este posibil ca decizia luat la un moment dat s depind de cele luate n etapele anterioare.

O modalitate de rezolvare a problemelor pentru

care nu este posibil s se efectueze o secven de decizii care s conduc la soluia optim const n ncercarea tuturor secvenelor posibile de decizii.

Programarea dinamic ofer posibilitatea reducerii drastice a secvenelor de decizii, eliminndu-le pe cele care nu conduc la soluia optim.Rezolvarea unei probleme de programare dinamic se face respectnd urmtoarele etape:

- verificarea principiului de optimalitate n una din cele 3 forme ale sale;

- scrierea relaiilor care apar, corespunztoare formei n care este verificat principiul de optimalitate;

Pentru o explicaie ct mai clar a acestei metode se dau cteva exemple, care aplic algoritmul programrii dinamice:

- subir cresctor de lungime maxim- problema reconstituirii frazei

- problema tirului

Acest capitol conine i un subcapitol care propune spre rezolvare cteva probleme, folosind metoda programrii dinamice.