# zkouska 10.2.2006

<{ForumPost(poster="darkness", timestamp=2006-02-10 14:03:14)}>
takze zadani: Zadny aho-corasick  
  
(opraveno)  
1) posloupnost je k-setridena (kazdy prvek je nejdale k pozic od sveho rektniho umisteni), mame tridici sit sirky k s hloubkou S(k) a merge sit se sirkou 2k a hloubkou M(k)  
ukazte, ze staci tridici sit hloubky S(k) + 2M(k)  
  
2) RSA - zadana dve prvocisla p, q a dve cisla e1 a e2.  
Ukolem bylo spocitat soukromy klic, kazdy krok okomentovat a popr. rict, proc to nejde.  
(konkretni hodnoty p=17, q=13, e1=5, e2=3)  
takze pro e2 to nelze, pze cislo 16*12 je delitelne 3.  
  
3) Asi klasicky - prevod NP problemku  
Melo se dokazat, ze PSP je NP-uplny problem  
Petkovy soucet podmnoziny (PSP) je zvlastni pripad SP (soucet podmnoziny), lisi se tim, ze vsechna cisla a1,...,an,b jsou delitelna 5, ale princip je stale stejny - vybrat podmnozinu z prvku a1,...,an tak, aby soucet byl b.
<{/ForumPost}>

<{ForumPost(poster="tutchek", timestamp=2006-02-10 15:12:58)}>

 > darkness wrote:takze zadani: Zadny aho-corasick  
 >   
 > 1) dokazat neco u tridici site, nepamatuji si to presne, ale byl tam nejaky predpoklad, ze prvek je vzdalen max k pozic od sveho spravne pozice v setridene posloupnosti. (k je sirka tridici site, 2k je sirka slucovaci site)  
 > a melo se dokazat, ze to lze setridit pomoci S(k) + 2 M(k)  
 > (radsi me opravte)  
 >   
 > 2) RSA - zadana dve prvocisla p, q a dve cisla e1 a e2.  
 > Ukolem bylo spocitat soukromy klic, kazdy krok okomentovat a popr. rict, proc to nejde.  
 > (konkretni hodnoty p=17, q=13, e1=5, e2=3)  
 > takze pro e2 to nelze, pze cislo 16*12 je delitelne 3.  
 >   
 > 3) Asi klasicky - prevod NP problemku  
 > Melo se dokazat, ze PSP je NP-uplny problem  
 > Petkovy soucet podmnoziny (PSP) je zvlastni pripad SP (soucet podmnoziny), lisi se tim, ze vsechna cisla a1,...,an,b jsou delitelna 5, ale princip je stale stejny - vybrat podmnozinu z prvku a1,...,an tak, aby soucet byl b.

ad1) posloupnost je k-setridena (kazdy prvek je nejdale k pozic od sveho rektniho umisteni), mame tridici sit sirky k s hloubkou S(k) a merge sit se sirkou 2k a hloubkou M(k)  
  
ukazte, ze staci tridici sit hloubky S(k) + 2M(k)
<{/ForumPost}>

<{ForumPost(poster="darkness", timestamp=2006-02-10 16:38:46)}>
dekuji, opraveno :-) btw a mam to ;-)
<{/ForumPost}>

<{ForumPost(poster="wintermute", timestamp=2006-02-10 17:10:16)}>
Takovýhle tvrďárny tu máte, jo? To já si dneska dal u Kučery Aho-Corasicka a v pohodě.
<{/ForumPost}>

<{ForumPost(poster="tutchek", timestamp=2006-02-10 18:23:31)}>

 > wintermute wrote:Takovýhle tvrďárny tu máte, jo? To já si dneska dal u Kučery Aho-Corasicka a v pohodě.

ne, nemame tu takovy tvrdarny, to neni zkouska.. to je jen pripousteci test ke zkousce
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-02-11 08:48:01)}>
Mám to :-) Chachá...!!! Nevím, jak Tuchek, ale já spal ten den minimálně a na ústním jsem byl totálně vymaštěnej. Kdybych neměl plnej počet bodů, tak snad vyletím. Ale já to mám :-) Btw. jistá slečna řekněme Káá je zářný příklad toho, že jde dostat jedničku za 1.5 bodu.
<{/ForumPost}>

