Zkouska 6.8 2006 Hric

Uživatelský avatar
peva
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 25. 1. 2006 20:21
Typ studia: Informatika Bc.

Zkouska 6.8 2006 Hric

Příspěvek od peva »

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 :)
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

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.
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Příspěvek od Myshaak »

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...
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

Myshaak píše: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 píše: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,{}).
For every epsilon, there is delta.
Where is my delta?
Odpovědět

Zpět na „2006“