Vladan Majerech - NTIN060 Algoritmy a datové struktury 1

Last Modified: 28.3.2025

Valid HTML 4.01 Strict

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

Zápočtové příklady

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).

Pokud není uvedeno jinak, počet přidělených bodů rychle klesá v případě použití časově neoptimálních algoritmů. Za úkoly odevzdané po termínu je možno získat jen poloviční počet bodů. Termínem je vždy 10:40 v datum cvičení (tedy čas začátku cvičení), mezi dnem stanovení termínu a termínem je vždy přinejmenším jedno cvičení (výjimky obou pravidel možná budou na konci semestru). U některých úloh nemusí být nastaven termín, zvláště pokud navazují na dosud neprobranou látku. Dokud nacházíte lepší řešení, můžete úlohy odevzdávat opakovaně, o již získané body tím nepřijdete. Na domácí úkoly použijeme owl. Pokud jste ode mne nedostali e-mail s linkem, tak mne kontaktujte.

Odkazy na obdobné stránky

moje loňské cvičení, texty k cvičení Jana Hrice,

Cvičení 1

Bohužel se mi nepodařilo zprovoznit mikrofon, takže z hodiny není záznam. Na cvičení jsem oznámil podmínky zápočtu, pak jsem v podstatě celou hodinu budoval oslí můstek k zadání prvního domácího úkolu.

Začali jsme motivací k technikám rozděl a panuj ve formě Kirkpatrick-Seidel algoritmu na hledání konvexního obalu. Jednalo se o nestandardní použití rekurence, kterou neumíme napasovat na plánované tvrzení, ale jsme schopni vyřešit technikou použitou v důkazu tvrzení. Kromě hlavní rekurence poskytuje algoritmus i vedlejší rekurenci zvláštní tím, že jde o rozklad na jediný podproblém (technika prune and search na hledání průniku konvexního obalu s předem zvolenou polopřímkou) a dvakrát rekurenci, kde je problém pouštěn na dvě různě velké části (hledání mediánu). Ukázali jsme si dvě téměř stejné implementace algoritmu na hledání mediánu ($k$-tého z $n>k$ prvků) pomocí volby pivota jakožto aproximace mediánu na základě vhodně zvolené podmnožiny zadání. Vhodnou volbu parametrizace jsme byli schopni zvolit až na základě znalosti tvrzení.

Ve zbylé půlhodině jsme zformulovali rozumně obecnou formu rekurentního odhadu času algoritmu $t(n)\le cn^\alpha+\sum_{i=1}^k t(a_in)$, s počáteční podmínkou $t(n)\le C$, pro $n\le n_0$ (vhodnou jak pro prune and search, tak mediánovou rekurenci). Nebyl čas na seznámení se s rekurencí, takže jsem rovnou přešel k proslovu o efektivitě zápisu (odbočkou přes zapomínání neintegrovaných členů při několikanásobném integrování per partes a o správné(myšleno efektivní) organizaci zápisu) a rozdělili jsme výpočet na část s $cn^\alpha$ a na části s $t$, které je ještě potřeba rozepsat. Studenti krásně spolupracovali jak v tvorbě komprimované notace, tak v jejím použití. Homogenita zápisu v každé části nám umožnila nepsat zbytečně mnoho symbolů a věnovat se místo toho podstatě problému.

Ukázalo se, že stěžejní je hodnota $S(\alpha)=\sum a_i^\alpha$. Pokud je $S(\alpha)<1$, vyjde bez uvažování počáteční podmínky $t(n)=cn^\alpha/(1-S(\alpha))\in O(n^\alpha)$ (případ jak prune and search tak druhé mediánové rekurence), pokud je $S(\alpha)=1$, tak s uvažováním počáteční podmínky, ale bez zohledňování konstanty $C$ v odhadu, vyjde $t(n)\in O(n^\alpha\log n)$ (případ první mediánové rekurence) a pokud je $S(\alpha)>1$, existuje $\beta>\alpha$ pro něž je $S(\beta)=1$ a $t(n)\in O(n^\beta)$ (příklad algoritmu uvidíme příště).

Zdůvodnění, pro případ $S(\alpha)>1$ se součtem geometrické posloupnosti chyb odhadu byla trochu magie, ale i kvůli zohlednění konstanty $C$ v počáteční podmínce je vhodné všechny odvozené výsledky zkontrolovat například „matematickou indukcí“. Můžeme to vnímat tak, že jsme nic nedokázali, ale získali jsme velmi dobrou představu o tom, jaké tvrzení bychom měli dokazovat.