<{ForumPost(poster="random", timestamp=2006-02-11 08:49:34)}>
Teda já se zapomněl přihlásit a navíc zkomolil Tutchkovi jméno, za což se hluboce omlouvám jeho papučím.
<{/ForumPost}>

<{ForumPost(poster="qk_", timestamp=2006-02-11 16:14:18)}>
Mel bych dotaz k tomu RSA. Zkousel sem si to doma spocitat a mam problem u toho multiplikativniho inversu. Podle poznamek ma vyjit ax+ny, takovy ze ny je identicky s nulou a z ax to dostanu...no problem je ze mne vyslo ny -95 a ax 96, takze NSD je sice 1, ale nejak to nedpovida tomu co je v poznamkach. Muzete sem nekdo hodit ten vypocet inversu (mne to vyslo PuK(5,221) A PrK(2,221) )
<{/ForumPost}>

<{ForumPost(poster="nytram", timestamp=2006-02-11 16:35:11)}>

 > qk_ wrote:Mel bych dotaz k tomu RSA. Zkousel sem si to doma spocitat a mam problem u toho multiplikativniho inversu. Podle poznamek ma vyjit ax+ny, takovy ze ny je identicky s nulou a z ax to dostanu...no problem je ze mne vyslo ny -95 a ax 96, takze NSD je sice 1, ale nejak to nedpovida tomu co je v poznamkach. Muzete sem nekdo hodit ten vypocet inversu (mne to vyslo PuK(5,221) A PrK(2,221) )

mno, ja som to pocital takto:  
  
e=5;  
(p-1).(q-1) = 192;  
  
5*d = 1 + k.(p-1).(q-1)  
  
a vieme, ze 0 < d < 192  
teda max. 5*d = 5*192 = 960   
  
a potom korigujem "k" tak, aby sa to rovnalo   :roll:
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-02-11 18:13:59)}>

 > nytram wrote:
 >  > qk_ wrote:Mel bych dotaz k tomu RSA. Zkousel sem si to doma spocitat a mam problem u toho multiplikativniho inversu. Podle poznamek ma vyjit ax+ny, takovy ze ny je identicky s nulou a z ax to dostanu...no problem je ze mne vyslo ny -95 a ax 96, takze NSD je sice 1, ale nejak to nedpovida tomu co je v poznamkach. Muzete sem nekdo hodit ten vypocet inversu (mne to vyslo PuK(5,221) A PrK(2,221) )
 > 
 > 
 > mno, ja som to pocital takto:  
 >   
 > e=5;  
 > (p-1).(q-1) = 192;  
 >   
 > 5*d = 1 + k.(p-1).(q-1)  
 >   
 > a vieme, ze 0 < d < 192  
 > teda max. 5*d = 5*192 = 960   
 >   
 > a potom korigujem "k" tak, aby sa to rovnalo   :roll:

hu, takze podle tohohle je 2 dobre...192*2+1 = 385...tedy d je 77...hmmm, tak tomu opravdu nerozumim, jak k tomu dojit logicky a ne metodou pokus omyl :(
<{/ForumPost}>

<{ForumPost(poster="nytram", timestamp=2006-02-11 20:23:48)}>

 > Anonymous wrote:
 > hu, takze podle tohohle je 2 dobre...192*2+1 = 385...tedy d je 77...hmmm, tak tomu opravdu nerozumim, jak k tomu dojit logicky a ne metodou pokus omyl :(

no, metoda pokus/omyl je vhodna len pre male cisla, resp. na pisomke nebolo povedane, aby som pouzil algoritmus z prednasky, konkretne EXTENDED_EUCLID.  :twisted: Teda som si to takto "zjednodusil".  
  
Algo. E_EUCLID(a,b,d,x,y) { vopred sa ospravedlnujem za prologovsky zapis  :twisted: } ti vrati d = NSD(a,b) a "x" a "y" su koeficienty pre "d", kedze "d" mozeme zapisat ako d = ax + by.  
  
Z toho plynie: ax = d - by, kde pre pre potreby RSA je "a" = "e", "d" = 1,   
"b" = (p-1)*(q-1), "y" = "k", a "x" je ten multiplikativny inverz...aspon tak som to pochopil....snad to dava zmysel.... :)
<{/ForumPost}>