Analiza Algoritmilor · 2011 · Restanțe
- Profesor
- Andrei Mogos
- Anul examenului
- 2011
- Sesiune
- Restanțe
- Serie
- CC
- Adăugat
- 21 septembrie 2011 de Bogdan Ivanov
1. Sa se demonstreze ca daca exista o functie recursiva f:A->N, A inclus in N <=> exista un generator al lui A -> 1,5 p
2. Faceti o comparatie intre metoda analizei de ansamblu si metoda creditelor -> 1,5 p
3. Stabiliti daca relatia < peste multimea N intersectat cu [15,infinit) este bine formata. -> 1p
4. Demonstrati ca daca G (graf neorientat) are o k-clica atunci G barat (complementul lui G) are o (n-k)-acoperire. -> 1p
5. Sa se defineasca factorul de aproximare delta pentru o problema de aproximare: a) de minimizare; b) de maximizare. -> 1p
6. Se da: T(n)=k1, daca n=1 sau 7*T([n/5]) + k2*n, daca n>1. Sa se rezolve relatia de recurenta cu metoda substitutiei(asa cum e facuta la curs la laborator). -> 1,5p: 7. Sa se stabileasca daca problema k-SetCover este in NP. -> 1,5p (enuntu l-a dat complet, e exact acelasi enunt ca si in subiectele date in sesiunea trecuta).
Timp de lucru: 100 min.
2. Faceti o comparatie intre metoda analizei de ansamblu si metoda creditelor -> 1,5 p
3. Stabiliti daca relatia < peste multimea N intersectat cu [15,infinit) este bine formata. -> 1p
4. Demonstrati ca daca G (graf neorientat) are o k-clica atunci G barat (complementul lui G) are o (n-k)-acoperire. -> 1p
5. Sa se defineasca factorul de aproximare delta pentru o problema de aproximare: a) de minimizare; b) de maximizare. -> 1p
6. Se da: T(n)=k1, daca n=1 sau 7*T([n/5]) + k2*n, daca n>1. Sa se rezolve relatia de recurenta cu metoda substitutiei(asa cum e facuta la curs la laborator). -> 1,5p: 7. Sa se stabileasca daca problema k-SetCover este in NP. -> 1,5p (enuntu l-a dat complet, e exact acelasi enunt ca si in subiectele date in sesiunea trecuta).
Timp de lucru: 100 min.