Do konce hodiny jsem ještě jsem stihnul naznačit, že matematickou indukci nemusíme dělat pro krok z $n$ na $n+1$, ale mnohdy se hodí dokazovat tvrzení „platí tvrzení pro všechna $n\le n_1$“ a dokazujeme jakožto indukční krok „platí tvrzení pro všechna $n\le n_1+1$“ (stačí se koncentrovat jen na $n_1+1$). V podstatě se jedná o formulaci neexistuje nejmenší $n$ pro nějž by tvrzení neplatilo. V našem případě je vhodné dokazovat tvrzení existují vhodné konstanty (nezávislé na $n$) pro které je $t(n)$ v daném tvaru a v průběhu důkazu zjistit omezení, které konstanty musí splňovat, aby to vyšlo.

Na začátku přestávky jsem ještě zmínil, jak bychom museli modifikovat techniku důkazu, abychom dostali odhad hlavní rekurence Kirkpatrick-Seidel algoritmu (neznámé $h$ omezuje počet vrcholů stromu rekurence a největší součet dostaneme při vyváženém stromu jehož hloubka bude $\log_2 h$).

Příště budeme řešit nějakou hádanku, řekneme si něco o lineárních rekurenčních (ne)rovnicích a ukážeme další aplikace výše uvedené rekurence.

Cvičení 2

Nejprve jsme řešili vajíčkový problém. Na něm se ukázalo, že u pomalu rostoucích funkcí je mnohem efektivnější kódovat relaci „jsem nejvýš hodnota funkce“ pomocí funkce vyjadřující závislost minimálního parametru, pro nějž se daná hodnota nabývá. pro takový komprimovaný popis je mnohdy mnohem jednodušší najít rekurentní vztah. V našem případě šlo o rekurenci známou z Pascalova trojúhelníku, jen jsme si museli uvědomit odlišnost v počátečních podmínkách, ale i to, jak se projeví změna o jedna v počátečních podmínkách. Výsledný vzorec pak už nebylo těžké odvodit. Jakýkoli algoritmus prohledávání stavu úlohy s touto abslutně přesnou heuristikou pak dává optimální řešení úlohy (heuristiky bývají nepřesné, ale to asi není definiční vlastnost, takže absolutně přesná haeristika snad není protimluv).

Následně jsme stejnou techniku použili na odhad hloubky AVL stromu. Vyšla nám rekurence velice podobná rekurenci Fibonacciho posloupnosti. To byl oslí můstek k řešení lineárních difernečních rovností. Ukázali jsme si, jak je možno v případě, kdy rozdíly v indexech jsou celá čísla popsat homogenní rekurenci v maticové formě. A jak pomocí toho počítat $n$-tý člen posloupnosti pomocí $O(\log n)$ sčítání a násobení (rychle rostoucích čísel). Naznačil jsem, že vlastní čísla matice můžou pomoci k analytickému vyjádření $n$-tého členu posloupnosti. K hledání vlastních čísel matice se často používá charakteristický polynom, který v našem případě můžeme získat nezávisle na maticovém řešení rekurence přímo z předpokladu, že řešením rekurence je geometrická posloupnost krát polynom. Součástí hypotézy je, že je-li v řešení násobení polynomem řádu $k$, tak stejná geometrická posloupnost násobená polynomem menšího řádu je taky řešením, takže jsme goemetrické posloupnosti detekovali pro případ konstant(ních polynomů). Analytický tvar řešení naráží na reprezentaci algerbaických čísel, která nemusí být racionální, při vyhodnocování je pak potřeba velice přesně hlídat aby rozsah kumulované chyby nepřesáhl toleranci (v našem případě, abychom se nedostali blíže k nesprávnému přirozenému číslu). (Matice můžeme použít k přesné realizaci v rekurenci potřebných algebraických čísel, čímž bychom se jinou cestou dostali k maticové formě řešení rekurence).

V případě nalezení tolika nezávislých homogenních řešení, kolik je hodnot nutných k určení posloupnosti, nám soustava lineárních rovnic umožní najít lineární kombinaci homogenních řešení, která se shoduje s požadovanou posloupností. V případě nehomohenity ve tvaru polynom krát geometrická posloupnost hledáme řešení ve tvaru, kde stupeň příslušného polynomu homogenního řešení stoupne o 1+stupeň polynomu řešení nehomogenního.

V případě, kdy rozdíly indexů nejsou celá čísla, nejde maticový tvar použít, a charakteristická rovnice (stále stejná hypotéza) není polynom. Nicméně v absolutní hodnotě největší (reálný) kořen charakteristické rovnice nám stále dává dobrou představu o chování řešení „diferenční rovnice“. Což po substituci argumentu funkce (exponenciální resp. logaritmická) vede k jinému náhledu na řešení rekurence z minulé hodiny.

Plánoval jsem taky probrat Strassenův algoritmus, ale nezbyl nám na to čas.

Cvičení 3

