# Zkouska 6.8 2006 Hric

<{ForumPost(poster="peva", timestamp=2007-02-08 15:47:37)}>
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 :)
<{/ForumPost}>

<{ForumPost(poster="Lukas Mach", timestamp=2007-02-08 18:03:28)}>
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.
<{/ForumPost}>

<{ForumPost(poster="Myshaak", timestamp=2007-02-08 20:51:11)}>
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...
<{/ForumPost}>

<{ForumPost(poster="Lukas Mach", timestamp=2007-02-09 00:00:36)}>

 > 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,{}).
<{/ForumPost}>