zkouska 10.2.2006

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.

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)

dekuji, opraveno :-) btw a mam to ;-)

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

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

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.

Teda já se zapomněl přihlásit a navíc zkomolil Tutchkovi jméno, za což se hluboce omlouvám jeho papučím.

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) )

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. 5d = 5192 = 960

a potom korigujem "k" tak, aby sa to rovnalo :roll:

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. 5d = 5192 = 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 :(

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.... :)