Atestat informatic PROGRAMARE DINAMIC

Atestat informatic PROGRAMARE DINAMIC

PROGRAMARE DINAMIC

LUCRARE PENTRU ATESTAREA COMPETENELOR PROFESIONALE

Elev: Arhip GeorgianaProfesor ndrumtor: Balacea GeorgetaColegiul Naional Vasile Alecsandri GalaiSesiunea Mai 2013

Cuprins

1. Motivarea alegerii temei pag. 32. Introducere n programarea dinamic pag. 4-63. Descrierea metodei pag. 7-84. Probleme de alocare unidimensional pag. 95. Un model mathematic pag. 106. Posibiliti de rezolvare pag. 11-127. Probleme clasice ce se rezolv prin metoda programrii dinamice pag. 12-188. Tehnici avansate de programare dinamic pag. 19-36

MOTIVAREA ALEGERII TEMEI

Am ales ca tem pentru acest proiect programarea dinamic deoarece reprezint o metod de programare foarte interesant. Avnd ca scop rezolvarea ntr-un mod optim a problemelor, implementarea acestei metode este provocatoare, fiind mai complex dect o rezolvare neoptim a aceleiai probleme. Provocarea const n a gndi o rezolvare dinamic a unei probleme, i apoi n implementarea acestei rezolvri n limbajul de programare, lucru ce poate fi mai dificil dect sun. Scopul acestui proiect este de a explica pe nelesul tuturor aceast metod de programare i de a strni interesul pentru aceasta i pentru tipurile de probleme ce suport o rezolvare dinamic. Majoritatea problemelor date la Olimpiada de Informatic se rezolv cu ajutorul acestei metode, de aceea consider c programarea dinamic este important.

INTRODUCERE N PROGRAMAREA DINAMIC

