Vladan Majerech - NTIN067 Datové struktury 2
Last Modified: 28.3.2025
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áš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
Po přehledu probíraných témat a popisu používaného výpočetního modelu (zapomněl jsem zmínit konvenci, že používáme jako defaultní základ logaritmu dvojku) jsme začali řešit statické slovníky.
Po přehledu podobných struktur pro daný problém (používal jsem k popisu chování $O$, ale vhodnější by bylo $\Theta$) jsem nejprve ukázal 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 deterministické varianty 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)$ (evidentně neumím numericky počítat, pokud 4 prvky padnou na stejnou adresu, jedná se o $6={4 \choose 2}=4\cdot 3/2$ kolizí, nikoli 10 a $1={2 \choose 2}=2\cdot 1/2$ nikoli 2), s tím, že hešovací funkci spočteme v $O(1)$ s nejvýš dvěmi 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
(evidentně osvětlení tabule není příliš kompatibilní se schopnostmi kamery).
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=2^r\times 2^r$, $c>2$ s libovolnými $n$ hodnotami,
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í povede k tomu, že z $n/2$ řádkových konfliktů získáme sloupcově bezkonfliktní zobrazení, tedy cílovou hešovací funkci.
To jsme zatím neukázali.
Skončili jsme s tím, že jsme schopni vhodné konstanty volit i deterministicky po bitech tedy v celkovém worst case čase $O(n\log n)$.
Příště nás čeká důkaz bezkonfliktosti po druhém průchodu a další rozšiřování univerza.
Přednáška 2
Vše nasvědčuje tomu, že druhá přednáška byla nahrána bez zvuku:(, každopádně bez osvětlení tabule je záznam čitelný po celou dobu. Čtyři roky stará nahrávka by měla být dostupná v SIS v informacích k předmětu. Věřím tomu, že je dostupná pro studenty, kteří mají předmět zapsaný. Kdyžtak mi dejte vědět, abych ji překopíroval jinam.
Dokončil jsem případ kvadratického univerza ukázáním, že tresholdy při průchodu počínající s nejvýš $n/2$ řádkovými konflikty budou menší než 1, tedy výsledná funkce po druhé transformaci vyjde bezkonfliktní. Dostáváme z řádkového rozměru určenou konstantu $a$ kterou xorujeme sloupec, tím je určena sloupcová konstanta $a'$ kterou xorujeme řádek a tím dostaneme unikátní adresu.
Pokračoval jsem rozšířením univerza na velikost $2^{O(\log n)}$, tedy polynomiální. Takové prvky můžeme vnímat jako konstantně dlouhé řetězce nad $n$-písmenou abecedou. Pokud $n$ prvkovou množinu takových slov uložíme jako komprimované trie (kde v uzlech evidueme podle kolikátého písmenka se větvíme), tak nám stačí $n$ listů (v nichž je evidovaný klíč pro kontrolu) a nejvýš $n-1$ vnitřních vrcholů. Dohromady nejvýš $2n-2$ orientovaných hran. Hrany trie můžeme evidovat v heš tabulce pod klíčem vrchol a písmeno. To je $2\log n+O(1)$ bitů, můžeme tedy pro uložení $2n-2$ prvkové množiny hran (k určení cílového vrcholu) použít předchozí techniku hešování. Výslednou adresu pak získáme průchodem trie vyžadující vyhledání nejvýš konstantně mnoho hran. Pokud bylo univerzum velké $O(n^c)$, budeme tak číst nejvýš $3c$ krát.
Před dalším zvětšováním univerza (v zapomněnce) jsme odbočili k deterministické technice R1995 volby hešovací funkce $(ax \mod 2^b)>\!>(b-s)$ (liché $a$) v čase $O(bn^2)$ postupnou volbou $b$ bitů parametru $a$ tak abychom nepřekročili očekávaný odhad počtu konfliktů.
Dalším krokem bylo univerzum velikosti $2^{o(\sqrt n)}$, kde jsme navíc znali masku $M$ s nejvýš $O(\log n)$ nenulovými bity tak, že pokud prvky množiny $S$ transformujeme pomocí bitového and s maskou $M$, tak dostaneme množinu stejné velikosti (tedy $n$). Trik byl rozdělit masku na konstantní počet podmasek $M_0$, ... $M_{c-1}$ každou s nejvýš $\log n/4$ nenulovými bity a pro průniky $S \cap M_i$ vytvořit FKS hešování s použitím Ramanovy metody volby hešovacích funkcí. Jednotlivé množiny jsou velké $O({\root 4 \of n})$, takže na vytvoření hešovacích pro výsledné množiny potřebujeme $b{\root 4 \of n}^2\in o(n)$ času. Nejspíš nemáme čas počítat $S\cap M_i$, ale místo toho vytvoříme hešovací funkci pro množinu odpovídající všem podmaskám masky $M_i$. Výsledná adresa je pro každou takovou masku $O(1)+\log n/4$ bitová. Pokud výsledné bity adres spojíme dohromady, dostaneme $O(\log n)$ bitů, takže se pohybujeme v univerzu které již umíme perfektně hešovat. Vzhledem k tomu, že se libovolné dva prvky množiny $S$ liší po maskování maskou $M$, liší se i v maskování některou z podmasek $M_i$. Proto se spojení adres bude v části odpovídající masce $M_i$ lišit, takže je tato transformace univerza bezkonfliktní.
Následně jsme pokračovali k univerzu velikosti $2^w$, s tím, že jsme opět měli masku $M$ s nejvýš $k=O(\log n)$ nenulovými bity tak, že pokud prvky množiny $S$ transformujeme pomocí bitového and s maskou $M$, tak dostaneme množinu stejné velikosti (tedy $n$). Ukázali jsme, jak je možno nalézt $C$ a $M'$ tak, abychom pomocí $(((x \cap M) * C) >\!> w) \cap M'$ přetransformovali množinu $S$ na $n$-prvkovou množinu $k^3$ bitového univerza s maskou $M'$ s $k$ nenulovými bity. Vzhledem k tomu, že $k^3\in o(\sqrt n)$ můžeme použít předchozí techniku k dokončení konstrukce. K žádnému dalšímu čtení z paměti přitom nedochází.
V závěrečných okamžicích jsem naznačil, že s předpočítaným $\delta$-samoopravným kódem postupný (náhodný) výběr bitů do masky statisticky exponenciálně snižuje počet konfliktů. To jak se pomocí bitové aritmetiky s postupným zvětšováním přesnosti aritmetiky dá paralelně najít v $O(n\log n)$ čase nejefektivnější bit do masky jsem ani nenaznačoval. Ani jsem nenaznačil, jak existence univerzálního hešovacího systému z $w$ bitového do $4w$ univerza plyne existence $\delta$ samoopravitelného kódu. Dobrá zpráva je, že takový kód je nezávislý na reprezentované množině $S$, takže můžeme počítat s tím, že je předkompilovaný.
Přednáška 3
Video z přednášky vypadá OK.
Probírali jsme „vyhledávací stromy“ nad univerzem $2^k$ bitových čísel, tedy množinám s podporou dotazů succ a pred (i pro prvky nepatřící do množiny). Cílem bylo dosáhnout časů $\Theta(k)$ jak pro tyto dotazy, tak pro aktualizace insert/delete (i pro prvky nepatřící do množiny). Pomocí konstantního počtu takových dotazů succ/pred jsme schopni zjistit, zda daný prvek patří do reprezentované množiny (a dostat na něj odkaz). Všechny probírané reprezentace navíc podporovaly vyhledání minima a maxima reprezentované množiny v konstantním čase, což by šlo použít na snížení počtu potřebných dotazů succ/pred při vyhledávání daného prvku.
Začali jsme strukturou B1975, která worst case dosahovala $\Theta(k)$ časy, ale vyžadovala souvislý úsek paměti velikosti $\Theta(2^{2^k})$. (Při popisu succ(x) jsem nezvažoval případ prázdné množiny, kde je samozřejmě odpověď „prázdná množina“.) Pokračovali jsme strukturami W1993, první dosahovala $\Theta(k)$ pro succ/pred, ale aktualizace vyžadovaly $\Theta(2^k)$ času a struktura stále vyžadovala úsek paměti velikosti $\Theta(2^{2^k})$. První transformace (indirekce) vedla k amortizovanému času aktualizací $\Theta(k)$, ale neřešila problém s pamětí. (Když jsem říkal jak často budeme muset provádět aktualizaci indikátorového stromu, říkal jsem jednou za $O(2^k)$ aktualizací. Samozřejmě to mělo být jednou za $\Omega(2^k)$ aktualizací.) Druhá transformace (x-fast) (univerzální hešování potřebné části stromu) veda k tomu, že i pred/succ dotazy přestaly být worst case, ale staly se randomizovaně $\Theta(k)$, čas aktualizací se změnil na amortizovaně randomizovaný $\Theta(2^k)$. Velikost potřebné paměti ale klesla na $\Theta(n2^k)$, kde $n$ je velikost reprezentované množiny. Kombinace těchto dvou transformací (y-fast) pak vedla k randomizovaným $\Theta(k)$ succ/pred a amortizovaně randomizovaným aktualizacím v $\Theta(k)$. Velikost potřebné paměti klesla na $\Theta(n)$.
Zajímavou alternativou jsou FW1990 fusion trees, které využívají triky s širokou aritmetikou (proto vynecháváme). Ty jsou tím efektivnější čím je větší poměr velikosti (logaritmu) univerza vůči reprezentované množině (širší aritmetika) na rozdíl od prezentovaných technik, kde je to obráceně.
Na konci hodiny jsme se trochu věnovali ST1985 splay trees. Udělali rozbor operace Splay s ohledem na libovolně zvolené váhy vrcholů. (V rozboru jsem tvrdil, že $\mu'_x=\mu_x$ znamená, že jsou všechna zmíněná $\mu$ stejná, ono ale může být třeba $\mu'_y$ menší. Tvrzení jsme k ničemu nepotřebovali. Potřebovali jsme jen tvrzení, že pokud $\mu'_x=\mu_x$ a nejsou všechna $\mu$ stejná, pak jsme mohli jedničku v odhadu ušetřit. To že stejná být nemohou bylo zdůvodněno správně.)
Přednáška 4
Video z přednášky vypadá OK. Zdvojnásobení velikosti znamená zvětšení logaritmu o 1 a ne zdvojnásobení logaritmu, ... ach jo.
Začali jsme motivací pro používání cestových operací na stromech se z vnějšku daným tvarem. První z nich byla implementace hledání toku ve vrstevnatých sítích potřebná v Dinicově algoritmu pomocí cestových operací, čímž při vhodné implementaci dostáváme složitost $O(m\log n)$ pro vrstevnatou síť (případně při kombinaci s algoritmem 3 indů $O(\min\{m\log n,n^2\})$). Celková složitost Dinicova algoritmu pak vychází $O(n\min\{m\log n,n^2\})$. Druhou motivací byla $\Theta(\log n)$ implementace (v průběhu hodiny jsme ukázali amortizovanou variantu) struktury pro testování hranové dvousovislosti PW1998 při aktualizacích umožňujících přidávání vrcholů či hran s podporou odvolávání aktualizací (libovolně hluboké historie). K implementacím jsme potřebovali umět přidat mezistromovou hranu, navýšit/snížit cenu všech hran na určené (koncovými vrcholy) cestě o konstantu, umět odstranit danou hranu, zeptat se na nejlacinější hranu na určené cestě.
Pokračovali jsme popisem možné implementace podcestových dotazů operací v rámci jedné cesty, možností podcestových aktualizací vah v rámci jedné cesty. (Ukázalo se, že reprezentace cesty inorder pořadím v binárním stromy umožňují dotaz na podcestu rozložit na spojení logaritmického počtu předzpracovaných dotazů, takže typicky vede k $O(\log n)$ složitosti.)
Následně jsme řešili podcestové dotazy v rámci stromu. Cestu mezi dvěma vrcholy snadno najdeme pokud je strom zakořeněný. Stačí najít první průsečík „lca“ na cestách do kořene z daných dvou vrcholů a úseky cest k tomuto průsečíku. Potřebovali jsme zajistit, aby cesta protínala nejvýš $O(\log n)$ předzpracovaných částí a těmito částmi byly podcesty stromu. Každou takovou podcestu jsme reprezentovali binárním stromem, takže se dotaz na úsek mezi libovolnými dvěma vrcholy podcesty rozkládal na $O(\log n)$ předzpracovaných dotazů. Pouze dotaz v části obsahující lca potřeboval úsek mezi libovolnými dvěma vrcholy. Na ostatních částech byl vždy dotaz od nějakého vrcholu do posledního vrcholu cesty a ty mohly být předzpracované, takže každý vyžadoval $O(1)$ času. Celkový čas dotazu pak mohl být $O(\log n)$.
Pokud pomocí DFS z kořene spočteme velikosti všech podstromů a každý vrchol spojíme do části s nejtěžším dítětem (v případě shody vybereme náhodně, pokud je váha podstromu dítěte menší než polovina váhy podstromu rodiče, není spojení potřeba). Tato strategie znamená, že není-li dítě ve stejné části s rodičem, tak velikost podstromu rodiče je aspoň dvakrát větší než velikost podstromu dítěte. Na cestě z libovolného vrcholu ke kořeni se ale velikost podstromu může zdvojnásobit nejvýš $\log_2 n$ krát takže se taková cesta rozpadá na nejvýš $\log_2 n$ částí, jak jsme potřebovali. Takovému to rozkladu se říká heavy-light dekompozice.
Heavy light dekompozice bude mít nejspíš problém s aktualizací pro cestu určenou dvojicí vrcholů. Přepočítání všech sufixových informací bude nejspíš časově náročné.
Pak jsme se konečně dostali k dynamickému rozkladu na cesty T1983. Nevěnovali jsme se worst case variantám využívajícím BST1985 biased trees, ale jednodušší variantě se splay stromy, dosahujícím amortizovaně stejných časů. Základem práce s cestami je operace Expose($u$), která zajistí aby kořenová část byla tvořená cestou z vrcholu $u$ do kořene reprezentovaného stromu. V neorientovaném případě (kdy kořen není zvenku určen) potřebujeme ještě operaci Evert($u$), která kořenovou cestu začínající ve vrcholu $u$ převrátí, takže se $u$ stane kořenem reprezentovaného stromu.
Operace Expose($u$) je prováděna ve třech fázích, kde v lichých (pomocných) fázích provádíme splay v jednotlivých částech na cestě ke kořeni reprezentace počínaje Splay($u$), takže druhá fáze začíná v situaci kde vrcholy do nichž se napojují části počínaje vrcholem $u$ jsou kořeny jednotlivých Splay stromů (reprezentujících jednotlivé části). Ve druhé fázi pro každý kořen Splay stromu (na cestě od $u$ až ke kořenové části) odtrhneme levé dítě a nahradíme je (pokud tím kořenem není $u$) hranou z kořene splay stromu části obsahující vrchol $u$. Tím se postupně část počínající v $u$ spojí do kořenové části. Protože tuto výměnu provádíme vždy v kořeni splay stromu, reprezentuje vždy levý podstrom část cesty pod vrcholem reprezentovaným v kořeni podstromu. Záměnou levého dítěte kořene tak dochází ke korektnímu přepojení částí. Jako váhy vrcholů jsme pro amortizovanou analýzu Splay stromů zvolili velikost podstromu pod vrcholem s výjimkou podstromu dítěte ve stejné části, proto se při této záměně $\mu$ kořene vůbec nemění. Ceny (včetně času) operací splay v první fázi sa dají odhadnout rozdílem $3\mu_\rho-3\mu_u$ plus počet částí na původní cestě z $u$ do kořene, kde $\rho$ reprezentuje kořen splay stromu reprezentujícího kořenovou část, takže $\mu_\rho$ odpovídá logaritmu velikosti komponenty obsahující vrchol $u$. Cenu (včetně času) druhé fázi můžeme odhadnout počtem částí na původní cestě z $u$ do kořene. Ve třetí fázi se provede tolik rotací, kolik bylo částí na původní cestě z $u$ do kořene. Cenu (včetně času) třetí fáze můžeme odhadnout rozdílem $3\mu_\rho-3\mu_u$. Čas i potenciál je v takovém rozboru měřen v jednotkách času dvojrotace. Pokud tuto jednotku navýšíme tak, abychom započítali jednotku času potřebou v prvních dvou fázích za jednu část na cestě z $u$ do kořene, dokážeme z potenciálu zaplatit i „přeskoky“ mezi částmi v prvních dvou fázích. Tím dostáváme v nových jednotkách celkový odhad ceny (včetně času) operace Expose($u$) $6\mu_\rho-6\mu_u+O(1)$.
Operace Evert($u$) je prováděna zavedením (a flipnutím) bitu jehož význam je pravolevé převrácení podstromu pod kořenem splay stromu kořenové části. Pravolevé převrácení obrací inorder uspořádání, takže tím jsou implicitně otočeny všechny orientace hran v kořenové části. Operace Evert tedy trvá konstantní čas. Znamená ale konstantní zpomalení rotací prováděných v průběhu operací splay. Na určení relativní pravolevosti vůči prarodiči musíme xorovat flipovací bit vrcholu s flipovacím bitem rodiče.
Pomocí operací Expose() a Evert snadno zajistíme, aby kořenovou částí byla cesta mezi danými vrcholy $u$, $v$. Zbývá jen dorozmyslet, jak reprezentovat ceny hran tak abychom snadno určili minimum ceny hrany na kořenové části (reprezentované Splay stromem). Pokud nepoužíváme Evert (orientovaný graf jako v prvním příkladě), můžeme ceny hran reprezentovat ve vrcholech z nichž vycházejí (v kořeni je $\infty$). Implementace Evert flipovacím bitem je ale s takovouto reprezentací nekompatibilní, protože by se jím měnily vrcholy v nichž by měly být váhy udržovány. Řěšením je přidat do reprezentovaného stromu na každou hranu pomocný vrchol, v němž bude váha hrany reprezentována. V původních vrcholech je cena $\infty$. Dodržujeme pak pravidlo, že část vždy začíná původním vrcholem. S takovouto reprezentací je implemantace evert flipovacím bitem kompatibilní.) Nyní již máme určeno v kterých vrcholech reprezentujeme ceny hran, potřebujeme ale takovou reprezentaci, aby byly dotazy i aktualizace efektivní. Řěšením je ceny v rámci části (v rámci Splay stromu) reprezentovat součtem mezivýsledků. V kořeni splay stromu reprezentujeme minimum cen celého splay stomu, a cenu reprezentovnou tímto kořenem jako rozdíl mezi reprezentovanou cenou a minimem podstromu (součtem těchto dvou hodnot dostaneme reprezentovanou cenu). Pro ostatní vrcholy splay stromu reprezentujeme minimum cen jejich podstromu rozdílem od minima ceny podstromu rodiče. Minimum cen podstromu tedy můžeme získat jako součet diferencí minim cen podstromů na cestě ke kořeni včetně minima cen v celém stromu. Cenu daného vrcholu reprezentujeme i zde rozdílem od minima ceny podstromu. Takže reprezentovanou cenu získáme přičtením minima ceny podstromu. (Vzhledem k tomu, že u splay stromů vždy pracujeme v kořeni, tak nikdy nepotřebujeme určovat cenu takto složitým výpočtem.) Zjišťování minimální ceny kořenové části je v této reprezentaci triviální, je uložena přímo v kořeni. Změna všech cen hran kořenové části přičtením stejné konstanty je triviální (přičteme danou konstantu k minimu celého splay stromu reprezentujícího kořenovou část). Tato implicitní reprezentace cen ale opět konstantně zpomaluje rotace (je potřeba přepočítat relativní minima a relativní ceny vůči relativním minimům, nepotřebujeme k tomu znát absolutní hodnoty minim), stejně tak to konstantně zkomplikovalo převěšení levých podstromů kořene (do vrcholu z kterého se stane kořen utrhávaného podstromu musíme přičíst minimum celého stromu a opačně při připojování).
Amortizovaná složitost (současně i worst case) jednotlivých operací s našimi dynamickými stromy je pak konstantní s výjimkou operace Expose($u$) jejíž amortizovaná složitost je $6\mu_\rho-6\mu_u+O(1)$, kde $\mu_\rho$ je logaritmus velikosti komponenty obsahující $u$, a $\mu_u$ je logaritmus velikosti podstromu splay stromu pod vrcholem $u$ včetně velikosti všech částí připojených do tohoto podstromu.
Ve zbývajícíh 3 minutách jsem naznačil užitečnost (pokud nepotřebujeme cestové dotazy) reprezentace tvaru stromu pomocí Eulerovských procházek na zdvojených hranách stromu, kde libovolně přeseknutou procházku reprezentujeme inorder pořadím vyváženého stromu. Jednoduše pak můžeme v logaritmickém čase spojovat či rozpojovat takovéto stromy (jen přitom musíme měnit „přeseknutí“, k tomu ale stačí strom vertikálně přeseknout a vzniklé dvě části spojit v opačném pořadí).
Kromě Eulerovkých procházek jsem upozornil na existenci interface AHLT2003 Top stromů, kde strom je dekomponován na podstromy, které je možno vnímat jako zobecněné hrany. Existuje driver, který zaručuje logaritmickou hloubku dekompozice a jako hlavní operaci umožňuje Expose($u$,$v$) zajistit, aby bylo možno vnímat strom obsahující $u$ a $v$ jako zobecněnou hranu $(u,v)$ (pokud jsou $u$, $v$ v jednom stromě). Interface umožňuje uživateli definovat informace, které chce v zobecněných hranách udržovat a jak tyto informace přepočítávat při primitivních operacích se zobecněnými hranami (spojení dvou zobecněných hran do jedné, rozdělení zobecněné hrany, konverze hrany na zobecněnou hranu a naopak).
Tento interface umožňuje jak práci s cestovými, tak necestovými informacemi. Umožňuje například udržovat centrum stromu efektivněji než jiné datové struktury. Existuje více driverů, jejich imlementace je netriviální, výše popsané link cut trees mohou sloužit jako podklad jedné z nejjednodušších (amortizovaných) implementací.
Přednáška 5
Věnovali jsme se rozboru TL1984 Disjoint Find Union. Připomněli jsme si, že nezávisle na tom, zda spojujeme třídy ekvivalence dle ranku či dle velikosti vychází podstrom pod vrcholem ranku $r$ velký alespoň $2^r$ (neuvažujeme zkracování cest resp. v době, kdy je vrchol stále ještě kořenem). Proto je nejvýš $n/2^r$ vrcholů ranku $r$ (disjunktnost), kde $n$ je počet vrcholů (počátečních tříd ekvivalence). Připomněli jsme si, že $\sum_{k=0}^\infty k/2^k=2$.
Pak jsme definovali tři techniky zkracování cest v průběhu Find (na cestě vždy ostře roste rank), z nichž komprese a splitting byly formou kompakce, což znamená, že všechny hrany po provedení operace Find vedou buď do kořene či do vrcholu na původní cestě s větším rankem než měly před operací Find. U halvingu toto platí pro skok přes dvě hrany. Čas operace Find je proporcionální délce cesty, takže naší snahou je odhadnout celkovou délku všech cest použitých operacemi Find v době práce s datovou strukturou.
Následně jsme bez znalosti významu ${\rm level}(x)$, pouze s tím, že hodnoty jsou nezáporné a menší než nějaké $\ell$ odhadli délku cesty (z operace find na $x_0$) průchodem po jednotlivých vrcholech cesty se zohledněním potenciálu „${\rm level}(x)$“, kde $x$ ja aktuální vrchol na cestě. Dostali jsme odhad ${\rm level}(x_0)+\sum_{i\in P} (1+{\rm level}(x_{i+1})-{\rm level}(x_i))$, kde $P$ označuje vrcholy $x_i$ na cestě, jejichž level není větší než level následujícího vrcholu ($x_{i+1}=p(x)$) na cestě. Potenciál jsme zavedli, abychom dokázali odhadnout počet vrcholů nepatřících do $P$. ${\rm level}(x_0)\le \ell$ naúčtujeme dané operaci Find.
Důležitou vlastností ${\rm level}(x)$ je, že v průběhu času pro vrchol $x$ nemůže tato hodnota nikdy klesnout a pokud je $x$ v $P$, bude po operaci find jeho level roven alespoň ${\rm level}(x_{i+1})$. To nám umožňuje předplatit všechny příspěvky ${\rm level}(x_{i+1})-{\rm level}(x_i)$ v odhadu délek cest zdražením o $\ell$ operace Union, která připojila $x_i$ pod nějaký jiný vrchol.
K dokončení odhadu celkové délky cest potřebujeme posčítat jedničky v daných sumách, tedy kolikrát mohli být jednotlivé vrcholy v $P$. K tomu již potřebujeme definici ${\rm level}(x)$. V prvním nástřelu víme, že funkce ${\rm level}(x)$ bude definována na základě $\ell+1$ řádkové tabulky (počínaje od řádku 0), kde v prvním řádku jsou hodnoty $0\dots \log_2 n$ rozděleny na intervaly délky 1 a v dalších řádcích je méně a méně intervalů vzniklých spojováním intervalů předchozího řádku, s tím, že v řádku $\ell$ je jediný interval. Můžeme označit $b_{i,j}$ z kolika intervalů předchozího řádku se skládá $j$-tý interval na $i$-tém řádku.
${\rm level}(x)$ (pokud $x$ není kořen) je první řádek, na němž je jak ${\rm rank}(x)$ tak ${\rm rank}(p(x))$ ve stejném intervalu. Vzhledem k tomu, že je rank pro nekořeny konstantní, a rank rodiče se může měnit jen tím, že se změní rodič (zvýšení) či je-li rodič kořen, jemuž se rank zvětšil připojením podstromu stejného ranku, nemůže tedy později dojít k tomu, že by se interval mezi $x$ a $p(x)$ zkrátil a vešel se do intervalu na dřívějším řádku. Tedy náš předpoklad neklesání hodnoty ${\rm level}(x)$ v čase platí. Navíc po kompakci s výjimkou předposledního vrcholu na cestě bude ${\rm rank}(p'(x))$ velký alespoň ${\rm rank}(p(p(x)))$ (a předposlední vrchol nepatří do $P$). Proto ${\rm level}'(x)\ge \max({\rm level}(x),{\rm level}(p(x)))$ (přinejmenším sjednocení obou intevalů se musí vejít do intervalu příslušného řádku), takže platí předpoklad, že pro $i$ v $P$ bude po Find ${\rm level}'(x_i)\ge {\rm level}(x_{i+1})$.
Navíc, pokud je $a\in P$, pak ${\rm level}(x_a)\ge 1$ a musely být $x_a$, $p(x_a)$ i $p(p(x_a))$ v různých intervalech úrovně ${\rm level}(x_a)-1$. To může pro vrchol jehož rank padne do $j$-té přihrádky úrovně $i$ nastat na úrovni $i$ nejvýš $b_{i,j}-1\le b_{i,j}$ krát. Pokud to posčítáme pro všech $n_{i,j}$ vrcholů přihrádky, dostaneme odhad $n_{i,j}b_{i,j}$. Přes všechny přihrádky pak $\sum_{i\ge 1,j}n_{i,j}b_{i,j}$. Je-li $r_{i,j}$ nejnižší rank v $j$-té přihrádce řádku $i$, pak $n_{i,j}\le 2n/2^{r_{i,j}}$. Zvolíme-li pro $i<\ell$ $b_{i,j}\le r_{i,j}$ dostaneme součet $\sum_j n_{i,j}b_{i,j}\le \sum_r 2nr/2^r=4n$. Tím bychom dostali celkem $\sum_{i\ge 1,j}n_{i,j}b_{i,j}\le 4\ell n+nb_{\ell,1}$. Nám se ale v odhadu faktor $\ell$ nelíbí a radši navýšíme cenu operace Find o $\ell$. Tím že pro každý level $l$ první $x_i \in P$ s ${\rm level}(x_i)=l$ zaplatí operace Find. V takovém případě nikdy neúčtujeme na úrovni $i$ vrcholu, jehož rank padne do první přihrádky na úrovni $i-1$. Posčítáme zvlášť příspěvky za první přihrádky na každém řádku a za ostatní přihrádky (poslední řádek zcela samostatně). Součty na řádcích od druhé přihrádky jsou $$\sum_{j>1} n_{i,j}b_{i,j}\le \sum_{r\ge r_{i,2}} 2nr/2^r=2n/2^{r_{i,2}}\sum_{r\ge 0}((r+r_{i,2})/2^r)=2n/2^{r_{i,2}}((\sum_{r\ge 0} r/2^r)+r_{i,2}(\sum_{r\ge 0}1/2^r))=4n(1+r_{i,2})/2^{r_{i,2}}.$$ Zvolíme $b_{i,1}=2$, tedy $r_{i,2}$ rostoucí (a $r_{1,2}\ge 2$) a celkově $$\sum_{i\ge 1,j>1}n_{i,j}b_{i,j}\le \sum_{i\ge 1} 4n/2^{r_{i,2}}(1+r_{i,2})\le 4n(\sum_{r\ge r_{1,2}} 1/2^r+\sum_{r\ge r_{1,2}}r/2^r)\le 4n(2/2^{r_{1,2}}+2(1+r_{1,2})/2^{r_{1,2}})\le 8n.$$
V první přihrádce $i$-tého řádku účtujeme jen za vrcholy jejichž rank je aspoň $r_{i-1,2}$, tedy nejvýš $2n/2^{r_{i-1,2}}\cdot b_{i,1}=4n/2^{r_{i-1,2}}$ součet přes všechny řádky pak dává $\sum_i 4n/2^{r_{i-1,2}}\le 4n$.
Zbývá finalizovat přihrádkové schéma a určit $\ell$. Nechť $m$ je počet operací prováděných datovou strukturou. Zjednodušíme to a $j$ tou přihrádku na řádku $i$ ukončíme těsně před rankem $A(i,j)$, kde $A(0,j)=j$, $A(i,1)=A(i-1,2)$ pro $i>0$ a $A(i,j)=A(i-1,A(i,j-1)+1)$ pro $i,j>0$. (V článku je používána rychleji nastartovaná varianta Ackermanova funkce a je dodržováno $b_{1,j}=r_{1,j}$, nicméně ve výsledku je naše $\alpha(m,n)$ nejvýš o $2$ větší.) První podmínka zajišťuje, aby každý interval na nultém řádku byl jednoprvkový, druhá aby $b_{i,0}=2$ a třetí $b_{i,j}\le r_{i,j}$ pro $j>1$ dokonce $\sum_{k\le j} b_{i,k}\le r_{i,j}$. Zvolíme $\ell-1=\alpha(m+n,n)=\min\{i\mid A(i,\lfloor (m+n)/n\rfloor)>\log n\}$ tedy jakmile na řádku $\ell-1$ je nejvýš $\lfloor (m+n)/n\rfloor$ intervalů, pak tedy $b_{\ell,1}\le \lfloor (m+m)/n\rfloor$ a $n_{\ell,1}b_{\ell,1}\le n(m+m)/n=m+n$. (Pokud bychom chtěli využít fakt, že účtujeme jen vrcholům s ${\rm rank}(x)\ge r_{\ell-1,2}=A(\ell-1,1)$, mohli bychom použít $\ell-1=\alpha'(m+n,n)=\min\{i\mid A(i,\lfloor (m+n)/n\rfloor \cdot 2^{A(i-1,1)-1})>\log n\}$.)
Dostali jsme tak, že kromě času $O(1+\alpha(m+n,n))$ účtovanému jednotlivým operacím potřebujeme $13n+m$ času. Celkem tedy $O(n+m(1+\alpha(m+n,n)))$ (pokud vytváření vrcholů zavedeme jako třetí metodu datové struktury, můžeme sčítanec $n$ v odhadu nahradit pomocí $m$).
Pro halving je potřeba důkaz mírně modifikovat a definovat level na základě $x$ a $p(p(x))$. Rozbor přirozeně zaplatí půlku délky cesty (vrcholy, jimž se mění $p(x)$), takže dostáváme dvojnásobek pro odhad celkové složitosti.
Užitečné je si všimnout, že $\alpha(m,n)$ je nerostoucí v první a neklesající ve druhé souřadnici a například pro $m>n\log\log^*n$ platí $\alpha(m,n)\le 4$. Takže například Kruskalův algoritmus volaný se setříděným seznamem hran podle cen je v případě aspoň $n\log\log^*n$ hran lineární (v počtu hran). V článku definují „separovatelné algoritmy“ a s odkazem na jiné články dokazují, že dosažený výsledek je pro takové algoritmy asymptoticky optimální.
Přednáška 6
Věnovali jsme se haldám. Jako motivaci jsme měli algoritmus Fredman Tarjan na hledání minimální kostry FT1987 v řádově $\log^*n$ fázích, kde každá trvá $\Theta(m)$.Následně jsme rychle proletěli $d$-reguární haldy a začali se věnovat odvození varianty Fibonacciho hald na základě principu „drahého porovnávání“. K dosažení optimální amortizované složitosti nám v rozboru stačil součet 4 potenciálů.
Ke konci hodiny jsem naznačil, jak efektivně implementovat worst case verzi hald bez operace meld M2020. Od Fibonacciho hald byl rozdíl v tom, že místo lokální podmínky omezující ztrátu každého rankového potomka (poté co byl připojen rankovou hranou mu byl ztráta krát snížen rank) na nejvýš 1 používáme součet ztrát všech potomků je menší než maximální řád plus 1. Ukazuje se že maximální řád se tím příliš nezmění (asymptoticky je menší než u Fibonacciho hald). Struktura vyžaduje různé priority prvků, což je případně potřeba zajistit lexikografickým porovnáváním a přidaným identifikátorem v druhé souřadnici. Na rozdíl od Fibonacciho hald struktura při konsolidaci nevlkádá všechny kandidáty na minimum do pole dle řádů, aby je na konci z pole odstranila, ale rankové kořeny stromů dle jednotlivých řádů udržuje v poli celou dobu. Obdobně v poli dle jednotlivých řádů udržuje potomky se ztrátou 1.
Aby bylo dosaženo worst case složitostí, končí ExtractMin plnou konsolidací, zatímco metody které mají pracovat v konstantním čase končí konsolidací částečnou. Při ní je zajištěno, aby existoval jediný kandidát na minium a jak počet rankových stromů, tak součet ztrát byly nejvýš maximální rank plus 1. Toho je dosaženo pomocí konsolidačních operací spojujících stromy stejného řádu (a stejné „poruchy“), případně pro vrchol se ztrátou aspoň 2 konverzí rankové hrany na nerankovou, čímž se danému vrcholu vynuluje ztráta, ale jeho rodiči, nebyl-li rankovým kořenem se zvětší ztráta o 1. Mohou nastat situace, kdy je příležitost pokračovat s konsolidací nekonstantně dlouho. My místo toho konsolidaci (za jasně definovaných okolností) přerušíme a vrchol, jenž by měl být dále řešen odložíme na zásobník čekajících konsolidací. Takový zásobník máme jak pro konsolidace počtu nerankových hran, tak pro konsolidace ztrát. Z hlediska rozboru používáme součet dvou potenciálů. Prvním je jednou zaplnění pole řádů rankových kořenů plus dvakrát počet prvků na zásobníku nerankovýh hran, druhým je třikrát zaplnění pole řádů potomků se ztrátou 1 plus čtyřikrát součet velikostí ztrát (resp. 1 pro vrchol bez ztráty) na zásobníku konsolidace ztrát. Každý konsolidační krok snižuje tento potenciál. Dodržujeme strategii, že po skončení operace musí být pro obě složky potenciálu buď daná složka menší než byla na začátku operace, nebo musí být příslušný zásobník konsolidace prázdný. Dá se spočítat, kolik jakých konsolidačních kroků je potřeba pro každý druh operace vykonat, aby byla podmínka splněná. A je to konstanta.