Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17

Úvod · Pravidlá · Prednášky · Prezentácia · Ako poznámkovať · Moodle
Táto stránka sa týka školského roku 2016/17. V školskom roku 2017/18 predmet vyučuje Jakub Kováč, stránku predmetu je https://people.ksp.sk/~kuko/ds


OHW

Z VPDS
Prejsť na: navigácia, hľadanie

Nepovinná domáca úloha

A (2 body)

Uvažujme Morissov-Prattov algoritmus pre vzorku P dĺžky m, ktorý bežíme na veľmi dlhom texte T. Koľko najviac bude trvať spracovanie úseku dĺžky k niekde uprostred textu T ako funkcia parametrov m a k? Hodnota k môže byť menšia alebo väčšia ako m. Uveďte asymptotický horný aj dolný odhad, t.j aj príklad, kde to bude trvať čo najdlhšie (príklad by mal fungovať pre všeobecné m a k, ale môžete si zvoliť T a P a aj ktorý úsek T dĺžky k uvažujete).

B1 (1 bod)

V nasledujúcej sérii podpríkladov sa vrátime k binárnemu reťazcu, o ktorom sme sa bavili, že má veľký lexikografický strom všetkých sufixov. Postupne to podrobnejšie ukážeme. Uvažujme reťazec tvaru T_{k}=1010^{2}10^{3}10^{4}1\dots 10^{k}1. Aká je dĺžka T_{k}? (presný vzorec). Ak označíme n=|T_{k}|, vyjadrite k ako funkciu n, asymptoticky, t.j. v \Theta notácii.

B2 (2 body)

Ak vezmeme dva sufixy reťazca T_{k} a začneme ich porovnávať od začiatku, ako dlho bude v najhoršom prípade trvať, kým nájdeme prvý rozdiel? Vyjadrite asymptoticky ako funkciu n, horný aj dolný odhad.

Poznámka: pýtame sa na časovú zložitosť cyklu x=0; while(Tk[i+x]==Tk[j+x]} { x++; }

B3 (1 bod)