Vladan Majerech - NTIN060 Algoritmy a datové struktury
Last Modified: 8.9.2018
Index
zápočtové příklady, odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5, cvičení 6, cvičení 7, cvičení 8, cvičení 9, cvičení 10, cvičení 11, cvičení 12, cvičení 13
Pro získání zápočtu z NTIN060 je potřeba získat (2/3 z možných bodů za domácí úkoly zadávané v průběhu semestru).
Zápočtové příklady
Pokud není uvedeno jinak, počet přidělených bodů rychle klesá v případě použití časově neoptimálních algoritmů.
| Kód | Body | Zadání |
|---|---|---|
| řeka | 10 | Máme mapu úzkého povodí bez ostrovů (strom soutoků zakořeněný v ústí). Na povodí jsou mola (ne nutně na soutocích). Znáte vzdálenosti mezi soutoky (i se vzdálenostmi k molům na každém úseku toku). Popište algoritmus, který zjstí, zda existují dvě mola kde jedno je po proudu od druhého vzdáleno (říční vzdáleností) přesně V. |
| řeka2 | 12 | Máme mapu úzkého povodí bez ostrovů (strom soutoků zakořeněný v ústí). Na povodí jsou mola (ne nutně na soutocích). Znáte vzdálenosti mezi soutoky (i se vzdálenostmi k molům na každém úseku toku). Popište algoritmus, který zjstí, zda existují dvě mola (mohou být na různých přítocích) vzdálená (říční vzdáleností) přesně V. |
| logik | 12 | Popište algoritmus na srovnání dvou stejně dlouhých řetězců čísel. Výsledkem mají být dvě čísla: A) Počet shod včetně pozic B) Za každé číslo na jiných pozicích je započítáno minimum z počtu jeho výskytů v obou posloupnostech. Například pro 1,1,2,3,3;1,3,3,1,1 dostaneme A:1 B:3 (min(1,2)+min(1,0)+min(2,2)). Jak délka řetězců N, tak množina M použitelných čísel jsou velké (M nezáporné menší než $2^{64}$, zvládněte to i pokud máte k dispozici jen $\Theta(N)$ paměti?). |
| rekur | 10 | Zjednodušte popis funkce $t$ (stačí $\Theta(t)$) dané následující rekurencí: $t(n)=2t(\lceil\sqrt n\rceil)+c$, pro $n\ge 3$ a kde $t(n)=n$ pro $1\le n\le 2$. |
| rekur2 | 10 | Zjednodušte popis funkce $t$ (stačí $\Theta(t)$) dané následující rekurencí: $t(n)=t(\lceil\sqrt n\rceil)+c$, pro $n\ge 3$ a kde $t(n)=n$ pro $1\le n\le 2$. |
| perm2n | 5 | Pro danou permutaci čísel od $1$ do $K$ nalezněte její „abecední“ pořadí mezi všemi takovými permutacemi (předpokládejte, že máte aritmetiku s dostatečně velkými čísly). |
| n2perm | 5 | Nalezněte permutaci která je mezi permutacemi čísel od $1$ do $K$ na daném $n$ tém „abecedním“ pořadí (předpokládejte, že máte aritmetiku s dostatečně velkými čísly). |
| permBi | 10 | Algoritmicky popište zobrazení a k němu inverzní zobrazení, mezi čísly od 1 do K! a permutacemi čísel od 1 do K (předpokládejte, že máte aritmetiku s dostatečně velkými čísly). |
| lavl | 12 | Ukažte, jak je možno z libovolného binárního stromu vytvořit AVL strom (zachovávající inorder pořadí) v lineárním čase a ukažte, že rychleji to nejde. |
| medián | 10 | Je dán „komprimovaný“ seznam čísel. Nalezněte jejich medián. Komprimace spočívá v tom, že místo čísel dostáváme dvojice čísel, kde první udává hodnotu a druhé počet výskytů dané hodnoty v nekomprimované posloupnosti (stejná hodnota může být ve více dvojicích, dokonce ani není zakázáno její použití v ihned následující dvojici). |
| rbt | 8 | Nakreslete posloupnost červenočerných stromů, odpovídající provedením následujících operací (uváděny pouze klíče) nad prázdným stromem: insert(6), insert(4), insert(2), insert(1), insert(3), delete(6), delete(4). |
| Id studenta | celkem | rozpad bodů |
|---|---|---|
| A | 84 | řeka(8), řeka2(9), logik(10), rekur(10), rekur2(10), perm2n(4), n2perm(4), permBi(7), medián(10), lavl(12) |
| B | 83 | řeka(8), logik(10), rekur(10), rekur2(10), perm2n(5), n2perm(5), permBi(10), lavl(12), medián(5), rbt(8) |
| C | 71 | řeka(6), logik(12), řeka2(8), rekur(10), rekur2(10), perm2n(5), n2perm(3), permBi(7), medián(10) |
| D | 73 | řeka(8), řeka2(8), logik(10), n2perm(4), perm2n(4), permBi(7), rekur(10), rekur2(10), lavl(12) |
| E | 81 | logik(10), lavl(12), rbt(8), n2perm(3), perm2n(3), permBi(6), rekur(10), rekur2(10), řeka(10), řeka2(9) |
| F | 74 | řeka(8), rbt(8), lavl(12), rekur(10), rekur2(10), řeka2(9), medián(5), n2perm(3), perm2n(3), permBi(6) |
| G | 73 | řeka(8), řeka2(9), rekur(10), rekur2(10), lavl(12), rbt(8), medián(7), logik(9) |
| H | 70 | řeka(10), řeka2(9), perm2n(1), lavl(12), rbt(8), rekur(10), rekur2(10), logik(10) |
| I | 70 | rbt(8), perm2n(3), medián(4), řeka(10), řeka2(3), rekur(10), rekur2(10), logik(10), lavl(12) |
| J | 70 | rbt(8), rekur(10), rekur2(10), lavl(12), logik(9), n2perm(4), perm2n(4), řeka(8), řeka2(5) |
| K | 61 | řeka(6), logik(10), lavl(11), perm2n(3), n2perm(3), rekur(10), rekur2(10), rbt(8) |
| L | 71 | rbt(8), řeka(6), lavl(12), medián(7), logik(10), perm2n(4), n2perm(4), permBi(6), rekur(10), rekur2(10) |
Odkazy na obdobné stránky
Cvičení Jirky Švancary, Cvičení Miloše Chromého, Cvičení Veroniky Slívové, Texty k cvičení Jana Hrice, Cvičení Petra Kučery, Cvičení Jakuba Svobody, Cvičení Jany Syrovátkové, Cvičení Jakuba PekárkaCvičení 1
Na prvním cvičení jsem rozáhle mluvil o tom, že při reportování nároků výpočtu můžeme dostávat různé výpočty pro jednotlivé vstupy,
v tom případě můžeme průměrovat tyto výsledky přes pravděpodobnosti výstupů náhodného generátoru (randomizovaná složitost)
či můžeme vzít maximum (worst case v randomizovaném rozměru). (bez příkladu)
Výsledky reportujeme v závislosti na velikosti vstupu,
zde můžeme opět průměrovat přes pravděpodobnosti jednotlivých vstupů (průměrná složitost vzhledem k rozložení vstupů)
či můžeme vzít maximum (worst case v rozměru průměrování pro danou velikost vstupu).
(Příklad třídění startovních čísel vybraných v cíli závodu kde závodníci startují s rostoucími čísly s konstantními rozestupy.)
V případě datových struktur použitých v nějakém algoritmu se navíc hodí popis datové struktury který nám na základě počtu
vyvolání jednotlivých metod dokáže odhadnout celkové nároky práce s datovou strukturou (amortizovaná složitost).
(Příkladem bylo zdvojnásobování velikosti pole pro reprezentaci prodlužovaného seznamu, kde nejpomalejší operace jsou lineární,
ale celkový čas práce se strukturou bude stále jen lineární.)
Tyto rozměry mohou být kombinovány a můžeme tak dostat v extrémním případě průměrnou randomizovanou amortizovanou složitost,
kde průměrujeme přes pravděpodobnosti posloupností použitých metod (včetně parametrů).
Nároky nevyjadřujeme přesně, ale používáme $O$, $o$, $\Theta$ notaci. Přitom píšeme např. $2n+7\in O(n)$, protože $O(n)$
není jedna funkce, ale množina funkcí. Pojmy $\omega$ a $\Omega$ nepotřebujeme, protože $f\in O(g)\equiv f\not\in\omega(g)$ a obdobně
$f\in o(g)\equiv f\not\in\Omega(g)$.
Užitečná je alternativní definice těchto pojmů pomoci $\overline{\lim}_{n\to\infty} f(n)/g(n)$.
Taky jsem se zmínil o implementační složitosti, která nás v akademickém světě příliš netrápí, ale v praxi bývá důležitá.
Ve zbytku cvičení jsem se věnoval prohledávání do šířky a hloubky na úloze kde skutečně hledáme cíl.
Srovnal jsem výhody těchto prohledávání a prohledávání do šířky příliš výhod nemělo.
Základní výhodou prohledávání do hloubky je jeho lokalita pohybu umožňující aktualizace globálních informací.
Výhodu prohedávání do šířky ve smyslu nalezení nejkratší cesty je možno eliminovat iterativním prohlubováním.
(To by bylo extrémně neefektivní u velkých grafů s malými stupni vrcholů, ale u pravidelných grafů s velkými stupni vrcholů roste
exponenciálně velikost grafu dosažitelného v daném počtu kroků, tedy časy jiných než posledních dvou iterací jsou zanedbatelné.)
Problém jsem prezentoval na hledání cesty na implicitním grafu rubikovy kostky mezi daným a složeným stavem kostky.
Program by žádnou z uvedených metod nedopočítal.
Prohledávání do šířky i do hloubky by rychle došla paměť, iterativnímu prohlubování by došel čas.
Ale pomohlo by zavedení heurstického odhadu počtu nutných tahů k dosažení cíle.
Jeden takový odhad tabulováním pozic rohů a vybrané šestice hran jsem zmínil. S ním již program doběhne v rozumném čase.
Cvičení 2
Na druhém cvičení jsme si hráli s prohledáváním do hloubky neorientovaného grafu. Definovali jsme stromové a zpětné hrany, preorder a postorder pořadí a zadefinovali jsme si i low hodnoty. Ukázali jsme si, jak detekovat komponenty souvislosti, ale pomocí low hodnot i rozklad vrcholů grafu do mostových bloků a rozklad hran do bloků vrcholové dvousouvislosti (Ověřili, že ne nutně mají všechny vrcholy mostového bloku stejnou low hodnotu. Most $(u,v)$ má $low(v)=preorder(v)$ a artikulace je buď kořen prohledávání s více stromovými hranami nebo nekořen s $low(v)=preorder(v)$. Při detekci rozhraní můžeme vysypat blok nad rozhraním z pomocného zásobníku). Jako zapomněnku jsem naznačil, že dvojím prohledáváním do hloubky s použitím i low2 hodnot je možno vnořovat graf do roviny (je-li rovinný). Všechny tyto algoritmy pracovaly v čase $O(m+n)$, kde $m$ je počet hran a $n$ počet vrcholů. Na konci cvičení jsme přišli na to, jak prohledáváním do hloubky najít nejvzdálenější dvojici vrcholů v stromě s hranami ohodnocenými celými čísly.
Cvičení 3
Na třetím cvičení jsme si povídali o výpočetních modelech. Zasekli jsme se jak na složitosti aritmetických operací, tak na složitosti adresace. Zabývali jsme se složitostí násobení čísel a společně jsme vymysleli násobení $n$-ciferného čísla v čase $O(n^{\log 3})$. Tedy dospěli jsme k rekurenci s 3mi násobeními čísel zhruba poloviční délky a řešení rekurence jsme neprověřovali. Pak jsem naznačil, že se znalostí algebry je možno násobení polynomů řešit převodem ze světa koeficientů polynomů do světa funkčních hodnot polynomů ve vhodných bodech a zpět. Při volbě bodů na pravidelném $2^m$ úhelníku vychází převod všech $2^m$ bodů celkově v čase $O(2^m\cdot m\cdot \log^c m) $. Trikem je organizace výpočtu tak, aby výpočty sdílely velké části mezivýsledků. To symetrie $2^m$ úhelníku umožňuje. Člen $\log^c m$ ohodnocuje složitost primitivních operací v modulární aritmetice vhodně zvoleného prvočísla (věříme že existuje). Ve výsledku je tedy možno $n$ ciferné násobení implementovat v čase $O(n\log n\log^c\log n)$.
U složitosti adresace je často používán logaritmus adresy. V našem fyzikálním světě bychom měli brát za složitost „náhodné“ adresace spíš třetí odmocninu. Protože v čase $t$ nemůžeme adresovat větší prostor než $c{4\over3}\pi t^3$ (kde $c$ je rychlost světla). V běžných odhadech složitosti algoritmů jsou tyto nejednotkové ceny jednotlivých operací komplikací, kterou se nebudeme zbytečně trápit. V posledních minutách cvičení jsem dal motivační příklad na vyhodnocení pozice ve hře logik/master-mind. Na rozdíl od běžného provedení zde uvažujme dlouhé posloupnosti na vstupu s hodně velkým možstvím přípustných barev. (Zde by nejspíš penalizace za adresaci mohla hrát významnou roli.)
Cvičení 4
Cvičení začalo nevinnou zmínkou o BFS. Chtěl jsem povědět jedinou aplikaci BFS, kterou znám, a tou je věta o planárním separátoru, tedy to, že roviný graf je možno v lineárním čase rozdělit na dva podgrafy, jejichž průnik je velikosti $O(\sqrt n)$ a hrany neopouštějí jednotlivé podgrafy. Navíc s podmínkou na to, že podgrafy musí mít každý nejvýš $2n/3$ vrcholů.
Nezbylo mi než začít s motivací k větě, tedy k povídání o rozděl a panuj. Napsal jsem řešenou rekurenci $t(n)\le cn^\alpha+\sum t(a_in)$ (okrajovou podmínku jsem zmínil jen ústně). Pak jsme si s rekurencí chvilku hráli. Zmínil jsem analogii s integrováním per partes v rozdělení výpočtu na hotové a rozpracované. V našem případě měla každá z těchto částí natolik homogenní strukturu, že nebylo potřeba psát příliš písmen a stačilo posčítat hotové. Jednotlivé řádky tvořili geometrickou posloupnost, takže při kvocientu $S=\sum a_i^\alpha<1$ byl součet konečný a dostali jsme $O(n^\alpha)$. V případě kvocientu $S=1$ jsme potřebovali odhadnout počet pater rekurence a vyšlo nám $O(n^\alpha \log n)$. V případě kvocientu $S>1$ jsem převedli úlohu na předchozí případ a hledali jsme $\beta$, pro nějž je $\sum a_i^\beta=1$. Pak je řešením $O(n^\beta)$. Vypozorované odhady je nejlépe dokázat matematickou indukcí.
P.S.: Homogenní řešení rekurence bylo $c_1n^\beta$, pravé straně odpovídalo $c_2n^\alpha$. Řešení bylo tedy ve tvaru lineární kombinace $n^\beta$ s $n^\alpha$, nás zajímá větší z nich. V případě, kdy je $\alpha=\beta$, dostáváme „dvojnásobný kořen“ a jako druhé řešení $c_2n^\alpha \log n$.
Ukázali jsme použití principu věty na quisksortu, věty tak jak je na mergesortu a Strassenově algoritmu násobení matic. I u Strassenova algoritmu jsme si pohráli se značením, využili jsme toho, že používáme lineární kombinace podmatic poloviční velikosti, kde jsou použity koeficienty jen +1,0,-1, navíc se stejnou podmaticí jsme používali vždy stejné znaménko. Místo nul jsme nechávali prázdné místo, stačilo nám tedy zapisovat jen znaménka. Výsledné matice poloviční velikosti jsme získali sčítáním resp. odčítáním po řadě 4, 4, 4 a 2 součinů matic poloviční velikosti. Trik byl ale v tom, že součiny jsme recyklovali a stačilo jich počítat jen 7. Časová složitost byla tedy $O(n^{\log_2 7})$.
Na konci hodiny jsem se konečně vrátil k větě o planárním separátoru. Naznačil jsem, jak pomocí BFS vytvořit 2 „horizontální“ řezy velikosti nejvýš $\sqrt n$. Tyto řezy jsou od sebe vzdáleny nejvýš $\sqrt n$. Bohužel oblast mezi nimi může být příliš velká, takže je potřeba i v ní najít řez. K tomu již prohledávání do šířky nepomůže a musíme použít několik prohledávání do hloubky. Dvě z nich jsou potřeba k rovinnému nakreslení grafu (pokud nebylo součástí zadání), pak je potřeba dotriangulovat a na triangulaci dalším prohledáváním nalézt příčku v původní BFS kostře, kde vnitřek i vnějšek kružnice obsahuje dostatečný počet vrcholů (ve skutečnosti prohledáváme do hloubky duální kostru). Celkový separátor bude velikosti nejvýš $4\sqrt n$. Odddělené části je potřeba posjednocovat do dvou tak, aby žádná nebyla větší než $2n/3$. To ale není problém. Na větu o planárním separátoru jsem si nechal jen tak málo času, aby bylo jasné, že je to složité a že bez prohledávání do hloubky si nepomůžeme. Cílem nebylo větu dokázat, pouze ukázat cestu, kterou se vydat.
Cvičení 5
Na pátém cvičení jsme probírali algoritmy na hledání délek nejlacinějších sledů v grafu. Dijkstra, který zvládá sledy z jednoho vrcholu do ostatních v nezáporně ohodnoceném grafu. Bellman Ford, který zvládá totéž ale i v grafu bez záporných cyklů. V případě záporných cyklů si můžeme pomoci „skokem do $-\infty$“. Floyd Warshall, který zvládá sledy ze všech vrcholů do všech i v případě existence záporných cyklů.
Zmínili jsme se o použití datových struktur pro Dijkstru a s předpokladem znalostí amortizovaného rozboru pak dostali složitost $O(m+n\log n)$. U Bellman Ford jsme si dokázali, že algoritmus dělá co má dělat. Stačí si s triviálními datovými strukturami, ale jeho čas je $O(mn)$. Floyd Warshall též komplikované datové struktury nepotřebuje a dosahuje času $O(n^3)$, pouze jsem se zmínil o možnosti odstraňování řádků či sloupců z mezivýsledků, pokud by nás ne úplně všechny vzdálenosti zajímaly (a o optimalizaci pořadí zpracování s tim související).
Ve zbytku hodiny jsem jako zapomněnku zmínil principy odvození Fibonacciho hald (potřebných pro Dijkstru). K úplným detailům implementace FindMin či Decrement jsme se nedostali.
Cvičení 6
Na šestém cvičení jsme se věnovali algoritmům na hledání minimální kostry. Nejprve jsem naznačil (bez důkazu), že existuje „nedeterministické“ barvící schéma pro hledání minimální kostry a u probíraných algoritmů jsme pak vždy ukazovali, že přidání hrany do kostry ospravedlňuje modré pravidlo a zahození hrany červené.
U Kruskalova algoritmu jsme se dále zabývali datovou strukturou potřebnou pro rozhodnutí o tom, jakou barvu použít. Vyšlo nám DFU (disjoint find union). Popsali jsme si implementaci se size a rank heuristikami pro union a compress, split a halve heuristikami na zkracování prohledávaných cest. Naznačil jsem bez důkazu, že samotné zkracování cest libovolnou z uvedených metod vede k amortizované složitosti $O(\log n)$. Dokázali jsme, že obě uvedené union heuristiky bez zkracování cest vedou k worst case složitosti $O(\log n)$. Naznačil jsem, jak vypadá Ackermanova funkce a k ní inverzní funkce $\alpha$ a bez důkazu jsem naznačil amortizovanou složitost $O(\alpha(n))$ na libovolnou jednu operaci při libovolné kombinaci uvedených union a compress heuristik. Naznačil jsem taky, že při backtrackingu je výhodnější používat split či halve než compress což pak vede při správné evidenci platností hran k složitosti $O(\log n/\log\log n)$ místo $O(\log n)$.
Pak jsme se věnovali Prim/Jarník/Dijkstra algoritmu na hledání minimální kostry. Vzhledem k tomu, že jsme Dijkstrův algoritmus probírali minule, všimli jsme si, že odlišnosti jsou minimální a dostali jsme s použitím Fibonaccioh hald stejnou složitost $O(m+n\log n)$.
Uvědomili jsme si ale, že nelinearitu složitosti nese jen logaritmus velikosti haldy při provádění DeleteMin. To vedlo k FredMan-Tarjan algoritmu, kdy jsme se rozhodli zavést treshold pro maximální velikost haldy $2^{2m/n}$. Díky tomu vyjde složitost jedné fáze algoritmu $O(m+n\log 2^{2m/n})\subseteq O(m)$. Nevýhodou je, že při uplatnění tresholdu nekončí fáze spočítanou kostrou, ale pouze spočítanými podstromy kostry. Lexikografické třídění hran podle čísel podstromů, do nichž patří koncové vrcholy hrany zvládáme v $O(m)$ a umožní to hromadně aplikovat červené pravidlo a nadbytečné hrany odstranit. Můžeme pak znovu pustit algoritmus, kde roli původních vrcholů hrají podstromy spočtené v předchozí fázi. Ukazuje se (nedělal jsem), že to umožňuje použít treshold $t_{i+1}\ge 2^{t_i}$ pro další fázi. Ve chvíli, kdy je treshold dostatečně velký, nekončí výpočet dosažením tresholdu, ale dopočítáním celé kostry. Určitě stačí, když je $t_i>n$. Což vede k hornímu odhadu na počet fází a po pronásobení $O(m)$ na odhad celkového času algoritmu.
Cvičení 7
Na sedmém cvičení jsme řešili jednoduché příklady: Lámání čokolády (odfiltrování nepodstatného), krájení kvádru (opět neřešení nepodstatného), házení speciálních vajíček (dospěli jsme ke vzorci $\sum_{i=0}^{v} {h \choose i}$), nejdelší úsek v posloupnosti kladných čísel s daným součtem, největší čtverec dané barvy (v $O(w\cdot h)$ s použitím součtů přes obdélníky z fixního rohu, testujeme rostoucí velikosti čtverců). Na rozmyšlenou jsem dal úlohu na co nejefektivnější vysvobození dvou robotů z bludiště za použití synchronizovaných povelů (kde právě neproveditelné jsou ignorovány).
Cvičení 8
Na začátku osmého cvičení jsme se dále věnvali jednoduchým úlohám. (Dvojice robotů a obdoba v pronásledující příšeře, hledání cyklu obsahujícího zelený vrchol v orientovaném grafu, kdy existence mostu garantuje existenci artikulace, zjišťování počtu nejkratších cest v grafu s jednotkovými hranami, jak ovlivní přičtení konstanty k ceně každé hrany nejlacinější sledy a jak minimální kostru v grafu)
Jak spočíst $k$-té Fibonacciho číslo pro velké $k$ jsme řešili tuším už minule. Nikdo tehdy nenavrhoval neefektivní rekurenci, objevil se návrh s postupným počítáním od nejmenších prvků. Zazněla souvislost s explicitní formulí se zlatýmí řezy související s hledáním řešení ve tvaru lineární kombinace geometrických posloupností, dosazením geomerické posloupnosti do rekurence a vykrácením získáme kvadratickou rovnici a oba její kořeny (zlaté řezy) jsou příslušnými kvocienty. (Obecně jsou příslušné geometrické posloupnosti doplněny jejich násobky polynomy stupně menšího než je násobnost, tak abychom měli tolik funkcí, kolik je stupeň rovnice.) Nevýhoda této explicitní formule je, že pracuje s iracionálními čísly (odmocnina z 5) proto je vyhodnocení náročné na aritmetiku. Efektivnější je popsat transformaci z $(F_{i-1},F_i)$ na $(F_i,F_{i+1})$ jako násobení jednoduchou maticí. Vícenásobnou aplikaci transformace je možno vyhodnotit tak, že nejprve umocníme transformační matici. Výpočet touto metodou si vystačí s celými (nezápornými) čísly a také vyžaduje $O(\log k)$ kroků. (A hádejte, jaká jsou vlastní čísla (a charakteristický polynom) příslušné matice ... již byly definovány na Lineární algebře?).
Ke konci hodniny jsme se věnovali AVL stromům. Oddělil jsem otázku vyhledávacích stromů od AVL vyvažování v stromech reprezentujících inorder pořadí. Ukázali jsme si že minimální velikost AVL stromu hloubky $h$ úzce souvisí s Fibonacciho posloupností. Hloubka AVL stromu je tedy logaritmická (o základu zlatý řez). Pak jsem se zmínil o počtu rotací a aktualizací vyvažovací informace během insert a delete operací. (Rotací je $\Theta(1)$ u insert, jinak je všeho $\Theta(\log n)$.) Vyvažování souvisejcí Insert prvku do AVL vyváženého stromu jsme na konci hodiny stihli rozebrat. K delete jsme se nedostali.
Cvičení 9
Na devátém cvičení jsme se opět věnovali rozděl a panuj, tentokrát už po probrání na přednášce jedné z paralelek. Nejprve jsme si připoměli, jaké je tvrzení věty. Přitom jsem opět odbočil k obecným řešením méně obecných rekurenčních rovnic, abych naznačil, že existuje prostor řešení homogenní rovnice a po kombinaci s jedním řešením pravé strany dostáváme všechna řešení. Naznačil jsem, že stejně se chová i master theorem, jen si nevšímáme asymptoticky nevýznamných členů. Pak jsme probírali různá použití master theoremu. První bylo hledání mediánu a rekurence pro algoritmus, kde pivota hledáme jako medián mediánů k-tic. Pro $k=3$ vyšel čas $\Theta(n\log n)$, pro $k=5$ vyšel čas $\Theta(n)$.
Pak jsem předvedl Kirkpatrick-Seidel algoritmus na hledání konvexního obalu. Tam se rozděl a panuj použilo 4 krát. Jednou na hledání mediánové souřadnice ve vnějším programu, pak pro celkovou rekurenci skládání konvexního obalu z jednotlivých úseků. Dále na hledání mediánového směru v algoritmu hledání horního mostu (úseku konvexního obalu protlého danou polopřímkou). Nakonec při spočtení celkového času hledání horního mostu. Všechna použití jsou něčím výjimečná. Hledání mediánu (obou) tím, že díly, na které rozkládáme původní problém nejsou stejně velké, navíc nejprve musíme vyřešit první z nich, abychom mohli sestavit druhý díl. Rekurence při hledání horního mostu je výjimečná tím, že úlohu voláme na menší zadání jen jednou (prune and search). Celková rekurence je výjimečná tím, že použítím tvrzení věty bychom dokázali pouze čas $O(n\log n)$, dokázat čas $O(n\log h)$, kde $h$ je počet úseček tvořících konvexní obal vyžaduje podívat so dovnitř do jejího důkazu.
Cvičení 10
V souvislosti s domácími úkoly jsme se na desátém cvičení věnovali příkladu nalezení $n$-tého dle velikosti součtu $a_i+b_j$, kde $a_1\le\dots\le a_n$ a $b_1\le\dots\le b_n$.
Cvičení 11
Na jedenáctém cvičení jsme si povídali o červenočerných stromech. Zdůraznil jsem, že není důležité, zda jsou použité jako vyhledávací, že hlavní je způsob vyvažování.
Upozornil jsem na nešťastnost používat nestandardní pojmy v definici (neexistující vrcholy mají význam v definici). Přefurmulovali jsme invariant černé hloubky pomocí stejné černé délky cesty do nil pointerů. Červený invariant ... nemohou být dva červené pod sebou.
Pak jsme se zabývali maximální možnou hloubkou červenočerného stromu (minimální možnou velikostí při dané hloubce). Vyšlo nám, že hloubka je nejvýš logaritmická, ale v tomto případě o základu $\sqrt 2\approx 1.414$ na rozdíl od základu zlatý řez $q=(1+\sqrt 5)/2\approx 1.618$ pro AVL stromy. Červeno-černé stromy jsou tedy v nejhorším případě hlubší.
Pro struktury s velkým relativním počtem vyhledávání vůči počtu modifikací resp. počtu delete vycházejí AVL stromy nepatrně efektivněji (poměr logaritmů je $\approx 1.388$). Standardní implementace červeno-černých stromů si jak při insert, tak při delete vystačí s konstantním počtem rotací. AVL stromy potřebují při delete až $\Omega(\log n)$ rotací. Standardní implementace v obou případech při vyvažování změní v až $\Omega(\log n)$ vrcholech vyvažovací informace, takže zde není jednoznačný vítěz. Pokud udržujeme informace o barvách v červenočerném stromě implicitně pomocí rozkladu na cesty, je možno implementovat červeno černé stromy tak, že aktualizace provádí pouze pouze $O(1)$ rotací a vytváří pouze $O(1)$ změn v implicitní evidenci barev. Pokud chceme verzovat stavy binárního stromu, vyjdou v takovémto případě červenočerné stromy asymptoticky lépe.
Nakonec jsme se bavili o vyvažování po insertu, jehož standardní verzi jsme dali dohromady. Proaktivní verze, která při vyhledávání (když nemáme přímý odkaz na vrchol) přebarvuje po cestě dolů, aby bylo jednodušší vyvažování směrem nahoru, zůstala nedořešena. Vytváří až $\Omega(\log n)$ červených konfliktů? Vede k až $\Omega(\log n)$ rotacím? Standardní verze vede k nejvýš jedné rotaci.
Delete jak AVL stromů, tak červeno černých stromů jsme stále ještě neprobrali.
Cvičení 12
Na dvanáctém cvičení jsme doprobrali vyvažování jak AVL, tak červenočerných stromů při delete.
Cvičení 13
Na posledním cvičení jsme probírali domácí úlohy a řešili hádanky o vězních.