Zkouska 6.8 2006 Hric

Pisomka:

1a zasifrovanie c 6 v RSA pri p=3,q=11,e=3 + desifrovanie
1b kolko je moznosti pre e okrem e=1?

2 dokazte asociativitu + neplatnost komutativity bool x bool operatoru strieska, ak plati (q1,p1)strieska(q2,p2)=(q1 v (p1 + q2),p1+p2)

3,pocet nenasytenych prevedeni v golbergovom algoritme + dokaz

4,prevod problemu dvojitych nespojitych mnozin na kliku. PDNM - mame grafy G1,G2, cislo k, odpoved je ano, pokial v grafoch existuje nespojita mnozina velikosti k. ( alebo tak nejak...:P)

dost lahke, hoci sa to sprvu nezdalo :)

Jen dodam, ze podle vseho byly ty grafy G1 = (V, E1), G2 = (V, E2), tj. meli spolecnou mnozinu vrcholu. V zadani to sice nebylo, ale v opacnem pripade by to bylo divne nebo trivialni (podle uhlu pohledu). Alespon jsem to teda predpokladal a chybu jsem tam nemel.

A ja zas jen upresnim: u 4) se melo ukazat, ze je problem Dvojitych nezavislych mnozin NP. (pomoci Kliky) -> tzn. mel se ukazat prevod z Kliky na DNM ;)

->Lukas: Zajimavy, to me nenapadlo. A tos mel ty E1 a E2 disjunktni?? Ja normalne bral G1 a G2 jako uplne jiny grafy, ale v podstate je to sumafuk... :))

K ustnimu: postoupilo odhadem neco kolem 2/3 lidi, otazky:
korektnost Aho-C. alg
naky dukaz k Dinicovi
aprox. alg. pro obchodniho cestujiciho, kde plati trojuhel. !=
dukaz neexistence polynomialniho aprox. alg. pro obecny prob. obch. cestujiciho

...vyhlaseni vitezu bylo v 13:00, rozdal pisemky a kazdemu pridelil 1 otazku. Casu na pripravu je hoooodne. Ja jsem sel jako paty a to az v pul treti. Hric byl uplne v pohode, z pisemky 19/20, dukaz jsem mel, on si to precetl, neco se zeptal no a asi pro peti minutach "dajte mi index"
Hurray!! :)) Uz jen analyza...

Myshaak wrote:Zajimavy, to me nenapadlo. A tos mel ty E1 a E2 disjunktni?? Ja normalne bral G1 a G2 jako uplne jiny grafy,

Hm, disjunktni jsem je nemel (nevim, jak by to pomohlo...)

Ja myslel, ze ta mnozina M mela byt nezavisla v obou tech grafech. A tim padem je nutne, aby M < V1, M < V2 (jinak to neni ani dobre definovane). Ale jestli to tam nebylo a melo se najit mnoziny M1 < V1, M1 nezavisle v G1, M2 < V2, M2 nezavisle v G2, tak by se DNM dalo resit tak, ze clovek dvakrat spusti normalni NM, coz je tak nudny problem, ze si to ani nezaslouzi vlastni nazev.

Myshaak wrote:ale v podstate je to sumafuk... :))

To je vlastne pravda... kdyz clovek chce prevest hledani NM v G na hledani DNM v grafech G1,G2 , tak at uz to bylo definovane jakkoliv, stejne zvoli G1=G, G2=(V1,{}).