První půlhodinu jsme strávili ukázkou rekuretního algoritmu na násobení matic v čase $\Theta(n^{\log_27})$.

Pak jsme si povídali o prohledávání grafů. Připomněli jsme si prohledávání do šířky i do hloubky, uvědomili jsme si jejich problémy při prohledávání velkých (implicitních) grafů. Ukázalo se, že mnohdy je nejlepší kombinovat je pomocí iterativního prohlubování. Taky se hodí heuristický (dolní) odhad zbývající vzdálenosti.

Cvičení 4

Nejprve jsme si ukazovali užitečnost zpracování informace z podstromů v postorder pořadí DFS. Bylo to na příkladě určování extrémní vzdálenosti v podstromě s cenami vah obsahujícími jak kladná tak záporná čísla. Pak jsme si hráli jak s preorder tak postorder číslováním, klasifikovali jsme hrany jak prohledování neorientovaného, tak orientovaného grafu. Pak jsme definovali low hoddnotu a ukázali, jak ji v postorder pořadí počítat. Pak jsme si „připomněli“ co je vrcholová a co hranová dvousouvislost, ukázali, jak nacházet mosty či artikulace pomocí DFS (a low hodnot) i jak nalézt příslušné třídy ekvivalence. V závěru hodiny jsme prošli dvouprůchodový algoritmus na hledání topologického uspořádání silně souvislých komponent (orientovaného) grafu.

Pak jsem ještě naznačil, že k řešení domácích úkolů by se mohlo hodit hešování, tedy struktura, která anmortizovaně, randomizovaně v konstantním čase dokáže na základě „libovolných“ klíčů přistupovat k prvkům.

Cvičení 5

Nejprve jsme dokončili DFS prohledávání rozborem Tarjanova jednoprůchodového algoritmu na zjišťování komponent silné souvislosti. Pak jsme se zabývali algoritmy pro hledání nejlacinějších sledů v grafech s cenami na hranách. Prošli jsem algoritmy Dijkstra, Bellman-Ford a Floyd-Warshal. Pouze první z nich měl význam v kontextu implicitních grafů. U Dijkstrova algoritmu nás zaujala potřeba vhodné datové struktury pro podporu operací Decrement (nejčastěji), Insert (méně často) a ExtractMin (nejméně často), nezbyl nám ale čas na to věnovat se jí více než stanovením dolních odhadů. Místo toho jsem v posledních pár minutách zformuloval příklad, který měl být motivační pro druhý domácí úkol (najít $n$-tý součet dvojic čísel vybraných ze dvou setříděných $n$ prvkových polí (každý sčítanec z jiného pole).). Zatím jsme stihli jen nástřel možného času algoritmu $O(n)$ bez náznaku algoritmu a oznámení, že to jde rychleji a uvědomění si, že součet $a_i+b_j$ se určitě vyskytuje v pořadí aspoň $i\cdot j$ (pole číslujeme od $1$).

Cvičení 6

Nejprve jsme dokončili motivační příklad na vážený medián. Vyšlo nám nezvyklé $\Theta(\sqrt{n}\log^2 n)$. Pak jsme se zabývali haldami. Odvodili jsme optimální haldy (na základě porovnávání) z předpokladu „extrémně drahého“ porovnávání. Dělali jsme amortizovanou variantu a vystačili jsme si se součtem čtyř potenciálů. Nezdůraznil jsem, že $\Phi_3$ musí mít větší multiplikativní konstantu, aby dokázal kromě času platit i příspěvek do potenciálu $\Phi_1$.

Cvičení 7

Věnovali jsme se mminimálním kostrám. Nejprve jsme až na domácí úkol ukázali, že nedeterministický barvící algoritmus vždy modře obarví minimální kostru. Pak jsme probrali 3 algoritmy z přednášky a ukázali, že se jedná o konkretizace barvícího algoritmu.

V případě Borůvkova algoritmu jsme museli být opatrní v paralelní verzi a bylo potřeba zajistit aby v případě "racing" došlo k tomu, že je obarvená stejně stejná hrana. Pokud by se mohly váhy hran opakovat, byl by racing problém a algoritmus by nefungoval.

