Vladan Majerech - NTIN067 Datové struktury 2

Last Modified: 19.5.2023

Valid HTML 4.01 Strict

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ášky 9 a 10, přednáška 11,

Přednášky budu nahrávat, prosím připomínat, pokud bych zapomněl.


Odkazy na obdobné stránky

stránky mj, k předmětu z předchozích let, moje předloňské přednášky


Přednáška 1

Statické slovníky - nejprve jsme si ukázali metodu derandomizace na základě kriteriální funkce ... randomizovanou typicky se zhoršující konstantou 2 (jak v kriterální funkci tak v čase) a deterministickou nezhoršující kriteriální funkci, ale vyžadující volbu parametrů po bitech a vyhodnocování střední hodnoty zohledňující zafixované bity časová složitost je násobena počtem volených bitů (základem je výpočet střední hodnoty kriteriální funkce).

Následně jsme probrali FKS1984 perfektní hašování s indirekcí. Stačil nám k tomu c-univerzální hešovací systém. A $n$ prvkovou množinu jsme bezkonfliktně zahešovali do tabulky velikosti $O(n)$ randomizovaně v čase $O(n)$, s tím, že hešovací funkci spočteme v $O(1)$ s nejvýš dvěma výpadky keší. Dvoustupňová hešovací funkce bude mít $O(n)$ parametrů. Vzhledem k bezkoliznosti je čtení v $O(1)$ worst case.

Pak jsme začali HMP2000 cestu k worst case času $O(n\log n)$ tvorby bezkonfliktní hašovací funkce metodou postupného zvětšování univerza.
Pro univerzum velikosti $2^{\log n+O(1)}$ je identita vyhovující hešovací funkcí.
Dalším krokem bylo rozšíření na univerzum velikosti $2^{2\log n+O(1)}$. Ukázali jsme si, jak čtverec rozměrů $cn\times cn$, $c>2$ s libovolnými $n$ hodnotami, kde rozměr je mocninou dvojky můžeme xorováním řádků s nově volenými konstantami setřást tak, aby počet sloupcových konfliků klesl na $n/2$. Stejná metoda po transponování vedla k tomu, že z $n/2$ řádkových konfliktů jsme získali sloupcově bezkonfliktní zobrazení. To je výsledná hešovací funkce. Důkaz nebyl náročný, ale byl technický a po povídání o implementaci (výpočet střední hodnoty se zafixovaným prefixem xorované hodnoty v $O(n_i)$ a aktualizace po volbě celé xorované hodnoty stojí $O(bn_i)$, kde $b\in O(\log n)$ je počet bitů rozměru čtverce) nám do konce hodiny zbylo jen 5 minut, takže jsme další rozšiřování univerza nechali na příště.


Přednáška 2

Dokončili jsme statické slovníky, nejdříve jsme rozšířili univerza na polynomiálně velká, pak jsme řešili nepatrně větší univerza, se známou maskou na polynomiálně mnoho možností rozlišující prvky množiny $S$. Pak jsme ukázali, jak je možno setřepat maskované bity do délky $\log^3 |S|$, tedy jek se trefovat do nepatrně většího než polynomiáního univerza s maskou. Dále jsme naznačili, jak masku najít na základě samoopravného kódu nad čtyřnásobně prodlouženým slovem. Nevýhoda je, že neznáme vhodný samoopravný kód. Takový samoopravný kód je nezávislý na $S$, můžeme si jej tedy předpočítat. Popsaný randomizovaný algoritmus má ale takovou složitost, že bychom se během životnosti počítače výsledku nejspíš nedočkali. Dobrat se k vhodnému samoopravnému kódu jinou matematickou cestou bude nejspíš efektivnější.


Přednáška 3

Věnovali jsme se (dynamickým) uspořádaným množinám, tedy množinám s podporou operace succ a pred (i pro prvky nepatřící do množiny). Cílem bylo dosáhnout časů $\Theta(\log w)$ při práci nad univerzem velikosti $2^w$ vEB1975. Zvládli jsme to nakonec (randomizovaně amortizovaně) v prostoru $\Theta(n)$, kde $n$ je velikost reprezentované množiny W1983, W1984.

Na konci hodiny jsme začali povídat o strukrukturách podporujících práci nad lesy okolnostmi určené topologie.


Přednáška 4

Věnovali jsme se dále srukturám na reprezentaci topologie lesa, od Sleator Tarjanových dekompozic (Dinic, hranová dvousouvislost s backtrackingem) přes Eulerovské procházky (Henzinger, King) po Top stromy (Thorup, Holm, Lichtenberg, Alstrup).


