Unelte utilizator

Unelte site


laboratoare:laborator-11

Aceasta e o versiune anterioară a paginii.


Laborator 11: Programare dinamică


1 Obiectivele laboratorului

  • Înțelegerea noțiunilor de bază legate de programarea dinamică
  • Însușirea abilităților de implementare a algoritmilor bazați pe programarea dinamică
  • Înțelegerea aplicabilității practice a programării dinamice în:
    • Genetică (sequence alignment)
    • Teoria grafurilor (algoritmul Floyd-Warshall)
    • Limbaje formale și automate (algoritmul Cocke-Younger-Kasami,care analizează dacă și în ce fel un șir poate fi generat de o gramatică independentă de context)
    • Implementarea bazelor de date (algoritmul Selinger pentru optimizarea interogării relaționale)


2 Programare dinamică

2.1 Prezentare generală

Programarea dinamică presupune rezolvarea unei probleme prin descompunea ei în subprobleme și rezolvarea acestora. Spre deosebire de divide et impera, subprogramele nu sunt disjuncte, ci se suprapun.

Pentru a evita recalcularea porțiunilor care se suprapun, rezolvarea se face pornind de la cele mai mici subprograme și folosindu-ne de rezultatul acestora calculăm subproblema imediat mai mare. Cele mai mici subprobleme sunt numite subprobleme unitare, acestea putând fi rezolvate într-o complexitate constantă, ex:cea mai mare secvență dintr-o mulțime de un singur element.

2.2 Implementare

Pași ce trebuie urmați:
  1. Identificarea structurii și a matricilor utilizare în caracterizarea soluției optime
  2. Determinarea unei metode de calcul recursiv pentru a afla valoarea fiecărei subprobleme
  3. Calcularea „bottom-up“ a acestei valori (de la subprogramele cele mai mici la cele mai mari)
  4. Reconstrucția soluției optime pornind de la rezultatele obținute anterior

2.3 Probleme tip rezolvate cu acest algoritm

2.3.1 Problema rucsacului

laboratoare/laborator-11.1487190430.txt.gz · Ultima modificare: 2017/02/15 22:27 de către sebastian.cancel