Jarníkův algoritmus implementovaný pomocí hald podporujících rychlý decrement má bottleneck v složitosti operace ExtractMin. Tímto problémem se zabývá algoritmus Fredman-Tarjan, který jsme taky probrali. Principem je stanovení prahové hodnoty ($2^{2m/n}$), při níž ja zakázáno provádět ExtractMin. Tím máme zaručeno, že cena ExtractMin je $O(m/n)$. Nevýhodou je že pěstování modrých stromů skončí, ačkoli z nich stále ještě vedou neobarvené hrany. Algoritmus pracuje ve fázích, kde každá fáze trvá $O(m)$ ($m$ je počet hran, $n$ vrcholů). Musíme si dávat pozor a využívat jak operace FindMin tak ExtractMin s tím, že odstraňovaný vrchol je ten, který jsme dostali pomocí FindMin. Chceme na každý vrchol zavolat nejvýš jednou ExtractMin, proto nejprve voláme FindMin, a ExtractMin voláme jen v případě, že na daný vrchol zavolán ještě nebyl (v opačném případě nám srostly modré stromy a pěstování aktálního stromu končí). V druhé části fáze barvíme červeně hrany mezi modrými stromy tak aby nám kontrakcí modrých stromů do vrcholů vznikl graf bez duplicitních hran a smyček a k tomu se hodí přihrádkovým tříděním seřadit hrany podle lexikografického pořadí čísel komponent koncových vrcholů. Ukázali jsme, že prahová hodnota pro fázi $i+1$ je aspoň $t_{i+1}=2^{t_i}$, takže brzy ($i\le\log^* n$) dojde k tomu, že $n\le t_i$, takže se algoritmus v dané fázi bude chovat stejně jako Jarníkův algoritmus (na konrahovaném grafu) a půjde o poslední fázi.

Pro Kruskalův algoritmus jsme si povídali o implementaci Union Find datové strutury s naivním Union, ale i Union by rank/size, a taky o zkracování cest pomocí komprese, halvingu a splittingu. Naivní spojování bez zkracování cest má lineární složitost na operaci, naivní union se zkracováním má na operaci logaritmickou amortizovanou složitost o základu $\lfloor 1+k/n\rfloor$, pokud $k\ge n$ je počet operací. Union by rank/size bez zkracování má worst case složitost $O(\log n)$. Naznačil jsem pomalost funkce $\alpha$ i že existuje důkaz složitosti $O(\alpha(n))$ na jednu operaci pro jakoukoli kombinaci Union by rank/size se zkracováním.

Cvičení 8

Věnovali jsme se vyhledávacím stromům. Nejprve jsme rozebírali interface a uvědomili jsme si, že potřebujeme přibližné vyhledávání, a že velice užitečné jsou funkce prev, next. Věnovali jsme se optimalizaci dvojrozměrných intervalových dotazů a uvědomili si, že by se hodilo mít v inerface funkci, která vrací index prvku v utříděné posloupnosti. V případě opakovaných klíčů by se hodilo mít buď v interface možnost nechat vyhledat menší/větší konec intervalu, nebo (nezaznělo) možnost udržovat prvky setříděné lexikograficky podle klíče "rozšířeného o ID". Pak bychom se na příslušný konec intervalu mohli zeptat dotazem $({\rm key},-\infty)$ či $({\rm key},+\infty)$.

Pak jsme se věnovali vyvažování binárního stromu abychom dodržovali AVL invariant. (Technikou bylo v případě porušení invariantu rozložit na podstromy téměř stejné hloubky a rozmyslet si, jak je vhodně spojit. Probematický případ je když prostřední z trojice podstromů má výšku větší než oba krajní a v takovém případě musíme použít dvojrotaci.) Uvědomili jsme si, že až na evidenci relativní velikosti podstromů musíme při Insert použít nejvýš dvě rotace. V případě Delete se nám situaci takto vyřešit nepodařilo (nejde to). Použití nejvýš dvou rotací stačí na to, že problém vyřešíme lokálně, nicméně v konsoldaci musíme pokračovat výš ve stromě. Pro Delete tedy potřebujeme $\Theta(\log n)$ rotací.

Naznačil jsem, že u červenočerného invariantu jak Insert, tak Delete dokážeme vyřešit pomocí konstantního počtu rotací (a logaritmického počtu evidence pomocných informací). To se může velmi hodit v případě (semi)persistentní verze datové struktury, protože to povede ke struktuře velké $\Theta(n)$, pokud vznikne pomocí $\Theta(n)$ Insert a Delete. (U AVL vyvažování bychom potřebovali velikost $\Theta(n+d\log n)$, kde $d$ je počet Delete). Naznačil jsem jak by se takové semipersistentní udržování vyhledávacího stromu mohlo hodit pro lokalizaci trojůhelníku trojúhelníkové sítě v němž se nachází zadaný bod v čase $\Theta(\log n)$. (Jedna souřadnice odpovídá historii, druhá stavu řezu).

Velice krátce jsme si povídali i o vyvažování víceárních stromů (které mají listy ve stejné hloubce). Hlavní jejich výhodou je zohlednění cache hierarchie. Uvědomili jsme si taky, že jsou dva přístupy, jak uspořádanou množinu reprezentovat. V prvním je reprezentovaná jen v listech (u víceárních stromů přirozené), v druhém i ve vnitřních vrcholech (typické u binárních stromů).