Hello dragi fosti colegi de serie!

examenul de AA de azi mi s-a parut de tot kktul!!!!Subiecte naspa,la supraveheat au fost diana petrescu si andrei mogos si proful care mai pleca din cand in cand....se putea vorbi cu cel din fata/spate dar cu grija. In schimb proful a fost super de treaba si a zis k ne da la toti 1 pct in plus la nota asa de la el :) iar la cei care au fost la ultimele 4 cursuri inca 1:)
au fost 5 sub de teorie (50 pct), 1 prob de ind structurala(30 pct) si una de construit un alg nedeterminist(20 pct) :(

Intrucat sub de teorie au fost un kkt nu pot sa va reproduc decat 2 din ele(care aveau textul mai scut...k restu erau pe cateva randuri):

1. Se da relatia binara "<" peste functiile de complexitate f:N->R+ f<g =(def) cu f=o(g) (o mic). Sa se arate k nu e reflexiva.

2. Fie prob Q(G,k)=(def)"Sa se decida daca graful G are o k-clica"
 unde G=(V,E) este un graf neorientat BIPARTIT. 
Care e duritatea rez pb Q? (aici se pare k graful fiind bipartit este in P si nu in NP...asta am aflat de la prof dupa ex)



Pb de inductie structurala nu era grea trebuia sa ai grija k erau multi operatori insa nu era complicata.

PB2(cu alg nedeterminist):

Fie G1=(V1,E1) si G2=(V2,E2) 2 grafuri orientate oarecare iar Q (G1,G2) problema: 
"sa se deida daca G1 este izomorf cu G2". sa se arate k Q apartine NP.

Se dadea k G1 izomorf G2 daac si nunai 
daca |E1|=|E2| si exista f:V!->V2 cu f bijectiva ai oricare au fi (u,v) din E1 (f(u),f(v)) apartine E2.

Mie personal mi s-a parul un examen naspa...nu ne astaptam la sub astea intrucat seminaristul ne-a zis k dam analiza amortizata nu prob cu alg nedetrministi..ma rog..asta e..Notele o sa le primim la 19.30 asa k daca e ceva interesant de zis
(daca s-a picat ..etc) o sa va zicem.

Spor!