Přednáška 5

Věnovali jsme se dynamizaci datových struktur (přehešovávání, BB-$\alpha$ ... částečná dynamizace integrovaná do principu struktury, dynamizace černých skříněk implementujících rozložitelný zobecněný vyhedávací problém). Dynamizace byla semidynamizace (jen inserty), kde jsem předvedl jak amortizovanou, tak worst-case verzi. Pro úplnou dynamizaci (včetně delete), jsem pro případ možného kaňkování naznačil amorizovanou verzi. Query se dynamizací $\log$ krát zpomalilo.

Na konci přednášky jsem udělal motivaci k persistenci, předvedli jsme funkcionální techniku i techniku tlustých vrcholů. Příště budeme řešit problémy linearizace čísel verzí plné persistence a redukci overheadu způsobeného implementací tlustých vrcholů.


Přednáška 6

Dokončili jsme persistenci (list order) a $O(1)$ amortizované udržování plně či čásečně persistentní struktury za podmínky konstantního (in resp. celkového) stupně.


Přednáška 7

Věnovali jsme se analýze Disjoint Find Union a minimálně splay stromům (kompetitivní srovnání se statickými stromy).


Přednáška 8

Věnovali jsme se DecreaseKey haldám.


Přednášky 9 a 10

Naznačil jsem trik, jak pomocí ordered file maintainance dosáhnout cache oblivious reprezentaci vyhledávacích stromů. Využijeme podstrom úplného binárního stromu reprezentovaného ve van Emde Boas pořadí. S tím, že aktualizace diktujeme pomocí file ordered maintainance, kde máme v listech logaritmicky velké keše, v nichž pracujeme sekvenčně. Díky keším je frekvence aktualizací nad nimi zredukována tak, že stíháme aktualizace uamortizovat.

Hlavně jsme se věnovali kompaktním, úsporným a implicitním datovým strukturám. (Dělení dle prostoru navíc oproti teoretickému minimu $m$ na zákaldě množství prvků univerza. Implicitní $O(1)$, úsporné $o(m)$, kompaktní $O(m)$). Ukázali jsme si jak zakódovat řetězec nad abecedou $\Sigma$ ne nutně mocninou 2, tak, aby na vlastní data stačilo implicitně mnoho informace a byli jsme teoreticky schopni pracovat s řetězcem lokálně (lokální čtení/přepisování, nikoli vkládání). Bohužel k tomu, abychom tyto operace byli schopni provádět, si potřebujeme udržovat parametry pro „mixéry“ dobrá zpráva je, že stromovým trikem pro normalizaci mixérů jsme schopni zajistit, aby stačilo pamatovat si $O(\log m)$ informací, místo přirozených $\Theta(m)$. Takže celkem dostáváme úspornou reprezentaci, místo přirozené kompaktní.

Ukázali jsme si, jak zakódovat tvary stromů pomocí bitově zakódovaných průchodů do šířky resp. do hloubky. Vlastní reprezenace byly implicitní, ale pokud chceme umožnit nějaké smysluplné přístupy  prvkům stromu, potřebujeme příslušné řetězce předzpracovat. Nejzákladnější nutnou operací jsou zjištění počtu jedniček v nějakém prefixu reprezentace resp. opačně určení polohy pořadím dané jedničky. Indirekcí se nám podařilo srazit velikost pomocných informací do šetrných mezí. (Nemusíme si všechna čísla pamatovat pomocí $log n$ bitů, stačí si data pro podůseky délky $n'$ pamatovat $\log n'$ bitů a velmi krátké úseky se nevyplatí předzpracovávat vůbec resp. celou bitovou informací je možno adresovat nezávisle spočenou charakterisiku.)


Přednášky 11

Na poslední přednášce jsme se věnovali použití datových struktur menších než je teoretické minimum. Bavili jsme se o „proudových algoritmech“, tedy o zpracovávání obrovského množství dat s relativně velmi omezenou pamětí. Jeden průchod sloužil k vytvoření kandidátů na vítěze, ale pro potvrzení bychom potřebovali konrolní půchod daty. Řešili jsme problémy majoritních prvků, odhadované četnosti prvků a odhadovaný počet prvků. (Pro odhady se hodily (nezávislé) hešovací funkce, v jednom případě k adresaci tabulek s jednostrannou chybou...)