Analiza Algoritmilor · 2012 · Sesiune
- Profesor
- Cristian Giumale
- Anul examenului
- 2012
- Sesiune
- Sesiune
- Serie
- CA
- Grupă
- 323
- Adăugat
- 4 februarie 2012 de Laurentiu-Ionut Tuca
Am avut urmatoarele subiecte:
Teorie:
1.Daca o este sau nu reflexiva? ATENTIE ca au confundat multi simetria cu reflexivitatea,inclusiv eu.O relatie e reflexiva daca orice element e in relatie cu el insusi
2.Daca multimea multimilor formate cu elemente din {0,1} are proprietatea ca relatia de incluziune stricta este bine formata.Rasp era DA,deoarece are un cel mai mic element(multimea vida).
3.O stiva cu operatii elementare,sa ziceti de ce alegerea unei functii de potential constante era corecta.
4.Se da un algoritm Test(parametrii) {...} sa ziceti care este complexitatea spatiala a lui .Faza e ca in corpul functiei nu apareau decat parametrii lui test,deci complexitatea spatiala era O(1) care il puteam incadra in LOGSPACE.
5.Un arbore cu inaltime infinita , o prop decidabila si stim ca multimea nodurilor din arbore cu prop aia este finita.Sa spunem daca e sau nu decidabila.
Probleme
1.inductie structurala clasica care iesea destul de repede
2.Se dadea o prob Q de optimizare NP-dura,pt care exista un algoritm de aprox AlgQ cu factorul 2.Prob Q se zicea ca se poate rezolva tot printr-o prob de optimizare NP-dura,H cu factorul 2/3.Sa se det probabilitatea a nu stiu ce,si sa se schiteze un algoritm pt asta in pseudocod. Rasp era ca AlgH nu exista deoarece nu poti construi in algo de aprox cu factor subunitar,deci cerinta era doar ca sa te incurce.
Teorie:
1.Daca o este sau nu reflexiva? ATENTIE ca au confundat multi simetria cu reflexivitatea,inclusiv eu.O relatie e reflexiva daca orice element e in relatie cu el insusi
2.Daca multimea multimilor formate cu elemente din {0,1} are proprietatea ca relatia de incluziune stricta este bine formata.Rasp era DA,deoarece are un cel mai mic element(multimea vida).
3.O stiva cu operatii elementare,sa ziceti de ce alegerea unei functii de potential constante era corecta.
4.Se da un algoritm Test(parametrii) {...} sa ziceti care este complexitatea spatiala a lui .Faza e ca in corpul functiei nu apareau decat parametrii lui test,deci complexitatea spatiala era O(1) care il puteam incadra in LOGSPACE.
5.Un arbore cu inaltime infinita , o prop decidabila si stim ca multimea nodurilor din arbore cu prop aia este finita.Sa spunem daca e sau nu decidabila.
Probleme
1.inductie structurala clasica care iesea destul de repede
2.Se dadea o prob Q de optimizare NP-dura,pt care exista un algoritm de aprox AlgQ cu factorul 2.Prob Q se zicea ca se poate rezolva tot printr-o prob de optimizare NP-dura,H cu factorul 2/3.Sa se det probabilitatea a nu stiu ce,si sa se schiteze un algoritm pt asta in pseudocod. Rasp era ca AlgH nu exista deoarece nu poti construi in algo de aprox cu factor subunitar,deci cerinta era doar ca sa te incurce.