#let OOO = math.cal("O") #set text(lang: "cs") = Velké otázky + Definujte Splay strom. Popište, jak na něm probíhají operace Splay, Find, Insert a Delete. Popište výhody a nevýhody oproti jiným datovým strukturám, zejména vyváženým vyhledávacím stromům. Vyslovte a dokažte větu o amortizované složitosti operace Splay. - strom, ve kterém všechny operace vykonáváme pomocí Splay - neřešíme vyváženost, ale dokážeme, že Splay se vždy uamortizuje na $log$ - *Splay*: vybraný vrchol přesunu do kořene pomocí rotací, přičemž preferuji dvojrotace - každý Splay použije nejvýše jednu jedno-rotaci - *Find*: Najdu vrchol jako v BVS, vysplayuji nalezený nebo poslední navštívený do vrcholu - *Insert*: Insert jako do normálního BVS, vysplayuji nalezený/vložený vrchol do kořene - #text(red)[přidání listu může být drahé] - zvýším rank všem vrcholům na cestě do kořene - $ Delta Phi = r'(v_(t+1)) + sum_(i=1)^t r'(v_i) - r(v_i) $ - jejich rank se zvýší o 1, což se dá odhadnout zhora původním rankem jejich rodiče – $r'(v_(i)) <= r(v_(i-1))$ - $r'(v_(t+1)) = 0$ (je to list) - $ Delta Phi <= r'(v_1) - r(v_t) $ - *Delete*: Najdu vrchol k odstranění, vysplayuji do vrcholu, odstraním, vysplayuji nejpravější vrchol levého podstromu, spojím dohromady - výhody - sequential access - working set - ⇒ vyhledání $m$ prvků z podmnožiny velikosti $s$ je $𝓞(n log n + m + m log s)$ - *složitost Splay*: - zavedeme $r(x)$ (rank vrcholu) jako $log(s(x))$ - potenciál je $Phi = sum_(x_i in V) r(x_i)$ - dvojrotace mají amortizovanou cenu $A = 3r'(x_i) - 3r(x_i)$, jednorotace $A = 3r'(x_i) - 3r(x_i) + 1$ ($r$ je před rotací, $r'$ je po) - celá Splay je pak posloupnost rotací jednoho vrcholu, $A = (sum_i 3r_i (x) - 3r_(i-1)(x)) + 1$, všechny až na poslední rotaci jsou dvojrotace, teleskopická suma se posčítá na $ A = 3r_n (x) - 3r_0 (x) + 1 $ (kde +1 je z poslední rotace) - *zig-zag*: - $A = 2 + r'(x) + r'(w) + r'(y) - r(x) - r(w) - r(y)$ - $s'(w) + s'(y) <= s'(x)$ - $r'(w) + r'(y) <= 2 log(s'(w) + s'(y)) - 2 <= 2 r'(x) - 2$ - $A <= 3r'(x) - r(x) - r(w) - r(y)$ - $r(x) <= r(w)$, $r(x) <= r(y)$ - $A <= 3r'(x) - 3r(x)$ - *zig-zig*: - $A = 2 + r'(x) + r'(y) + r'(z) - r(x) - r(y) - r(z)$ - $s(x) + s'(z) <= s'(x)$ - $r(x) + r'(z) <= 2 log (s(x) + s'(z)) - 2 <= 2 r'(x) - 2$ - $A <= 3r'(x) + r'(y) - 2r(x) - r(y) - r(z)$ - $r'(x) >= r'(y)$, $r(x) <= r(y)$, $r(z) = r'(x)$ - $A <= 3r'(x) + r'(x) - 2r(x) - r(x) - r'(x)$ - $A <= 3r'(x) - 3r(x)$ - *zig*: - $A = 1 + r'(x) + r'(y) - r(x) - r(y)$ - $r(x) <= r(y)$, $r'(x) >= r'(y)$ - $A <= 1 + 2r'(x) - 2r(x)$ - $r'(x) - r(x) >= 0$ - $A <= 1 + 3r'(x) - 3r(x)$ + Definujte (a,b)-strom. Popište, jak na něm probíhají operace Find, Insert a Delete. Vyslovte a dokažte větu o amortizovaném počtu změn uzlů pro operace Insert a Delete a (a,2a)-stromech. Jak se to liší pro (a,2a-1)-stromy? Popište výhody a nevýhody oproti jiným datovým strukturám, zejména vyváženým binárním vyhledávacím stromům. - stromy, kde počet potomků každého vrcholu je mezi $a$ a $b$, kde $b >= 2a-1$ - *hloubka*: $Theta(log_b n)$, $OOO(log_a n)$ - *Find*: musíme projít $OOO(h) = OOO(log_a n) = OOO(log n \/ log a)$ vrcholů, v každém vrcholu vrchol najdeme binárním vyhledáváním v $OOO(log b)$, celkově $OOO(log n dot log b \/ log a)$ - *Insert*: přidáme klíč do nejnižšího vrcholu, splitujeme, je-li třeba, split trvá $OOO(b)$, celkově $OOO(b dot log n\/log a)$ - *Delete*: odstraníme klíč a nahradíme maximem levého podstromu, buď se mergenem se sousedem, nebo z něj půjčíme klíč (soused → rodič → my) - $m$ po sobě jdoucích insertů do prázdného stromu je v $𝓞(m)$ - každý split zvýší množství vrcholů, merge neděláme, vrcholů je $OOO(m)$ - *věta*: pro (a,2a)-stromy taky $m$ po sobě jdoucích insertů a deletů do prázdného stromu je v $𝓞(m)$ - určíme si potenciál podle počtu klíčů ve vrcholu ($a,2a$) → ($a-1, 2a-1$) - #table(columns: 8, $k$, $a-2$, $a-1$, $a$, $...$, $2a-2$, $2a-1$, $2a$, $f(k)$, $2$, $1$, $0$, $0$, $0$, $2$, $4$) - přidání/odebrání vrcholu -- $|f(i) - f(i+1)| <= c$ - split: - $f(2a)$ → $f(a) + f(a-1) + underbrace(c, "přidání vrcholu do rodiče") + underbrace(1, "skutečná cena")$ - $4 >= 0 + 1 + 2 + 1$ - merge: - $f(a - 2) + f(a - 1)$ → $f(2a - 2) + underbrace(c, "ubrání vrcholu z rodiče") + underbrace(1, "skutečná cena")$ - $2 + 1 >= 0 + 2 + 1$ - *důsledek*: Libovolná posloupnost $m$ Insertů a Deletů je $OOO(n+m)$ (můžu postavit posloupnost $n$ Insertů do prázdného stromu) - výhody: - cache-aware - amort. konstantní složitost operací - nevýhody?? + Definujte I/O model pro správu cache a srovnejte cache-aware a cache-oblivious algoritmy. Vyslovte a dokažte Sleatorovu-Tarjanovu větu o kompetitivnosti LRU. Popište přínos této věty pro analýzu cache-oblivious algoritmů. - externí a interní paměť - interní má omezenou velikost $M$ - externí je neomezená, ale lze číst a zapisovat pouze načtením bloku velikosti $B$ do interní paměti - I/O složitost se obvykle určuje jen ve čteních z externí paměti, protože zápisy jsou většinou čteními zhora omezené - algoritmus neovládá, které bloky se vyhodí z keše, je použit nějaký online algoritmus - algoritmus OPT vyhazuje vždy ten blok, který bude potřeba nejdále v budoucnosti – optimum - algoritmus LRU vyhazuje ten blok, který byl použit nejdále v minulosti - umíme dokázat, že to není tak špatné: $ C_"LRU" <= (M_"LRU")/(M_"LRU" - M_"OPT") dot C_"OPT" + M_"OPT" $ tedy, pokud $M_"LRU" = 2 dot M_"OPT"$: $ C_"LRU" <= 2 C_"OPT" + M_"OPT" $ - *důkaz* - rozdělme posloupnost přístupů k blokům do _epoch_ $e_0, ..., e_n$, tak, aby pro každou epochu kromě $e_0$ platilo $C_"LRU" (e_i) = M_"LRU"$, pro $e_0$: $C_"LRU" (e_0) <= M_"LRU"$ - pro každou epochu kromě $e_0$ platí jedna z možností: - všechny missnuté prvky jsou různé, takže $C_"OPT" (e_i) >= M_"LRU" - M_"OPT"$ - některý prvek byl missnut vícekrát, takže mezi jeho načteními muselo být přistoupeno ke všem ostatním prvkům keše, takže opět $C_"OPT" (e_i) >= M_"LRU" - M_"OPT"$ - tedy $C_"LRU" (e_i) = M_"LRU"$ a $C_"OPT" (e_i) >= M_"LRU" - M_"OPT"$: $ (C_"LRU" (e_i))/(C_"OPT" (e_i)) <= M_"LRU"/(M_"LRU" - M_"OPT") $ - pro $e_0$ pak platí: - pokud keše začínají prázdné, všechny missy LRU jsou různé a OPT je všechny musí načíst taky, proto $C_"OPT" (e_0) >= C_"LRU" (e_0)$ - pokud LRU obsahuje bloky, nějaký miss se může proměnit v hit, ale výsledný LRU seznam se nezmění - pokud OPT obsahuje bloky, budou to přesně ty, které bude v $e_0$ potřebovat, tedy $C_"OPT" (e_0) >= C_"LRU" (e_0) - M_"OPT"$ - po zprůměrování přes epochy $e_1...e_n$ a $M_"OPT"$ z $e_0$ získáme chtěný vztah - *důsledek*: ve většině zkoumaných algoritmů je závislost na $M$ taková, že vynásobení konstantou $c M$ (v tomto případě $c = 2$) se asymptotika nezmění, takže lze předpokládat OPT, i když se použije LRU + Definujte c-univerzální a k-nezávislé rodiny hešovacích funkcí. Uveďte příklady, kde nestačí c-universální rodina hešovacích funkcí, ale musíme použít k-nezávislou rodinu. Formulujte a dokažte větu o střední délce řetězce v hešování s řetězci. Ukažte příklady c-univerzálních a k-nezávislých rodin pro hešování přirozených čísel. Pro jeden příklad dokažte c-universalitu nebo k-nezávislost, pro k ≥ 2. - pro danou konstantu $c$, je rodina hashovacích funkcí $cal(H): cal(U) -> [m]$ $c$-univerzální, pokud pro všechny různé dvojice $x,y in cal(U)$: $ Pr_(h in cal(H))[h(x) = h(y)] <= c/m $ - pro dané $k$ a konstantu $c$, je rodina hashovacích funkcí $cal(H): cal(U) -> [m]$ $(k,c)$-nezávislá, pokud pro každou $k$-tici různých $x_1...x_k in cal(U)$ a $y_1...y_k in [m]$: $ Pr_(h in cal(H))[h(x_1) = y_1 and ... and h(x_k) = y_k] <= c/m^k $ - právě lineární adresování potřebuje 5-nezávislost pro konstantní čas, případně kukačky, also *[T]* se odkazuje na QuickSort - *délka řetězce*: - věta: pro $c$-univerzální rodinu $cal(H): cal(U) -> [m]$, $X = {x_1, ..., x_n}$ prvky v ní uložené, a $y$ prvek neuložený: $ EE_(h in cal(H))[\#i: h(x_i) = h(y)] <= (c n)/m $ - dk: nechť $A_i$ je indikátorová veličina, že $h(x_i) = h(y)$, $EE A_i <= c/m$ z $c$-univerzality, $EE sum_i A_i = sum_i EE A_i <= (c n)/m$ - důsledek: - neúspěšné vyhledávání projede celý řetízek s $h(y)$, takže $<=(c n)/m$ - úspěšný insert nejdřív provede neúspěšné vyhledávání, $<=(c n)/m$ - úspěšné vyhledávání projde nejvýše tolik prvků, kolik prošlo přidání daného prvku $<=(c n)/m$ - neúspěšný insert odpovídá úspěšnému vyhledávání, $<=(c n)/m$ - delete odpovídá úspěšnému/neúspěšnému vyhledávání $<=(c n)/m$ - tedy, pokud je $m in Omega(n)$ jsou operace na řetízkové hashovací tabulce konstantní - příklady: - *Lineární kongruence*: pro prvočíslo $p$ a $m < p$, $ cal(L): [p] -> [m]: { h_(a,b) | a, b in ZZ_p } $ $ h_a,b(x) = ((a x + b) mod p) mod m $ - v $ZZ_p$ existuje pro dané různé $x,y$ a soustavu: $ r = (a x + b) mod p\ s = (a y + b) mod p $ bijekce mezi páry $(r,s)$ a $(a,b)$ - $Pr[h_(a,b) (x) = r and h_(a,b) (y) = s] = 1/p^2$ pro rovnoměrně náhodně vybrané $a,b$ - bez druhého $mod m$ je tedy rodina $2$-nezávislá, lemma o modulení říká, že s ním to bude jen $2c$ horší - *Polynomiální hashování*: $ cal(P)_k: [p] -> [p]: {h_bold(t)(x) | bold(t) in ZZ_p^k} $ $ h_bold(t)(x) = sum_(i=0)^(k-1) t_i x^i mod p $ - je $k$-nezávislé, neboť pro $x_1...x_k$ a $a_1...a_k$ existuje právě jeden polynom stupně nejvýše $k$ takový, že platí: $forall i: p(x_i) = a_i$ - takových polynomů je $p^k$, máme $(k,1)$-nezávislost - pro $[p] -> [m]$, kde $p > 2 k m$ dává modulící lemma $(k,2)$-nezávislost - Multiply-shift - Tabulkové hashování + Popište a analyzujte hešování s lineárním přidáváním s plně náhodnou hešovací funkcí a např. třetinovým zaplněním. Popište výhody a nevýhody oproti jiným datovým strukturám, zejména založeným na hešování. - do každého kyblíku hashujeme pouze jeden prvek, v případě kolize hledáme $h(x) + i mod m$ - pro zaplněnost $<= 1/3$ (tedy $m >= 3n$) a plně náhodnou hashovací funkci dokážeme konstantní délku "běhů" - nechť $n = m/3$ (horší už to být nemůže) - kyblíky $[m]$ rozdělíme postupně na po sobě jdoucí bloky velikosti $2^t$ (jako úplný binární strom) - blok je _kritický_, pokud se do něj *zahashuje* $2/3 dot 2^t$ prvků - *Černovova nerovnost*: Pro nezávislé náhodné veličiny s hodnotami ${0,1}$, jejich součet $X = X_1 + ... + X_k$, $mu = EE[X]$ a $c > 1$: $ Pr[X >= c mu] = (e^(c-1)/c^c)^mu $ - Pravděpodobnost, že blok $B$ velikosti $2^t$ je kritický je $(e/4)^(1/3)^2^t = q^2^t$, $q dot(eq) 0.879$ - $ EE[X] = 2^t dot 1/3 $ - Černov: $c = 2$, $ Pr[X >= 2^t dot 1/3 dot 2] = (e/2^2)^(2^t dot 1/3) $ - Každý běh $R$, $|R| >= 2^(l+2)$ obsahuje alespoň jeden kritický blok délky $2^l$ - Běh $R$ zasahuje do 4 nebo 5 bloků velikosti $2^l$. - První blok $B_0$ obsahuje alespoň $1$ prvek z $R$, $B_1...B_3$ obsahují $2^l$ prvků - Před $B_0$ je prázdno, takže všechny prvky v $L = B_0...B_3 inter R$ se sem i zahashovaly (nepřetekly sem) - Do $L$ musí být zahashovaných alespoň $1+3 dot 2^t$, ale čtyři nekritické bloky obsahují nejvýše $4 dot 2/3 dot 2^t$. - Nechť $R$ je běh obsahující $h(x)$ a $|R| in [2^(l+2), 2^(l+3))$, pak jeden z 12 okolních bloků je kritický, 8 před $h(x)$, 3 po - $R$ je 4 až 8 bloků dlouhý, ale nemusí být aligned, takže zasáhne 4 až 9 bloků - pokud končí blokem s $h(x)$, zabírá až 8 bloků před $h(x)$ - pokud začíná blokem s $h(x)$, zabírá až 8 bloků za $h(x)$, ale kritický je jeden z prvních 4 - Aby běh $R$ obsahující $h(x)$ byl dlouhý $[2^(l+2), 2^(l+3))$, musí z okolních 12 bloků být alespoň jeden kritický - Union bound – pravděpodobnost, že libovolný z 12 jevů nastane je nejvýše $12 dot p$ - Tedy pro $R$ běh obsahující $h(x)$, $ Pr[|R| in [2^(l+2), 2^(l+3))] <= 12 dot Pr["blok velikosti "2^l" je kritický"] = 12 dot q^2^l $ - Pro běh $R$ obsahující $h(x)$: $ EE[|R|] <= 3 dot Pr[|R| <= 3] + sum_(l>=0) 2^(l+3) dot 12 dot q^2^l\ EE[|R|] <= 3 dot 1 + 12 dot 8 dot sum_(l>=0) 2^l dot q^2^l\ EE[|R|] <= 3 dot 1 + 96 dot sum_(i>=1) i dot q^i $ - poslední úprava – suma před úpravou dosazuje za $i$ jen mocniny dvojky, suma po úpravě dosazuje všechna přirozená čísla, což je určitě horní odhad - Gabrielovo schodiště konverguje pro libovolné $q$ + Definujte vícerozměrné intervalové stromy (range trees). Rozeberte prostorovou složitost datové struktury a časovou složitost konstrukce a obdélníkových dotazů (bonus: včetně zrychlení zlomkovým kaskádováním). - Intervalové stromy jsou identické s BVS, jen při hledání pamatujeme interval vrcholů, které daný podstrom může obsahovat #let inv = "inv" - *Vyhledávání intervalu $I$*: Rekurzí, - pokud je $v in I$, reportuju $v$ - pokud je $inv(v) subset.eq I$, reportuju celý podstrom a končím - rekurzím do potomků, které zasahují do $I$, pokud zasahují oba, v každém mi zůstane jen jeden konec intervalu a už budu rekurzit vždy jednou - $2$-d intervalové stromy - v každém vrcholu $x$-stromu je $y$-strom pro daný podstrom - každý vrchol je v $OOO(log n)$ sekundárních stromech (jeden za každý vrchol na cestě do kořene) -- paměť $OOO(n log n)$ - vyhledávání: - pro každý nalezený vrchol z $x$-stromu se ptám daného $y$-stromu -- $OOO(n log^2 n)$ - dynamizace - weight-balanced přestavení celého nevyváženého podstromu $OOO(n log^2 n)$ - $d$-d intervalové stromy - v každém vrcholu primárního stromu je $(d-1)$-d strom - paměť $OOO(n log^(d-1) n)$ - vyhledávání v $OOO(n log^d n)$ - zlomkové kaskádování ve $2$-d - místo $y$-stromů udržuji seřazená pole a odkazy do podseznamů pod každým z $x$-potomků, pro pokračování vyhledávání - $OOO(log n)$ + Definujte sufixové pole a LCP pole. Popište a analyzujte algoritmy na jejich konstrukci (pro sufixové pole stačí ve skoro lineárním čase). Popište příklad úlohy, kterou umí tato pole efektivně řešit. + Popište zámky a atomické operace CAS a LL/SC. Navrhněte a analyzujte bezzámkovou implementaci zásobníku. Vysvětlete problém ABA a navrhněte jeho řešení. Porovnejte paralelizaci datových struktur za použití zámků a za použití atomikých operací (tzv. bezzámkové datové struktury), přičemž v obou případech vysvětlete, jaké mohou nastat problémy. = Malé otázky + Popište dynamické pole, tedy „nafukovací pole" se zvětšováním a zmenšováním. Analyzujte jeho amortizovanou složitost. - když dojde místo, realokuju na dvojnásobek - po každé realokuji 2× tolik prvků, kolik jsem od poslední realokace přidal + Popište vyhledávací stromy s líným vyvažováním (BB[α]-stromy). Analyzujte jejich amortizovanou složitost. Uveďte příklad jejich použití. - začínám s plně vyváženým stromem, v každém vrcholu si počítám množství vrcholů v podstromu - za vyvážený ho považuji, pokud $1/3 m(v) <= m(cal(l)(v)) <= 2/3 m(v)$ - to udrží $log$ hloubku (délka cesty je omezená $log_(3/2)(n)$) - postavit nový podstrom trvá $n$ času, ale od jeho poslední přestavby z tohoto vrcholu jsem musel přidat $1/3 n$ vrcholů ⇒ amort - potenciál je součet přes všechny vrcholy $|m(cal(l)(v)) - m(cal(p)(v))|$ - #text(red)[pokud je strom vyvážený, je potenciál 0, ne 1] - použití: k-d stromy, k-d intervaláče? prostě BVS? + Navrhněte operace Find, Insert a Delete na Splay stromu. Analyzujte jejich amortizovanou složitost. Větu o složitosti operace Splay stačí vyslovit, nemusíte ji dokazovat. - *složitost Splay*: $3 dot (r'(v) - r(v)) + 1$, kde $r(v)$ je $log$ mohutnosti vrcholu $v$ před Splay a $r'(v)$ je po Splay - mohutnosti jsou $𝓞(log n)$ - všechny operace můžu naúčtovat Splayi, který je $𝓞(log n)$ - *Find*: Najdu jako v BVS a vysplayuju do kořene - *Insert*: Insetrnu jako v BVS a vysplayuju do kořene - přidáním listu zvýším rank celé cesty a tím i potenciál, ale jen o $𝓞(log n)$ - *Delete*: Vysplayuju do kořene, deletenu, vysplayuju pravého syna levého podstromu + Analyzujte hloubku (a,b)-stromů. - pro hloubku $h$ platí $h in Θ(log n)$ + Analyzujte k-cestný Mergesort v cache-aware modelu. Jaká je optimální volba k? - $log_k n = (log n) / (log k)$ průchodů - každá vrstva je $𝓞(n log k)$ (používáme haldu) - složitost $Θ((n dot log k dot log n) / (log k)) = Θ(n log n)$ - potřebujeme $K$ bloků na jednotlivé průchody a dalších $K$ na udržení haldy, takže $M >= 2 B K$, $K in 𝓞(M/B)$ - IO složitost $𝓞(n/B dot (log n) / (log k)) = 𝓞(n/B dot (log n) / (log (M/B)))$ + Formulujte cache-oblivious algoritmus pro transpozici čtvercové matice. Rozeberte časovou složitost a I/O složitost. - rekurzivní, rozdělíme transpozici na dvě transpozice a dvě kombinované transpozice a prohození - transpozice a prohození se dále rozděluje na čtyři transpozice a prohození - k reálnému swapování dochází pouze na nejnižší úrovni rekurze, každý prvek se swapne jednou, $𝓞(n^2)$ - IO složitost, v určitou chvíli swapujeme a transponujeme dva bloky velikosti $B × B$, pokud je keš velká alespoň $2 dot B^2$ (tall cache assumption, pak se celé takové bločky vejdou do keše a transponuje se dobře, každý blok načteme jen jednou, $𝓞(N^2/B)$ + Popište systém hešovacích funkcí odvozený ze skalárního součinu. Dokažte, že je to 1-univerzální systém ze $ℤ_p^k$ do $ℤ_p$. - $h_v (x) = x v$, vektor $v$ je náhodně generovaný a parametrizuje hashovací funkci - $c$-universálnost: $P_(h in cal(H))[h(x) = h(y)] <= c/p$ - nechť se x a y liší v $d$-tém prvku, $P[x v = y v] = P[(x - y)v = 0]$, bude platit pro právě jednu volbu $v_d$ ⇒ $1/p$ + Popište systém hešovacích funkcí založených na lineární kongruenci. Dokažte, že je to 2-nezávislý systém ze $ℤ_p$ do $[m]$ (můžete využít lemma o modulení, které zformulujte, ale nemusíte dokazovat). - $h_(a,b) (x) = ((a x + b) mod p) mod m$ - $k,c$-nezávislost: $P_(h in cal(H)) [h(x_1) = y_1 and ... and h(h_k) = y_k] = c/m^k$ - *lemma o modulení*: pokud $cal(H)$ je $k,c$-nezávislý systém z $cal(U)$ do $[r]$, pak pro $2 k m <= r$, $cal(H) mod m$ je $k,2c$-nezávislý - výběr $ r = (a x + b) mod p \ s = (a y + b) mod p $ je bijektivní na výběr $a,b$, tedy je i $2$-nezávislý + Sestrojte $k$-nezávislý systém hešovacích funkcí ze $ℤ_p$ do $[m]$. Zdůvodněte k-nezávislost (můžete využít lemma o modulení, které zformulujte, ale nemusíte dokazovat). - $cal(P)_k = {h_t | t in ZZ_p^k}, h_t = sum_(i=0)^(k-1) t_i x^i$ - existuje právě jeden polynom takový, že pro $x_1 ... x_k$ a $y_1 ... y_k$ tž $h(x_i) = y_i$ pro každé $i$, tzn. pravděpodobnost je $1/p^k$ - přes lemma o modulení, pokud $p >= 2 k m$, máme po vymodulení $k,2$-nezávislý systém + Sestrojte 2-nezávislý systém hešující řetězce délky nejvýše $L$ nad abecedou $[a]$ do $[m]$ založený na polynomech, tedy "rolling hash". Popište výhodu použití tohoto systému oproti jiným hešovacím funkcím. - $cal(R) = {h_a | a in ZZ_p}$, $h_a(x) = sum_(i=0)^(L-1) x_(i+1) a^i$ - dá se posouvat v konstantním čase – vynásobím $a$, přičtu příchozí znak, odečtu odchozí znak $dot a^L$ (musím předpočítat $a^L$) + Popište a analyzujte Bloomův filtr. Uveďte příklad jeho praktického použití. - pomocí hashe indexujeme v poli bitů a flipujeme bity nahoru pro prvky, které jsme viděli - pak se můžeme ptát "viděli jsme tenhle prvek?", na což dostaneme buď korektní NE, nebo possibly flase positive ANO - typicky $k$ hashovacích funkcí - také lze mít všechny hashe v jednom poli - s počítadly lze i delete + Definujte k-d stromy a ukažte, že 2-d intervalové dotazy trvají Ω(√n). - pro data z $RR^k$ vytvářím strom, kde na $l$-té úrovni mám medián daných podstromů v dimenzi $l mod k$ - pro ${0}×RR$ to suckuje, pro $x$ jdu furt do leva, ale pro $y$ furt rekurzím do všech + Ukažte, jak dynamizovat dvou dimenzionální intervalové stromy (tedy Range trees), stačí Insert. - pomocí BB[α] stromů, $𝓞(log ^2 n)$ + Ukažte, jak použít sufixové pole a LCP pole na nalezení nejdelšího společného podřetězce dvou řetězců. - concatnu za sebe s pomocí oddělovacího znaku, najdu max v LCP t.ž. jeden je před a jeden je za oddělovačem + Ukažte, jak paralelizovat (a,b)-strom pomocí zámků. - pomocí top-down strategie — preemptivně rozdělujeme/spojujeme už při cestě dolů, abychom vždy mohli udělat Insert nebo Delete - zamykáme vždy dva vrcholy za sebou - při deletu může dávat smysl vždy zamykat nejdřív levého sourozence — pro případ, že s ním budeme slučovat nebo půjčovat - pokud odstraňujeme klíč, který není v nejnižší vrstvě, je možné, že budeme muset dlouho hledat následníka, kdyžtak se dá vrchol označit hrobečkem