Vladan Majerech - NTIN060 Algoritmy a datové struktury 1
Last Modified: 29.5.2023
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í by měly být současně přes zoom, uvidíme, jak bude fungovat technika. 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 pondělního 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 | 27.2.2023 | Dokažte matematickou indukcí případy rekurence $t(n)\le cn^\alpha+\sum_{i=1}^k t(a_in)$, kde $\forall i\,a_i<1$ (a pro $n\le n_0$, $t(n)\le C$) dle srovnání $S_\alpha=\sum a_i^\alpha$ s $1$, užitečné je dokazovat existenci konstant $c_1$, $c_2$ pro něž platí pro všechna $n$ vztah $t(n)\le c_1n^\alpha+c_2n^\beta$, kde $S_\beta=\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 | 6.3.2023 | Ukažte, dvě varianty algoritmu (odlišné obdobně jako u Strassenova algoritmu), jak je možno násobit $n$ ciferná čísla v čase $O(n^{\log_23})$. |
| medián | 10 | 13.3.2023 | 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)$). |
| řeka | 10 | 20.3.2023 | 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 | 27.3.2023 | 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í. |
| rekur | 10 | 3.4.2023 | 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$. |
| bprav | 10 | 17.4.2023 | 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). |
| lavl | 10 | 24.4.2023 | 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. |
| perm2n | 5 | 15.5.2023 | 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 | 15.5.2023 | 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 | 22.5.2023 | Algoritmicky popište (co možná nejefektivnější) 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). |
| Id studenta | celkem | rozpad bodů |
|---|---|---|
| A | 71 | indukce(10), mult(10), medián(10), řeka(8), rekur(10), řeka2(8), lavl(10), perm2n(5) |
| B | 67 | indukce(10), mult(10), medián(10), řeka(9), řeka2(8), rekur(10), bprav(10) |
| C | 68 | indukce(10), mult(10), medián(10), řeka(8), řeka2(0), rekur(10), bprav(10), lavl(10) |
| D | 71 | indukce(10), mult(10), medián(10), řeka(4+6/2), řeka2(0+8/2), rekur(10), bprav(10), lavl(10) |
| E | 74 | indukce(10), mult(10), medián(10), řeka(4), řeka2(0), rekur(10), lavl(10), perm2n(5), n2perm(5), permBi(10) |
| F | 17 | indukce(2), mult(8), medián(6/2), řeka(0), řeka2(0), rekur(4), bprav(0) |
| G | 68 | indukce(6), mult(10), medián(10), řeka(4), rekur(10), bprav(10), perm2n(5), n2perm(5), permBi(8) |
| H | 7 | indukce(2), mult(5), medián(0) |
| I | 69 | indukce(10), mult(10), medián(10), řeka(4+4/2), řeka2(7+2/2), rekur(10), bprav(10), perm2n(5) |
| J | 9 | indukce(0), mult(5), medián(0), řeka(4) |
| K | 9 | indukce(0), mult(5), medián(2), řeka(2) |
| L | 72 | mult(10), medián(10), řeka(6), řeka2(8), rekur(10), bprav(6+4/2), lavl(10), perm2n(5), n2perm(5) |
| M | 73 | mult(5), medián(10), řeka(10), řeka2(10), rekur(10), bprav(10), perm2n(5), n2perm(5), permBi(8) |
| N | 6 | mult(0), medián(2), řeka(4) |
Odkazy na obdobné stránky
moje loňské cvičení, texty k cvičení Jana Hrice,
Cvičení 1
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.
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 hodnotou 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 1 jedna v počátečních posdmí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. 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ě 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ýsledek pro hloubku AVL byl logaritmus o základu zlatý řez plus zaokrouhlení.) To s nehomogenními rovnicemi bohužel na cvičení nezaznělo. Tak snad si na to vzpomenu příště.
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“.
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í“.
V době „(ne)zvonění“ 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$ (určitě by pomohlo, pokud bychom se bavili o nehomogenní variantě) ve 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
Na začátku hodiny jsme si hráli s lineární algebrou. Nejprve jsme si vyzkoušeli hledat řešení jedné nehomogenní lineární diferenční rovnice s konstantními koeficienty (s dvojnásobým kořenem, jehož geometrická řada byla i v nehomogenní části, navíc v nehomogenní části byl polynomiální násobek jiné geometrické řady). Sestavili jsme si maticový operátor, ale Jordánův tvar matice jsme neodvozovali, jen jsme našli z charakteristické rovnice (homogenní části) dvojnásobné vlastní číslo. Uhodnutý tvar řešení po dosazení do rekurentního tvaru umožnil sestavit tolik nezávislých lineárních rovnic, kolik jsme měli neznámých parametrů (a vztah pak platil současně pro všechna $n$). Nezkoušeli jsme, že pro jiné geometrické řady bychom neuspěli.
Trik se substiucí $T(n)=t(2^n)$ pro „naši rekurenci“ jsem zase zmínil až v diskusi po hodině.
Pak jsem ukázal jak efektivně násobit matice (máme-li $-$ jakožto inverzní operátor k $+$). Podařilo se nám místo 8 násobení matic poloviční velikosti použít 7 násobení matic poloviční velikosti. Sice jsme při tom museli odčítat a častěji sčítat, ale ze složitosti $O(n^{\log_2 8})=O(n^3)$ jsme se tak dostali ke složitosti $O(n^{\log_2 7})$. Hledali jsme $\beta$, pro které je $S_\beta=1$. Pro otrlé: Součiny v algoritmu měly u každého $A_{i,j}\cdot B_{k,\ell}$ (indexujeme poloviny matice, tedy $i,j,k,\ell\in \{0,1\}$) vždy stejný reálný koeficient s absolutní hodnotou $1$, který mohl případně být nahrazen 0. Dva potřebné součiny jsme vždy dostali jako rozdíl takovýchto koeficientů, kde díky pečlivému plánování „stínové magii“ se všechny ostatních součiny vyrušily. Z toho dostáváme podmínku na opačná znaménka čtyř dvojic součinů. Což znamená, že koeficienty násobení řádku matice A a sloupců matice B musí vždy v součinu být -1. Protože to platí pro každou kombinaci výběru řádků a sloupců, musí být součin koeficientů násobení matice A roven 1, stejně tak součin koeficientů násobení matice B. Správnost znaménka čtvrtého součinu je tím vynucena. Máme tedy $2^8/2^3=32$ možností jak zvolit koeficienty, kterými budou které části matic násobeny (pokud budou zastoupeny). Nejspíš bychom mohli rozmístit nenulové hodnoty součinů jinak (triviálně prohozením řádků či sloupců), čímž bychom se dostali na $2^2\cdot 32=128$ variant algoritmu. Vždy bychom měli jeden „řádkový“, jeden „sloupcový“, jeden „řádko-sloupcový“ a dopočítali bychom potřebu jednoho „$A$-čtvercového“ součinu, „$B$-čtvercového“ a dvou „bodových“ součinů. Jedná se o Strassen algoritmus, pravděpodobně o Winograd variantu.
Ke konci hodiny jsme začali Kirkpatrick-Seidel algoritmus na hledání konvexního obalu. Stihli jsme probrat vnější rekurenci a za předpokladu lineární složitosti vnitřních rekurencí jsme dostali složitost $O(n\log h)$, kde $n$ je velikost vstupu a $h$ výstupu. Jednalo se o nestandardní použití rekurence z minulé hodiny, kdy jsme nemohli použít výsledné tvrzení, ale museli jsme se znovu podívat dovnitř důkazu (případ $S_\alpha=1$) abychom mohli zohlednit vliv hodnoty $h$. Příště se podíváme na vnitřní rekurence a pak na DFS.
Cvičení 3
Dokončili jsme Kirkpatrick-Seidel algoritmus s tím, že jsme na něm viděli dvě použití naší věty. První bylo hledání $k$-tého z $n$ prvků dle velikosti klíče. Tam se ukázalo, že aproximace volby pivota pomocí mediánu mediánů trojic vede k $S_1=1$, tedy k $\Theta(n\log n)$ algoritmu. Když jsme ale pivota volili jako medián mediánů pětic, dostali jsme $S_1=9/10<1$, takže $\Theta(n)$ worst case časovou složitost (alternativně by se hodily „soft-heaps“).
Následně jsme řešili hledání horního mostu pomocí rekurence přavádějící úlohu na jediné volání menší úlohy. Jednu čtvrtinu bodů jsme v $O(n)$ zahodili na základě porovnání směru dvojice se směrem horního mostu. Vždy (pokud nejde o horní most) můžeme jeden z bodů zahodit. Pro polovinu dvojic tak můžeme jeden bod zahodit, pokud předtím porovnáme směr mostu s mediánovým směrem. V $O(n)$ dokážeme zjistit, zda daný směr je směrem horního mostu, či zda je jej potřeba pootočit po či proti směru hodinových ručiček. Stačí „proložit směr všemi body“ a vybrat extrémní body. Požadovanou informaci určíme dle toho, kde se extrémní body s ohledem k určující polopřímce nacházejí.
Následně jsme dělali motivaci k dalšímu DU. Hledali jsme $n$ tý z $n^2$ součtů $a_i+b_j$, kde $a_i$ i $b_j$ jsou neklesající posloupnosti délky $n$ zadané na vstupu odkazy na utříděná pole. Ukázalo se, že většinu součtů nepotřebueme, takže stačí hledat mezi $\Theta(nH_n)=\Theta(n\log n)$ možnostmi. Navíc je tyto možnosti možno reprezentovat pomocí $\Theta(\sqrt{n})$ utříděných intervalů a vážený medián jejich mediánů jakožto pivot nám umožní v čase $O(\sqrt{n}\log n)$ zredukovat počet kandidátů na polovinu (bohužel počet neprázdných seznamů může stále být $\Omega(\sqrt{n})$, takže celková složitost bude $\Theta(\sqrt{n}\log^2 n)$).
Ve zbytku hodiny jsme si povídali o prohledávání implicitních grafů a užitečnosti dolních odhadů vzdálenosti. Neřekli jsme si, jak v implicitních grafech nechávat drobečky, abychom se příliš neopakovali.
Cvičení 4
Věnovali jsme se prohledávání do hloubky za účelem zjišťování informací o grafu.
Cvičení 5
Věnovali jsme se hledání nejlacinějších sledů v grafu, konkréně z vrcholu do vrcholu v nezáporně ohodnoceném grafu. Popsali jsme Dijkstrův algoritmus, pohovořil jsem o různých dimenzích složitosti a ukázal jsem jak dojít k vhodné datové struktře pro Dijkstrův algoritmus. Postupně jsme dospěli ke čtyřem složkám potenciálu, které se k rozboru hodily. Naznačil jsem, jak je místo lokální podmínky pro ztráty možno udržovat globální podmínku pro ztráty a naznačil jsem variantu haldy, kde v globálním „konsolidačním poli řádů“ odkazy na stromy jednotlivých řádů necháváme a stejným způsobem řešíme i vrcholy se ztrátou. Ve worst case variantě potřebujeme navíc ke každému globálnímu poli ještě stejně hluboký zásobník, na který chychom si ukládali rozpracovanou práci, pokud bychom měli překročit čas na jednu operaci (to že nepořebujeme hlubší zásobník jsem nezdůvodňoval, důvodem je, že můžeme worst case udržovat celkové zaplnění zásobníku s globálním polem na hodnotě nejvýš 1+maximální možný řád) Při ExtractMin zásobníky vyprazdňujeme (a operace provádíme rovnou v konsolidačním poli).
Cvičení 6
Řešili jsme úlohy (převážně) související s DFS.
Cvičení 7
Věnovali jsme se hledání minimální kostry.
Cvičení 8
Věnovali jsme se vyhledávacím stromům a AVL (Fibonacciho) vyvažování.
Cvičení 9
Na devátém cvičení jsme si povídali o hešování.
Cvičení 10
Na desátém cvičení jsme řešili dvě hádanky o vězních.
Cvičení 11
Na dalším cvičení jsme si nejprve trochu povídali o domácích úkolech a později o QR kódech, takže jsme mírně zmínili BCH, Reed Solomonovy kódy, Galois Field $2^8$, diskrétní logaritmy, dynamické programování.