Vladan Majerech - NTIN067 Datové struktury 2
Last Modified: 27.5.2021
Index
odkazy, přednáška 1, přednáška 2, přednáška 3, přednáška 4, přednáška 5, přednáška 6, přednáška 7, přednáška 8, přednáška 9, přednáška 10, přednáška 11, přednáška 12
Přednášky budou probíhat přes zoom, měli byste včas dostat odkaz e-mailem. Pokud by k tomu z jakéhokoli důvodu nedošlo, kontaktujte mne mailem jmeno.prijmeni@mff.cuni.cz. Přednášky budu nahrávat, prosím připomínat, pokud bych zapomněl.
Nahrávky přednášek i tabule by měly být k dispozici v Sis dohledatelné z předmětu. Uvidím, v budoucnu se to může změnit, pokud se ukáže, že je žádoucí ukládat to jinam (zdá se že sharepoint nefunguje tak, jak by nám to vyhovovalo).
Odkazy na obdobné stránky
stránky mj, k předmětu z předchozích let
Přednáška 1
Na první přednášce jsme začali deterministické slovníky, FKS1984 randomizovaná $O(n)$ tvorba, worst case $O(1)$ dotazy, $O(n)$ paměť jsme stihli, HMP2000 randomizovaná $O(n)$ tvorba, worst case $O(1)$ dotazy, $O(n)$ paměť jsme nedokončili analýzu (té části, kterou plánujeme probrat), zbývá tedy analýza a derandomizace na slibovanou worst case $O(n\log n)$ tvorbu. Musím sebekriticky přiznat, že to co jsem vyprodukoval je zápis na tabuli, který by si každý měl sám „naformátovat“, zatímco zápis Martina Mareše z předchozích let by se dal jako zápisky rovnou tisknout. Uvidíme, zda se mi podaří v tomto ohledu polepšit, možná ta nutnost přepsání není na škodu. Dosud nalezené chyby jsou v zápisu červenou barvou.
Přednáška 2
Ukázalo se, že studenti na první přednášce daleko víc přikyvovali, než by odpovídalo pochopení látky. Na druhé přednášce bylo jen zhruba třetina studentů co na první, měl jsem pocit, že během 20 minut dokončím úvodní téma a začneme se věnovat uspořádaným množinám, ukázalo se ale, že druhou z popisovaných datových struktur nepochopil žádný účastník. Hloupá početní chyba s umocňováním logaritmů vedla ke slabšímu předpokladu na úvodní redukci velikosti univerza, každopádně tak jak to bylo podané je jasné, proč bylo těžké pochopit redukci „na trie“. Vpodstatě jsem celou druhou datovou strukturu zopakoval ještě jednou pomaleji, doplnil jsem derandomizaci (technický výpočet střední hodnoty pro daný prefix se objevil v zápiscích až po skončení hodiny).
Zbylo nám jen pár minut, tak jsem alespoň pověděl technický trik jak za cenu konstantního zpomalení a konstou znásobené velikosti potřebného prostoru umožnit pracovat s neinicializovanou pamětí (čtení vrací buď zapsanou hodnotu nebo informaci, že na adresu nebylo zapsáno). Příští hodinu budeme věnovat strukturám podporujícím operace succ a pred.
Přednáška 3
Probrali jsme van Emde Boasovské struktury, tedy reprezentace uspořádání pracující v $O(\log\log U)$ čase tedy nezávisle na velikosti množiny, ale závisle na velikosti univerza. Postupně jsme se propracovávali k méně a méně prostorově náročným preprezentacím, kde jsme se přes mírné časové zpomalení dostali ke stejné časové složitosti, nicméně nám tam přibyla nejprve amortizace u aktualizací, následně randomizace jak u aktualizací, tak u dotazů.
Podotýkám, že jsme předem pro letošek plánovali vypuštění Fusion trees, což pomocí vektorových triků na RAM umí reprezentovat uspořádané množiny efektivně v závislosti na $n$ i šířce slova $w$, tak, že s rostoucí šířkou slova klesá časová náročnost na $O(\log n/\log w)$. Zájemci si mohou dohledat v záznamech z předchozích ročníků (fusion node slouží jako uzel B stromu, kde větev kam pokračovat nacházíme v konstantní čase, navíc je B řádově $w^{(1/5)}$).
Přednáška 4
Věnovali jsme se Sleator Tarjanově dekompozici topologie lesa. Nějak se mi ztratila třetí stránka zápisu z přednášky, takže jsem ji psal po přednášce nanovo.
Přednáška 5
Věnovali jsme se analýze struktury Disjoint Find Union. Oproti předpokladům jsem se víc věnoval popisu struktury a analýzu jsem nedokončili, musíme ještě dopočítat, kolik maximálně můžeme naúčtovat dohromady všem vrcholům během historie datové struktury.
Přednáška 6
Dokončili jsme analýzu DFU a ve zbytku hodiny jsme se vrátili k Sleator Tarjanově dekompozici. Ukázali jsme si použití pro inkrementální bridge-blocky. Tam byl použit Link, ale opatrnou prací se spojováním "vrstev" bylo zajištěno, že nárůst potenciálu je možno odložit na příhodnou dobu. Spojování komponent mělo pak amortizovaný čas odpovídající logaritmu velikosti menší komponenty, což se za celou historii struktury nasčítá na O(n). Znamenalo to, že jsme potřebovali 3 struktury DFU na komponenty, na vrstvy a na bridge-blocky.
Pokud bychom měli hrany i odstraňovat, inkrementální DFU by nebylo možno použít, odpadl by argument o celkovém času spojování, takže by nám nezbylo než smířit se s logaritmem větší komponenty. V logaritmické složitosti není problém přidat i operaci Cut (odstraňující hrany z lesa (nejprve převedeme na mezicestové)).
V poseldních 10 minutách hodiny jsem předložil upoutávku k Top stromům.
Přednáška 7
Věnovali jsme se dynamizaci datových struktur (jak řešit rozšířit dynamičnost v omezeném (či nulovém) rozsahu na (inkrementální či plnou) dynamičnost). Ještě nám zbývá pár úvah jak řešit delete. Někdy jsem dostali amortizovaná, jindy worst case řešení. S datovou strukturou ve formě černé skříňky se u rozložitelných problémů dá pracovat, pohled dovnitř může přinést efektivnější řešení, ale typicky efektivnější strukturu dostaneme přímo, nikoli dynamizací.
Přednáška 8
Věnovali jsme se persistenci (verzování historie) datových struktur.
Přednáška 9
Věnovali jsme se optimálním haldám založeným na porovnávání (bez ohledu na výpadky keší). Řešili jsme jak amortizovanou, tak worst case variantu. Poměrně často jsem něco jiného říkal než chtěl říkat (podstrom menší, nikoli řád, odkazy na potenciál $\Phi_2$ místo $\Phi_1$, pole adresované řády jsem občas nazval keš). Asi až budu mít sílu, tak video doplním titulky. Neukázal jsem protipříklad, jak by se halda mohla rozpadnout pokud bychom dovolili opakování klíčů.
Přednáška 10
Nejprve jsme se věnovali Splay stromům, pak jsme se vrátili k plné persistenci a k pro ni potřebnému list order resp. list labeling. Příští středu je rektorský den.
Přednáška 11
Nejprve jsme se chvíli věnovali cache oblivious reprezenaci uspořádané množiny (nicméně jsem se zamotal v vEB/vEB layout). Pak jsme řešili prostorově nenáročné kódování slov nad obecnou abecedou, tak aby bylo možno efektivně změnit i dekódovat jedno písmeno.
Přednáška 12
Na začátku hodiny jsem rozmotal problém (vEB/vEB layout) co se týče cache oblivious reprezenrtace uspořádané množiny. Pak jsme řešili prostorově nenáročné kódování zakořeněných stromů (implicitní reprezentace stromu, nicméně pro efektivní práci je potřeba přidat pomocné struktury vedoucí pouze k úsporné reprezentaci).