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...)
dost lahke, hoci sa to sprvu nezdalo
Zkouska 6.8 2006 Hric
- Lukas Mach
- Matfyz(ák|ačka) level III
- Příspěvky: 258
- Registrován: 28. 3. 2006 17:08
- Typ studia: Informatika Bc.
- Bydliště: Praha a Kladno
- Kontaktovat uživatele:
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?
Where is my delta?
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 161
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
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...
->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!!"
- Lukas Mach
- Matfyz(ák|ačka) level III
- Příspěvky: 258
- Registrován: 28. 3. 2006 17:08
- Typ studia: Informatika Bc.
- Bydliště: Praha a Kladno
- Kontaktovat uživatele:
Hm, disjunktni jsem je nemel (nevim, jak by to pomohlo...)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,
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.
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,{}).Myshaak píše:ale v podstate je to sumafuk... )
For every epsilon, there is delta.
Where is my delta?
Where is my delta?