Programare dinamică

Referat
7/10 (1 vot)
Conține 1 fișier: doc
Pagini : 11 în total
Cuvinte : 4108
Mărime: 20.05KB (arhivat)
Publicat de: Mirela M.
Puncte necesare: 7
Profesor îndrumător / Prezentat Profesorului: Ion Popescu
despre programare dinamica

Extras din referat

Programarea dinamica face parte dintr-o categorie de metode matematice numite metode de scufundare.O problemã de programare dinamicã contine subprobleme comune (care nu sunt independente) din a cãror rezolvare si combinare se obtine solutia unei (sub)probleme mai mari.Deci rezolvarea unei (sub)probleme se poate face doar dupã solutionarea (sub)problemelor, care alcãtuiesc problema respectivã.Spunem cã programarea dinamica actioneaza de jos in sus,prelucrând si combinând subcazuri mici,obtinând astfel solutia pentru subcazuri tot mai mari.

Totodatã programarea dinamicã evitã rezolvarea de mai multor ori a aceleiasi subprobleme(rezolvându-se doar problemele independente ),prin memorarea rezultatelor partiale.

Sã presupunem cã avem de rezolvat urmãtoarea problemã :

Sã se calculeze valoarea C(n,k)(combinãri de n luate câte k).

Folosim functia recursivã :

function comb(n,k;integer):integer;

begin

if (k=0)or (k=n)then comb:=1

else comb:=comb(n-1,k-1)+comb(n-1,k)

end;

Din punct de vedere al timpului de executie aceastã metodã este ineficientã ,deoarece sunt calculate se mai multe ori aceleasi valori .

Vom elimina acest dezavantaj prin evitarea recursivitatii,pãstrând într-un tabel rezultatele intermediare si luându-le de acolo ori de câte ori este necesar.Argumentele functiei ne sugereazã forma tabelului(folosindu-le ca indice de linie,respectiv coloanã),iar formula ne precizezã modul de completare al tabelului:

1, I=jÚj=0

C(I,j)=

C(I-1,j-1)+c(I-1,j) 0<j<I

Pentru exemplul precedent avem:

Function comb(n,k;integer):integer;

Var i,j:integer;

c:array[0..20,0..20]of integer;

begin

for i:=0 to n do

begin c[i,0]:=1;

c[i,1]:=1;

for j:=1 to i-1 do

c[i,j]:=c[i-1,j-1]+c[i-1,j];

end;

comb:=c[n,k];

end;

Orice algoritm de programare dinamicã poate fi descris prin urmãtorii pasi:

1)Caracterizarea structurii unei solutii optime:se defineste un vector,o matrice ,...,în care fiecare componentã va contine o solutie optimã a unei subprobleme.

2)Definirea recursivã a valorii unei solutii optime .Totodatã se defineste valoarea celei mai mici subprobleme(celor mai mici subprobleme).

Ex: c[i,0]:=1;

c[i,1]:=1;

3)Calcularea de jos în sus a valorii unei solutii optime ,tinând seama de definirea recursivã a acestei valori.

4)Dacã pe lângã valoare se mai doreste afisarea solutiei care a generat rezultatul optim ,atunci se construieste de sus în jos solutia propriu-zisã.

Preview document

Programare dinamică - Pagina 1
Programare dinamică - Pagina 2
Programare dinamică - Pagina 3
Programare dinamică - Pagina 4
Programare dinamică - Pagina 5
Programare dinamică - Pagina 6
Programare dinamică - Pagina 7
Programare dinamică - Pagina 8
Programare dinamică - Pagina 9
Programare dinamică - Pagina 10
Programare dinamică - Pagina 11
Programare dinamică - Pagina 12
Programare dinamică - Pagina 13
Programare dinamică - Pagina 14
Programare dinamică - Pagina 15
Programare dinamică - Pagina 16
Programare dinamică - Pagina 17
Programare dinamică - Pagina 18
Programare dinamică - Pagina 19
Programare dinamică - Pagina 20
Programare dinamică - Pagina 21
Programare dinamică - Pagina 22
Programare dinamică - Pagina 23

Conținut arhivă zip

  • Programare Dinamica.DOC

Alții au mai descărcat și

Sortări în structuri de date

Metodele de sortare cele mai des folosite pot fi clasificate în doua categorii: METODE DIRECTE si METODE AVANSATE. METODELE DIRECTE se bazeazã...

Structuri de Date și Algoritmi

Arbori Binari Optimi Despre arbori binari optimi putem vorbi atunci cand, pentru fiecare dintre cheile unui arbore binar ordonat cunoastem...

Hackeri

Hackerii sunt pasionati ai informaticii, care, de obicei au ca scop „spargerea” anumitor coduri, baze de date, pagini web etc. Ei sunt considerati...

Te-ar putea interesa și

Teoria și Practica Riscului în Banca Comercială

ÎNTRODUCERE Actualitatea temei de cercetare şi gradul de studiere a acesteia Actualitatea temei de cercetare În anii 90 ai secolului trecut, în...

Abordarea Sistemelor Energocibernetice în Concepție Arhemică în Vederea Creșterii Eficienței Investițiilor

Data fiind importanta strategica a Sectorului Energetic National în dezvoltarea pe baze durabile a economiei românesti, evolutia acestuia trebuie...

Validarea datelor de intrare și manipularea erorilor în programarea web

INTRODUCERE Într-o epocă modernă ca aceasta în care se poate rezolva totul cu ajutorul internetului printr-un simplu ”click” - o singură apăsare a...

Site Web Dinamic-Educational Sportiv

INTRODUCERE Utilizarea unui serviciu de un tip oarecare in Internet implica prezenta a doi parteneri hardware (calculatoare ) care comunica: •...

Marketing Direct

1.Metode de culegere si prelucrare a datelor Toate adaptarile modelarii matematice la fenomenele economice concrete au la baza o conceptie mai...

Structuri de Date și Algoritmi

1. Conceptul de dată În informatică, prin dată, se desemnează un model de reprezentare a informaţiei, model cu care se poate opera pentru a obţine...

Structuri de Date și Alogoritmi

EXTENSII ALE LIMBAJULUI C++ A. Operaţii de intrare-ieşire specifice limbajului C++ I. Noţiuni teoretice Limbajul C++ furnizează o bibliotecă...

Programare dinamică

Metoda programãrii dinamice Problemã generalã Fie A si B douã multimi oarecare. Fiecãrui element x.A urmeazã sã i se asocieze o valoare v(x).B....

Ai nevoie de altceva?