Dac analizm natura problemelor care au fost rezolvate prin programare liniar sau prin teoria grafurilor, constatm c procesul economic pe care doream s l optimizm se desfura ntro singur faz (etap sau perioad). innd cont de faptul c exist numeroase probleme de optimizare care modeleaz procese economice care se desfoar n mai multe perioade i la fiecare perioad trebuie s stabilim soluia optim, viziunea static poate constitui un neajuns. Este evident faptul c succesiunea de soluii nu se poate determina innd seama numai de parametrii fiecrei perioade analizate n parte, i c este necesar s identificm o succesiune de soluii care optimizeaz ntregul proces analizat. Problemele economice care reclam o suit de decizii secveniale se caracterizeaz prin faptul c o decizie care adoptat ntr-o anumit perioad are att un efect economic imediat, ct i unul de lung durat, care influeneaz i asupra celorlalte etape. Optimizarea proceselor secveniale se obine prin metodele unei teorii matematice relativ recent constituite i care se numete programare dinamic. Creatorul acestei teorii este Richard Bellman, iar lucrarea sa fundamental este Dynamic Programming aprut n anul 1957. Programarea dinamic are un cmp larg de aplicaie n cercetarea operaional (organizarea produciei, gestiunea stocurilor, rennoirea echipamentelor), precum i n alte domenii (navigaie cosmic, procese cu conexiune invers etc.). S presupunem un proces secvenial a crui desfurare n timp depinde de o variabil care poate lua o mulime de valori n fiecare etap. Ne putem decide pentru o valoare determinat a variabilei n fiecare etap i din aceast cauz ea se numete variabil de decizie sau de control. O succesiune oarecare de decizii constituie o politic i cea care ne intereseaz este politica optim, de pild aceea care conduce la un cost total minim al procesului. Deosebim dou tipuri principale de procese secveniale: a) deterministe, cnd la fiecare faz procesul este controlat n ntregime de decizia pe care o lum;b) stohastice, atunci cnd evoluia procesului se desfoar sub dubla influen a deciziilor i a hazardului. Se numete politic optim acea succesiune de decizii care optimizeaz procesul n ansamblu lui, fiind vorba de un proces determinist. n cazul unui proces stohastic, se folosete n mod corespunztor noiunea de strategie optim. Procesele dinamice pot fi continue sau discrete. Un exemplu de proces discret este urmtorul: o ntreprindere trebuie s-i ntocmeasc planul de aprovizionare anual pentru un anumitmaterial; se consider 12 perioade (luni) i pentru fiecare perioad se stabilete cantitatea de aprovizionat, astfel ca pe ntregul an s rezulte un cost total minim. Procesele dinamice discrete pot avea orizontul limitat (n exemplu de mai sus 12 perioade) sau nelimitat.Programarea Dinamic (PD) este o metod de rezolvare a unor probleme de optimizare n care se opereaza pe FAZE (SECVENTE) numite n continuare PERIOADE. Prin aplicarea acestei metode, soluia optim se obtine n urma rezolvarii unui ir de probleme de optimizare LEGATE INTRE ELE, fiecare de de dimensiune si complexitate mult mai mic decat problema original. Dei teoretic PD este aplicabil oricarei probleme de optimizare multidimensional, totui metoda a dat rezultate foarte bune - n sensul uurrii rezolvrii - numai pe anumite clase de probleme cum sunt cele care modeleaz evoluia n timp a unui proces economic sau probleme de alocare (repartiie).Programarea dinamic rezolv problemele prin descompunerea lor n subprobleme i prin combinarea rezolvrilor acestora (termenul programare" se refer aici la o metod tabular). Spre deosebire de divide et impera, care considera c subproblemele sunt independente, programarea dinamic se aplic atunci cnd subproblemele nu sunt independente. ntr-un astfel de caz, divide et impera ar efectua calcule redundante, rezolvnd fiecare subproblem ca i cnd nu ar mai fi ntlnit-o. Programarea dinamic, ns, salveaz rezultatul fiecrei subprobleme ntr-o tabel, evitnd astfel rezolvarea redundant a aceleiai probleme.

Programarea dinamic se aplic n general problemelor de optimizare, atunci cnd dorim s determinm rapid soluia optim pentru o problem. De fapt, aplicnd aceast tehnic determinm una din soluiile optime, problema putnd avea mai multe soluii optime.Aplicarea acestei tehnici de programare poate fi descompus n urmtoarea secven de pai:1. Descoperirea structurii i "msurii" pe care o are o soluie optim.2. Definirea recursiv a valorii care caracterizeaz o soluie optim.3. Calcularea "de jos n sus" a acestei valori.4. Construirea soluiei optime pornind de la calculele efectuate anterior.Primii trei pai reprezint baza programrii dinamice. Dac trebuie doar s aflm doarvaloarea soluiei optime, ultimul pas nu mai este necesar. De aceea, pentru cazul n care dorim s determinm i soluia optim poate fi nevoie de construirea unor structuri de date suplimentare.

DESCRIEREA METODEI

O problem ar putea fi rezolvat prin programare dinamic dac poate fi descompus n subprobleme asemntoare de dimensiuni mai mici i soluia optim a problemei depinde de soluiile optime ale subproblemelor sale.Dar acest lucru nu garanteaz c programarea dinamic e soluia, sunt situaii n care se poate aplica cu succes metoda Greedy sau Divide et Impera. Dac ns subproblemele nu sunt independente, ci se suprapun (Overlapping subproblems), un algoritm Divide et Impera ar duce la un timp mare de execuie, pe motiv c o aceeai subproblem se rezolv de mai multe ori.S analizm calculul coeficientului binomial

O funcie recursiv ar arta astfel:Code:int comb(int n, int k){if (k==0 || k==n) return 1;else return comb(n-1,k)+comb(n-1,k-1);}Multe din valorile comb(n,k) sunt calculate n mod repetat, ceea ce face aceast abordare neeficient. n astfel de situaii n care exist un numr relativ mic de subprobleme independente, restul suprapunndu-se, soluiile subproblemelor nu vor fi calculate dect o singur dat i vor fi reinute ntr-o structur de date intern (de obicei un tablou). n acest caz, funcia se poate scrie:Code:int c[100][100],k,n;

void comb(){for(int i=0;i