Vladan Majerech - NTIN060 Algoritmy a datové struktury 1
Last Modified: 28.3.2025
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
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ů. 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$.