Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17
OHW: Rozdiel medzi revíziami
(Vytvorená stránka „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...“) |
|||
| Riadok 2: | Riadok 2: | ||
==A (2 body)== | ==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 | + | 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 <math>T_k = 1010^210^310^41\dots 10^k1</math>. Aká je dĺžka <math>T_k</math>? (presný vzorec). Ak označíme <math>n=|T_k|</math>, vyjadrite ''k'' ako funkciu ''n'', asymptoticky, t.j. v <math>\Theta</math> notácii. | ||
| + | |||
| + | ==B2 (2 body)== | ||
| + | Ak vezmeme dva sufixy reťazca <math>T_k</math> 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 <tt>x=0; while(Tk[i+x]==Tk[j+x]} { x++; }</tt> | ||
| + | |||
| + | ==B3 (1 bod)== | ||
Verzia zo dňa a času 14:32, 6. apríl 2016
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 
. Aká je dĺžka 
? (presný vzorec). Ak označíme 
, vyjadrite k ako funkciu n, asymptoticky, t.j. v 
notácii.
B2 (2 body)
Ak vezmeme dva sufixy reťazca 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++; }
