Nepovinná DÚ

Nepovinné domáce úlohy môžete použiť na získanie bodov za aktivitu aj mimo prednášky. V rámci semestra bude ešte aspoň jedna ďalšia séria úloh, ale nespoliehajte sa na to, že ich ešte bude veľa. Celkovo máte v hodnotení za body za aktivitu 10 bodov a môžete získať ďalších 10 ako bonus.

Riešenia úloh odovzdajte v písomne forme na prednáške do termínu odovzdania. Maximálny počet bodov je orientačný, ak sa úloha ukáže náročnejšia, než sa očakávalo, môže byť zvýšený. O úlohách sa môžete rozprávať, ale nepíšte si z takýchto rozhovorov poznámky a napíšte text vlastnými slovami. Pri väčšine úloh preferujem vaše vlastné riešenie, ale ak riešenie nájdete v literatúre, uveďte zdroj a napíšte riešenie vlastnými slovami. Všetky odpovede zdôvodnite.

Neskôr v semestri môže byť zverejnená aj ďalšia séria úloh, ale nespoliehajte sa, že tých sérií bude veľmi veľa.

Séria 1, odovzdať do 14.3.

Úloha 1 (max 2 body)

V štruktúre RRR sme rozdelili reťazec na bloky dĺžky t2 a každému sme v komprimovanom poli B priradili kód, pričom bloky s veľmi málo alebo veľmi veľa jednotkami mali kratšie kódy ako bloky, v ktorých bol počet jednotiek a núl probližne rovnaký. Namiesto tohto spôsobu môžeme použiť nasledovný spôsob kompresie bitového reťazca. Pre každý z $2^{{t_{2}}}$ typov bloku spočítame počet výskytov, t.j. koľko blokov nášho reťazca má tento typ. Potom typy blokov zoradíme podľa počtu výskytov a pripradíme im kódy tak, že najčastejšie sa vyskytujúci typ bloku dostane ako kód prázdny reťazec, druhé dva najčastejšie sa vyskytujúce typy blokov dostanú kódy 0 a 1, ďalšie štyri typy dostanú kódy 00, 01, 10 a 11, ďalších 8 tyov dostane kódy dĺžky 3 atď.

Popíšte ako k takto komprimovanému reťazcu zostavíme všetky ďalšie potrebné polia na to, aby sme mohli počítať rank v čase O(1). Veľkosť vašej štruktúry by mala byť m+o(n), kde n je dĺžka pôvodného binárneho reťazca a m dĺžka jeho komprimovanej verzie. Vaša štruktúra sa asi bude podobať na štruktúru RRR z prednášky, ale popíšte ju tak, aby text bol zrozumiteľný pre čitateľa, ktorý RRR štruktúru nepozná, pozná však štruktúru pre pre nekomprimovaný rank.

Úloha 2 (max 2 body)

Označme B1 komprimovaný reťazec z úlohy 1, t.j zreťazenie kódov pre jednotlivé bloky. Označme B2 komprimovaný reťazec z prednášky o dátovej štruktúre RRR, t.j. zreťazenie odtlačkov (signature) pre jednotlivé bloky. Nájdite príklad, kedy je B2 kratší ako B1 a naopak príklad, pre ktorý je B1 oveľa kratší ako B2.

Poznámka: B1 ani B2 neobsahujú dosť informácie, aby sa z nich samotných dal spätne rekonštruovať pôvodný binárny reťazec, lebo nepoužíme bezprefixový kód. Huffmanovo kódovanie je bezprefixový kód, lebo kód žiadneho znaku nie je prefixom kódu iného znaku.

Ak bonus za ďalšie body sa pokúste navrhnúť schému, v ktorej bude komprimovaný reťazec vždy kratší ako B2, ale ktorá búde spĺňať to, žo okrem nej potrebujeme len $\lg t_{2}+O(1)$ prídavnej informácie pre každý blok na to, aby sme vedeli spätne určiť pôvodný reťazec.

Úloha 3 (max 4 body)

V prednáške je uvedené bez dôkazu, že ak chceme počítať rank nad väčšou abecedou, môžeme namiesto wavelet tree použiť RRR štruktúru pre indikátorové bitové vektory jednotlivých znakov abecedy a že výsledná štruktúra bude mať veľkosť $nH(T)+O(n)+o(\sigma n)$. Dokážte toto tvrdenie. V tejto úlohe ocením aj vami spísaný dôkaz naštudovaný z literatúry s uvedením zdroja. Ako počiatočný zdroj môžete použiť prehľadový článok Navarro, Mäkinen (2007) Compressed full-text indexes [1] (strana 30).

Úloha 4 (max 3 body)

Uvažujme verziu štruktúry vector, ktorá používa ako parametre tri reálne konštanty A,B,C>1. Ak pridávame prvok a v poli už nie je miesto, zväčšíme veľkosť poľa z s na A*s. Naopak, ak zmažeme prvok a počet prvkov klesne pod s/B, zmenšíme pole na s/C. V knihe Cormen, Leiserson, Rivest and Stein Introduction to Algorithms (kap. 17 v druhom vydaní) nájdete analýzu pre A=2, B=4 a C=2. Nájdite množinu hodnôt parametrov A,B,C, ktoré pridávanie aj uberanie prvkov funguje amortizovane v čase O(1).

Nemusíte charakterizovať všetky trojice parametrov, pre ktoré je amortizovaný čas konštantný, ale nájdite nejakú množinu trojíc, pre ktoré je to pravda. Ideálne každému parametru povolíte hodnoty z nejakého intervalu, ktorý môže byť ohraničený konštantami alebo funkciou iných parametrov. Zjavne napríklad musí platiť, že B>C.