Vladan Majerech - NTIN060 Algoritmy a datové struktury
Last Modified: 11.6.2021
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
Cvičení by měla probíhat přes zoom. Včas byste měli dostat e-mailem odkaz na google doc. Pokud by k tomu z jakéhokoli důvodu nedošlo, kontaktujte mne mailem jmeno.prijmeni@mff.cuni.cz. V google doc by měly být odkazy na zoom i virtuální tabuli udržovány.
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 9:00 v datum 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. Domácí úkoly odevzdávejte e-mailem ať ve formě fotografie/skenu rukou napsaného řešení, nebo přímo v nějakém jiném všeobecně rozšířeném formátu (např. pdf, či přímo v textu e-mailu).
| Kód | Body | termín | Zadání |
|---|---|---|---|
| indukce | 10 | 15.3.2021 | Dokažte matematickou indukcí případy rekurence $t(n)\le cn^\alpha+\sum_{i=1}^k t(a_in)$ ($t(n)\le C$, pro $n\le n_0$, $\forall i\,a_i<1$) dle srovnání $S_\alpha=\sum a_i^\alpha$ s $1$, užitečné je dokazovat vztah $t(n)\le c_1n^\alpha+c_2n^\beta$, kde $\sum a_i^\beta=1$, případně $t(n)\le c_1n^\alpha+c_2n^\alpha\log n$, vhodná $c_i$ zjistěte v průběhu důkazu. Hodí se za indukční předpoklad brát, že tvrzení platí pro všechna menší $n$. |
| mult | 10 | 22.3.2021 | Ukažte, dva (velmi podobné) algoritmy, jak je možno násobit $n$ ciferná čísla v čase $O(n^{\log_23})$. |
| medián | 10 | 29.3.2021 | Je dán „komprimovaný“ seznam čísel. Nalezněte jejich medián (prvek na pozici $m/2$ v seřazené posloupnosti všech $m$ prvků). 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). Můžete využívat algoritmus na nalezení mediánu v nekomprimovaném případě jako podprogram (a nemusíte o něm dokazovat, že pro $n$ prvků pracuje v čase $O(n)$). |
| rekur | 10 | 12.4.2021 | 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$. |
| rekur2 | 10 | 19.4.2021 | 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$. |
| řeka | 10 | 26.4.2021 | Je dáno povodí řeky ve formě orientovaného stromu, v němž každý vrchol je buď soutok nebo molo (či současně obojí). Pro každý úsek mezi sousedícími vrcholy je dána jejich vzdálenost (malé přirozené číslo). Je dáno malé přirozené číslo $d$. Otázka je, zda v povodí existují dvě mola, kde jedno je dosažitelné po proudu od druhého a jejichž vdálenost je přesně $d$. Popište algoritmus, který na danou otázku odpoví. |
| řeka2 | 10 | 3.5.2021 | Je dáno povodí řeky ve formě orientovaného stromu, v němž každý vrchol je buď soutok nebo molo (či současně obojí). Pro každý úsek mezi sousedícími vrcholy je dána jejich vzdálenost (malé přirozené číslo). Je dáno malé přirozené číslo $d$. Otázka je, zda v povodí existují dvě mola (mohou být na různých přítocích), jejichž (říční) vdálenost je přesně $d$. Popište algoritmus, který na danou otázku odpoví. |
| lavl | 10 | 10.5.2021 | 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. |
| bprav | 10 | 17.5.2021 | Ukažte, že barvící algoritmus pro hledání minimální kostry nemůže žádnou hranu obarvit podruhé (v případě shodné ceny preferujeme neobarvenou hranu). |
| perm2n | 5 | 24.5.2021 | 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 | 24.5.2021 | 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 | 31.5.2021 | 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). |
| logik | (10) | 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ž 264, zvládnete to i pokud máte k dispozici jen $\Theta(N)$ paměti?). |
| Id studenta | celkem | rozpad bodů |
|---|---|---|
| F | 8 | mult(4), medián(4) |
| H | 25.5 | mult(10/2), rekur(10), medián(5/2), rekur2(8) |
| A | 78 | indukce(10), mult(10), medián(10), rekur(10), rekur2(10), řeka(8), lavl(10), perm2n(5/2), n2perm(5/2), permBi(10/2) |
| B | 74 | indukce(2), mult(10), medián(6), rekur(10), rekur2(10), řeka(3+6/2), řeka2(5), lavl(10), bprav(?), perm2n(3), n2perm(3), permBi(9) |
| C | 100 | indukce(10), mult(10), medián(10), rekur(10), rekur2(10), řeka(10), řeka2(10), lavl(10), perm2n(5), n2perm(5), permBi(10) |
| D | 84 | indukce(10), medián(10), mult(10), rekur(10), rekur2(10), řeka(4), lavl(10), perm2n(5), n2perm(5), permBi(10) |
| E | 76 | indukce(6), mult(10), medián(10), rekur(9), rekur2(4+6/2), řeka(6), lavl(10), perm2n(5), n2perm(5), permBi(8) |
| G | 70 | mult(10/2), medián(10), rekur(10), řeka(10), řeka2(10), perm2n(5), n2perm(5), permBi(10), rekur2(10/2) |
Odkazy na obdobné stránky
přednášky Martina Mareše, moje loňské cvičení, texty k cvičení Jana Hrice, cvičení Michala Kouteckého, Michala Oplera, loňská Jakuba Pekárka
Cvičení 1
Na cvičení jsem oznámil podmínky zápočtu a v podstatě celou hodinu jsem budoval oslí můstek k zadání prvního domácího úkolu.
Nejprve jsme odhadovali hloubku AVL stromu. Brzy jsme odhalili, že lepší je počítat velikost nejmenšího stromu dosahujícího dané hloubky a 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. Ve skutečnosti jsme s charakteristickým polynomem rekurence začínali, což jsme dostali z hypotézy, že homogenní řešení budeme hledat ve tvaru polynom krát geometrická posloupnost. 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).
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“.
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 jedno řešení ve tvaru polynom stupně o tolik většího, kolikanásobně se daná geometrická posloupnost vyskytuje v homogenních řešeních (1+maximální stupeň polynomu, jímž v homogenním řešení může být násobena daná geometrická posloupnost). V případě AVL rekurence konstantního polynomu s geometrickou posloupností $1^n$, která není řešením homogenní rovnice jsme tedy hledali konstantu, která je řešením. Matematickou indukcí jsme konstantu nalezli a ověřili, že v tomto případě konstanta stačí. Správně zazněl dotaz jak jsme věděli co máme matematickou indukcí dokazovat (ve skutečnosti jsem nejprve ukázal matematickou indukci a pak až zdůvodnění proč). Což je základní problém matematické indukce ... velice snadno se s ní dokazují pravdivá tvrzení, ale je potřeba "intuice" k tomu vědět co dokazovat. (Výsledek pro hloubku AVL byl logaritmus o základu zlatý řez plus zaokrouhlení.)
Pak jsme se dostali k řešení rekurence $t(n)\in O(n^\alpha)+\sum_{i=1}^k t(a_in)$, která poměrně přirozeně vzniká při analýzách chování algoritmů. Nejprve jsem se snažil poskytnout trochu času na seznámení se s rekurencí, pak jsem měl proslov 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é organizaci zápisu jsme rozdělili výpočet na část s $cn^\alpha$ a na části s $t$, které je ještě potřeba rozepsat. Homogenita zápisu v každé části nám umožnila nepsat zbytečně mnoho symbolů a věnovat se místo toho podtatě problému.
Ukázalo se, že stěžejní je hodnota $S(\alpha)=\sum a_i^\alpha$. Pokud je $S(\alpha)<1$, vyjde $t(n)\in O(n^\alpha)$, pokud je $S(\alpha)=1$, vyjde $t(n)\in O(n^\alpha\log n)$ a pokud je $S(\alpha)>1$, existuje $\beta>\alpha$ pro něž je $S(\beta)=1$ a $t(n)\in O(n^\beta)$. Zdůvodnění, pro případ $S(\alpha)>1$ se součtem geometrické posloupnosti chyb odhadu byla trochu magie. Takže všechny odvozené výsledky je lepší zkontrolovat například „matematickou indukcí“.
Na úplný závěr jsem naznačil, že substitucí $f(n)=t(e^n)$ (či $t(2^n)$) přechází rekurence do formy o níž jsme si povídali na začátku hodiny, proto z povídání o lineárních rekurencích speciálně v souvislosti vícenásobnými kořeny se dá tušit, že řešení jsou v případě $S(\alpha)=1$. Je tvaru $c_1n^\alpha+c_2n^\alpha\log n$ a v opačném případě $c_1n^\alpha+c_2n^\beta$. Vzhledem k tomu, že v $O$ notaci můžeme součet funkcí odhadnout asymptoticky větší z nich, dostáváme tvrzení ve shodě s předchozími pozorováními (pro $f(n)$ platí rekurence s odčítáním v argumentech, charakteristická rovnice přechází na tvar $1=\sum_i q^{\ln a_i}=\sum_i a_i^{\ln q}$ a z $n^kq^n$ dostáváme po převodu $\ln^k n\cdot n^{\ln q}$).
Cvičení 2
Cvičení (pro masochisty je nahrávka dostupná z google doc) jsem se pokusil udělat v duchu druhého cvičení lonského roku, tedy se studenty samostatně pracujícími v malých skupinkách. Nejprve jsme řešili úlohy, kde binární operace byly popsány rekurentními vztahy a bylo potřeba zjistit, co dané operace provádějí. Došlo k pár nejasnostem se značením ^ (xor/power), nicméně vpodstatě všechny skupinky po čase dospěly ke správným odpovědím. Bohužel to zabralo úvodních 60 minut hodiny. Takže jsem co se týče důkazu korektnosti naznačil, že většinou pomůže indukce přímočaře, protože argumenty se snižují. Pouze u první rekurence by bylo potřeba najít jiné dobré uspořádání argumentů funkce (je to celkový počet nenulových bitů argumentů). Dobré uspořádání argumentů (kde voláme funkci jen s nižšími argumenty) garantuje konečnost výpočtu, ale zároveň dává pořadí pro důkaz matematickou indukcí.
Pak jsme na chvilku ve skupinkách řadili vybrané funkce dle asymptotického růstu. Nejjednodušší metodou bylo všechny funkce zlogaritmovat (o stejném základu) a uspořádat logaritmy. Tohle se mi zdá, že šlo lépe než vloni. Kromě toho bylo za úkol dokázat 2 základní tvrzení o chování $O$ notace, věřím tomu, že důkazy ve skupinkách proběhly korektně, ale překvapivé je, že nikdo neupozornil na fakt, že druhá z nich platí jen za předpokladu nezápornosti uvedených funkcí.
Příště budeme řešit další příklady již dnes uvedené v google doc, tentokrát půjde o algoritmy a jejich anylýzu pomocí techniky z prvního cvičení.
Cvičení 3
Na třetím cvičení jsme probírali různé rekurentní algoritmy s ohledem na jejich složitost. V prvním případě schéma algoritmu na hledání k-tého prvku dle uspořádání. Ukázali jsme, jakou složitost bude mít v závislosti na volbě parametru a díky znalosti řešení rekurence (obecnější než "master theorem") jsme viděli, že při špatné volbě parametru dostáváme složitost $O(n\log n)$, zatímco při správné $O(n)$.
Pak jsme se zabývali efektivním násobením matic. Předvedl jsem zápisově efektivní značení, a ukázali jsme jak triviálně pomocí 8 násobení matic poloviční velikosti získat složitost $O(n^3)$ ... měřeno v rozměru matice, nikoli v ploše. Rozhodli jsme se nakombinovat stejný výsledek jen pomocí 7 násobení matic poloviční velikosti (a dostat tak složitost $O(n^{\log_27})$).
Ukázal jsem jak nakombinovat první tři součiny a jak jejich +- kombinací skoro získat čtvrtinu výsledné matice. Potřebovali jsme přidat ještě jeden součin, aby to vyšlo. Pak jsem nažnačil která +- kombinace je dobrý základ pro získání druhé a která třetí čtvrtiny výsledku. Součin který je potřeba odečíst jste již doplnili sami. Pro poslední čtvrtinu jste našli i mezivýsledek ze kterého je potřeba začít.
Pro otrlé: Schéma fungovalo tak, že v každém ze 7 vzorců součinů součin podmatice $A_{i,j}B_{k,l}$ buď vůbec nefiguroval, nebo tam byl s koeficientem 1 či -1, ale nenulové koeficienty u dané čtveřice indexů měly vždy stejné znaménko. Navíc měly různá znaménka vždy ty 2 pozice, které se vyskytují ve výsledných čtvrtinách součinu. Z hlediska kombinování mezivýsledků jsme se pak nemuseli starat o koeficienty, při odečítání dvou takových součinů se vynulovaly hodnoty v průniku nenulových, pouze symetrická diference nenulových koeficientů se projevila ve výsledku (jediná výjimka měla výsledný koeficient ve tvaru 2-1). Na schématu tedy bylo především důležité, které hodnoty koeficientů jsou nulové a které nenulové. V součinu jsme samozřejmě omezeni tím, že nenulovost koeficientu u $A_{i,j}B_{k,l}$ i $A_{m,n}B_{o,p}$ garantuje nenulovost u $A_{i,j}B_{o,p}$ i $A_{m,n}B_{k,l}$. Podmíku na stejnost znamének u příslušných koeficientů zajistíme jednoduše tak, že do činitele zahrnujeme $A_{i,j}$ pro dané $(i,j)$ vždy se stejným znaménkem (případně s nulou). Totéž pro $B_{i,j}$. K zajištění aby příslušné koeficienty měly v součinech různá znaménka zjistíme, že podmínka je, aby součin všech koeficientů, kterými jsou (v případě nenulovosti) násobeny $A_{i,j}$ musí být 1 a totéž platí pro koeficienty pro $B_{i,j}$. Navíc musí platit, že součin koeficientů jimiž je násobeno $A_{1,j}$ krát součin koeficientů, kterými je násobeno $B_{i,1}$ je -1. Máme tedy $2^{8-3}$ možností, jak si předvybrat znaménka, pro daný výběr nenulovostí koeficientů.
Pak jsme se ještě zabývali rekurencí typu prune and search, tedy případu rozděl a panuj, kdy dělíme na jedinou část. Použili jsme to v algoritmu hledání „horního mostu“, což je součást konvexního obalu množiny bodů jednoznačně určená protínající polopřímkou. Potřebovali jsme pro to medián směrů dvojic a jeho porovnání s neznámým směrem mostu. To nám umožnilo alespoň v polovině dvojic jeden z vrcholů zahodit. Počet bodů se nám tak podařilo v lineárním čase zredukovat z $n$ na nejvýš $1+3(n-1)/4$. To je od určitého $n_0$ určitě nejvýš $4n/5$, takže jsme dostali lineární algoritmus.
Shrnutí: Ukázali jsme si jedno využití rekurence s různě velkými částmi, jedno využití se stejně velkými částmi a jeno využití s jedinou částí. Čeká nás ještě využití, kde výsledné tvrzení není dostatečně silné a k odhadu složitosti bude potřeba podívat se, kde se dal v daném konkrétním případě odhad vylepšit.
Cvičení 4
Na čtvrtém cvičení jsme dokončili Kirkpatrick-Seidel algoritmus na nalezení konvexního obalu bodů v rovině v čase $O(n\log h)$, kde $h$ je počet bodů určujících konvexní obal.
Následně jsme se věnovali problému prohledávání grafů jak v explicitních, tak v implicitních grafech. Srovnávali jsme výhody a nevýhody BFS a DFS. Hovořili jsme i o IDA. Přidali jsme i heuristiky.
Pak jsme hovořili o užitečnosti BFS, DFS s ohledem na zjišťování informací o grafu. Zavedli jsme si preorder a postorder číslování a začali se bavit o topologickém třídění silně souvislých komponent a v tom budeme příště pokračovat.
Cvičení 5
Na cvičení jsme se věnovali aplikacím DFS, kromě dvouprůchodového algoritmu na silně souvislé komponenty jsme dělali algoritmy na komponenty hranové a vrcholové ouvislosti.
Cvičení 6
Na cvičení jsme se věnovali nejlacinějším sledům a cestám v grafu s cenami na hranách. (Dijkstra pro nezáporné, Bellman Ford pro bez záporných cyklů, Floyd Warshall pro sledy i se zápornými cykly. Sledy umíme vždy, cesty jen, pokud se jedná o sledy (Hamiltonovská cesta)).
Následně jsme se věnovali mnimání kostře a barvícímu algoritmu (Jarník=Dijkstra, Borůvka, Kruskal). Pro asymptoticky optimální implementace nám chybí probrat DFU a Haldy.
Cvičení 7
Povídali jsme si o dvou datových strukturách se zajímavou amortizovanou složitostí, u Disjoint Find Union byla složitost dána k uvěření. U hald děláme rozbor pomocí potenciálů, postupně se nám zaváděním potenciálů (a upřesňováním implementace metod) přesýpá cena mezi operacemi. Příště to dokončíme.
Cvičení 8
Většinu cvičení jsme se věnovali haldám, jen v závěru jsme se dostali k AVL stromům. U worst case verze binomiálních hald jsem nezmínil, že po Insertu zajišťujeme, aby byl jediný strom. Ale nemáme čas vyřešit všechny konflikty řádů při insertu $2^k$ tého prvku. Stejně jako při řešení decrementů (cut) při organzování stromů s nenulovým Loss potřebujeme keše zásobník na nedořešené konflikty. Pointer na insertovaného nového kandidáta na minimum dáme do keše (i v případě cut v rámci decrementu) Nejprve vyřešíme konstantní počet konfliktů ze zásobníku, pak provedeme konsolidaci, tedy pokud by stále ještě byli dva kandidáti na minimum tak je porovnáme (insertovaný mohl být pořad nejmenší a kořen neměl konfliktní řád).
Potenciál, který udržujeme je zaplnění pole řádů kandidátů + dvakrát velikost keše kandidátů + třikrát zaplnění pole řádů vrcholů s Loss + čtyřikrát velikost keše Loss (vrchol s Loss>1 je započítán dle svého Loss).
Každá "vyvažovací" operace snižuje potenciál o kladné celé číslo, DeleteMin vyprazdňuje keše, ostatní operace potenciál navyšují o konstantu a pak je spuštěno vyvažování, dokud potenciál neklesne na hodnotu nejvýš tak velkou, jakou měl před operací (nebo dokud se nevyprázní keš). Z toho vyplývá že provedeme nejvýš konstantní počet vyvažovacích operací a jak počet neřádných hran, tak součet Loss bude omezen maximálním řádem plus 1. Maximální Loss omezený maximálním řádem plus 1 vede k rovnici na určení maximálního možného řádu který je jen nepatrně větší než dvojkový logaritmus (Dá se hrubě odhadnout pomocí $1.2\log_2 n+4$).
Utrhnout otci se překládá (až na jedinou výjimku na konverzi řádné hrany na neřádnou).
Cvičení 9
Na cvičení jsme dodělali vyvažování AVL stromů a trochu jsme se věnovali i RB stromům.
Cvičení 10
Nejprve jsme si chvilku povídali o hešování, pak jsme řešili hádanky (efektivní algoritmus na nalezení n-tého součtu dvojic prvků z dvou nprvkových vstupních polí, na konci hodiny pak efektivní lámání čokolády a rozřezávání kvádru).
Cvičení 11
Opět jsme se bavili o hádankách, nebylo snadné nalézt těžkou hádanku, kterou by studenti neznali od Martina Mareše. Alespoň vajíčka jsme vylepšili nalezením explicitního vzorce.
Cvičení 12
Nejprve jsem se trochu zamotal při povídání o problému nejmenšího opsaného kruhu, pak jsme se věnovali vyvažování červeno černých stromů.
Cvičení 13
Na posledním cvičení jsme si nejprve hráli s dynamickým programováním / pamatováním mezivýsledků (podčísla/volba kódování zprávy pomocí bitů v QR kódech), pak jsme si chvíli povídali o pokročilých DS (triky částečné a plné persistence, pojem cache oblivious).