Vladan Majerech - NTIN061 Algoritmy a datové struktury II
Last Modified: 6.1.2020
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
Pro získání zápočtu z NTIN061 je potřeba získat (3/5 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 odevzdání po termínu je jen poloviční počet bodů. Termín je do počátku cvičení příslušného dne. Příklady s body uvedenými v závorce jsou bonusové, body je možno získat, ale nepočítají se do limitu požadovaných bodů.
| Kód | Body | Termín odevzdání | Zadání |
|---|---|---|---|
| jehly | 10 | do 21.10. 14:00 | Spočtěte, kolikrát se dané jehly vyskytují v daném seně (podslova v textu). Upřesnění: stačí mi celkový počet, jako bonus si rozmyslete, co by se stalo, kdyby mne zajímaly počty každé jehly zvlášť. |
| podposloupnost | 10 | do 28.10. 14:00 | Spočtěte, kolikrát se daná jehla vyskytne v daném seně jako podposloupnost (možnost proložení jinými znaky). Například v BARBARAR je BAR 9 krát. |
| věže a sloupy | 10 | do 11.11. 14:00 | Máme šachovnici $m\times n$ a na některých políčkách stojí sloupy. Na políčka (bez sloupů) je možno umísťovat věže. Každá věž ohrožuje políčka ve stejné řadě a stejném sloupci, ale pouze k nejbližšímu sloupu v daném směru. Otázkou je, kolik věží je možno rozmístit tak, aby žádná nestála na políčku ohroženém jinou věží. No a na Vás je popsat, jak nalézt odpověď (můžete používat „známé“ algoritmy jako podprogramy). |
| kluby | 10 | do 18.11. 14:00 | Na kolejích jsou různé kluby, koleják může být součástí libovolného počtu klubů. Jste postaveni před úlohu vybrat z každého klubu předsedu a místopředsedu a to tak, aby každý koleják byl vybrán za nejvýš jeden klub a pro něj do právě jedné funkce. |
| FourKaracuba | 10 | do 25.11. 14:00 | Karacubův algoritmus redukuje úlohu násobení $n$ ciferných čísel na 3 násobení čísel zhruba poloviční délky. Navrhněte, jak by šlo totéž redukovat na 7 násobení čísel zhruba čtvrtinové délky. Předpokládáme $O(n)$ sčítání na redukci. |
| cesty | 10 | do 2.12. 14:00 | Pro dané vrcholy $u$, $v$ v orientovaném grafu nalezněte maximální počet vrcholově disjunktních cest z $u$ do $v$. |
| porovnání | 10 | do 9.12. 14:00 | Vytvořte co nejmělčí hradlovou síť, která pro n-bitová čísla $a$, $b$ vydá $1$ právě když $a\le b$. |
| souvislost | 10 | do 16.12. 14:00 | Vytvořte co nejmělčí hradlovou síť, která pro matici sousednosti neorientovaného grafu $G$ vydá true, právě, je-li graf $G$ souvislý. |
| Hamiltonovské cesty | 10 | do 6.1. 14:00 | Dokažte, že zjištění zda v grafu existuje Hamiltonovská cesta je NP-těžké, jak ve variantě neurčených koncových bodů cesty, tak i v případě, kdy jsou jeden či oba koncové vrcholy určeny (jak pro orientované, tak pro neorientované grafy). Můžete předpokládat, že víme, že nalezení Hamiltonovské kružnice je těžké jak pro orientované, tak pro neorientované grafy. |
| Id studenta | celkem | rozpad bodů |
|---|---|---|
| I | 33 | jehly(8+2/2), podposloupnost(8), kluby(0), porovnání(7), souvislost(9), hamiltonovské cesty(0) |
| A | 70 | jehly(10), podposloupnost(10), věže a sloupy(10), kluby(10), fourKaracuba(10), cesty(10), porovnání(10) |
| B | 70 | jehly(10), podposloupnost(10), věže a sloupy(10), kluby(10), cesty(10), porovnání(10), souvislost(10) |
| C | 55 | jehly(10), podposloupnost(10), věže a sloupy(10), kluby(10), cesty(10), porovnání(10/2) |
| D | 68 | jehly(10), podposloupnost(8), věže a sloupy(10), kluby(10), cesty(10), porovnání(10), souvislost(10) |
| E | 60 | jehly(10), podposloupnost(10), věže a sloupy(10), kluby(10), cesty(10), porovnání(10), souvislost(0/2) |
| F | 66 | jehly(10), podposloupnost(6), věže a sloupy(10), kluby(10), fourKaracuba(10), cesty(10), porovnání(10) |
| G | 60 | jehly(10), podposloupnost(10), věže a sloupy(10), kluby(10), cesty(10), porovnání(10) |
| H | 59.5 | jehly(10), podposloupnost(9+1/2), věže a sloupy(0/2), kluby(10), fourKaracuba(10), cesty(10), porovnání(10) |
| J | 59 | jehly(10), podposloupnost(8+2/2), věže a sloupy(10), kluby(10), cesty(10), souvislost(10) |
| K | 60.5 | jehly(8), podposloupnost(6), věže a sloupy(10), kluby(10), fourKaracuba(0), cesty(10), porovnání(7+3/2), souvislost(8) |
Odkazy na obdobné stránky
Cvičení Jirky Švancary, Miloše Chromého, Michala Oplera, Jakuba Pekárka a rozcestník Jana Hrice, moje loňská cvičení.
Cvičení 1
Na cvičení jsme se zabývali hledáním textu v textu (jehly(jehel) v kupce sena). Snažil jsem se naznačit, že mnohdy bývá užitečnější si předzpracovat seno (google; sufixové stromy ... snad se to ani nedalo nazvat náznak). Vzpomenul jsem plovoucí hash algoritmus Rabin-Karp a pak jsme se dostali k Knuth-Morris-Pratt algoritmu a k jeho zobecnění Aho-Corasick. Nedělali jsme žádné důkazy koreknosti, jen jsme nakreslili automat a pověděli jsme si jak jej zkonstruujeme (včetně informace nutné pro hlášení jehel tvořících sufix aktuálně reprezentovaného slova). KMP stačí pole indexů, AC potřebuje obecnější odkazy, jinak je AC rozšířením KMP. Zmínil jsem alternativní možnost provedení časového rozboru pomocí potenciálu.
V posledních 5 minutách jsme začali na tržnici prodávat datové struktury. Nabídnuto bylo disjoint find union. Uvidíme, jaké budou další nabídky.
Cvičení 2
Na druhém cvičení jsme pokračovali v dražbě datových struktur. Nabídkou byly črveno černé stromy, ale dokud prodávající nenabídl souseda uzlu jako výsledek „neúspěšného“ vyhledávání, byl sousední trhovec s hashovací tabulkou bezkonkurenčně lepší. Když už jsme (s následníkem) dokázali vyhodnocovat intervalové dotazy, zamysleli jsme se ještě nad obdélníkovými dotazy. Pro jejich podporu se hodila metoda vracející počet menších prvků. Počet prvků v intervalu získáme snadno odečtením hodnot v krajích bodech. Pro obdélníkové dotazy znalosti velikostí intervalů v jednotlivých řezech umožňují optimalizovat vyhodnocení výrazu.
Popsaný (logaritmický) interface odpovídá vyhledávacím stromům. Dále jsme se zabývali otázkou zda binární a jaký druh vyvažování. Porovnali jsme RB s AVL. Na hloubku vítězí AVL, počet rotací během insertů je vyrovnaný. Pouze při delete má RB konstantní počet rotací, zatímco AVL logaritmický. Co se týče evidence vyvažovacích operací, v obou případech standardní verze vyžadují $\theta(\log n)$ změn. V případě RB je informaci o barvách možno ukládat implicitně, tak aby v případě insert či delete docházelo pouze k $O(1)$ změnám. Persistentní verze RB stromů pak mají velikost $O(n+k)$ na rozdíl od $O(n+k\log n)$.
Na konci hodiny jsme ještě řešili úlohu házení vajec z mrakodrapu. Udělali jsme obdobný formalismus jako při určování vztahu mezi velikostí a hloubkou ABL či RB sromů. Ukázalo se, že vztah podléhá obdobným pravidlům jako Pascalův trojůhelnk, pouze inicializace není v jednom bodu, ale na celé polopřímce. Součet všech možných posunutí Pascalského trojúhelníku dává počet rozlišitelných případů na daný počet hodů a vajec.
Kromě toho jsme si trošku povídali o Fibonacciho posloupnosti, diferenčních rovnicích a základních tvarech jejích řešení a o souvislosti s maticemi, jejich násobením a umocňováním.
P.S.: Studenti mne viděli, jak si před cvičeními hraju s Rubikovou kostkou, tak si na druhé na ukázku přinesli taky pár hlavolamů. Jeden z nich, permutační hlavolam s blokací Bagua cube jsem neznal.
Cvičení 3
Na třetím cvičení jsme se zabývali maximalizací toků v sítích, dali jsme společně dohromady definici problému, ukázali jsme si jak řešit problém s více zdroji a stoky, a pak jsme se zabývali algoritmy jak problém řešit.
Naznačil jsem, že existují dva přístupy, jak maximální tok hledat. První je nalézt nějaký tok a buď zjistit, že je maximální, nebo ve zbytku najít tok, o který by bylo možno původní navýšit. Druhá naopak začít s maximálním skorotokem a postupně zajistit, aby se z něj stal tok. Ve chvíli, kdy se tak stane (zbavíme se přebytků ve vrcholech s tím, že něco může vytéct i zdrojem) máme maximální tok.
Algoritmus se zlepšující cestou (Ford Fulkerson) nebyl překvapením, algoritmus se skorotokem (Goldberg Tarjan) není tak přirozený protože si potřebuje pomoci s výškami vrcholů, které v zadání nikde nefigurují.
Naznačil jsem, že algoritmus zlepšujících cest nemusí vůbec skončit a může konvergovat k menšímu než optimálnímu toku. To ale vyžaduje iracionální kapacity hran a rozmysleli jsme si, že pro racionální kapacity je algoritmus konečný.
Hráli jsme si s tím, jak vybírat zlepšující cestu co nejefektivněji a snažili jsme se dospět k časové složitosti závisející na počtu vrcholů a hran, nikoli na kapacitách hran. Hledat cestu s největší minimální kapacitou byla zajímavá myšlenka. Místo toho jsem nás navigoval směrem k použití cest s minimálním možným počtem hran (Edmons-Karp) a ukázali jsme pro takový případ časový odhad běhu algoritmu. Následně jsme ukázali (Dinic), že pro stejně dlouhé cesty nemusíme průběžňě aktualizovat zbytkový graf a můžeme hledat cesty pouze ve vrstevnaté síti (podgrafu hran na cestách nejkratších cest). Časovou složitost výpočtu blokujícího toku ve vrstevnaté síti uměl Dinic $O(nm)$, čímž byla celková složitost vylepšena z $O(nm^2)$ na $O(n^2m)$.
Já jsem místo toho naznačil, že při volbě vhodné datové struktury je možno počítat blokující tok ve vrstevnaté síti v čase $O(m\log n)$, čímž dostáváme celkově $O(mn\log n)$.
V poslední čtvrt hodině jsme diskutovali, jak to vypadá s Goldberg-Tarjan algoritmem a princip důkazu (potenciál pro odhad počtu nesaturovaných push jsme stihli vymyslet). A dostali jsme celkovou složitost $O(mn^2)$. Jak se projeví optimalizace volby vrcholu s přebytkem v rozboru složitosti nám zůstane na příští cvičení, stejně tak ukázka sítě, kde se algoritmus zlepšujících cest nemusí zastavit.
Cvičení 4
Větší část hodiny jsme vymýšleli potenciál pro dlouhé fáze Goldberg-Tarjanova algoritmu s heuristikou, dle níž je zpracovávaný vždy nejvyšší vrchol s přebytkem. Nakonec jsme potenciál klesající o $K$ pro fáze s aspoň $K$ nesaturovanými push přeci jen objevili (navíc za podmínky) že saturované push tento potenciál zvyšují nejvýš o $n$. Vzhledem k tomu, že jej up zvyšují dohromady méně ($O(n^3)$) než saturované push ($O(mn^2)$), dostali jsme lepší odhad než předtím. Celkem tedy $O(mn^2/K)$ za dlouhé fáze a $O(n^2K)$ za krátké fáze (počet fází se nám předtím podařilo odhadnout dvojnásobkem počtu Up, tedy $O(n^2)$). Při volbě $K=\sqrt{m}$ pak dostáváme složitost $O(n^2\sqrt{m})$.
Pak jsme se věnovali demonstraci nekonečnosti Ford-Fulkerson algoritmu. (Ukázali jsme jak v daném grafu situace se zbytkovými kapacitami rozhodujících třech hran $0$, $q^n$, $q^{n+1}$ pomocí čtyř zlepšujících cest dospět do situace se zbytkovými kapacitami $0$, $q^{n+2}$, $q^{n+3}$, tento vzor je tedy možno opakovat do nekonečna. Vzhledem k symetrii grafu by šlo argumentovat o nekonečnosti již po použití dvou zlepšujících cest, ale již uvedená argumentace je jednodušší. Předpokladem bylo $q^n=q^{n+1}+q^{n+2}$ a $q\in(0,1)$.)
Cvičení 5
Na začátku hodiny jsem se pochlubil novou verzí Decrease-key hald. Probrali jsme to v kontextu amortizované analýzy Binomiálních a Fibonacciho hald.
Pak jsme se přes Karacubův algoritmus a jeho zobecnění dostali k násobení pomocí dosazování různých hodnot místo základu číselné soustavy. Ke konci hodiny jsme se dostali k tomu, jak dosazování souvisí s násobení maticí a k tomu, že násobení vhodně zvolených hodnot je možno efektivně paralelizovat. Volba $\omega=\root 2^k\of 1$ a dosazování $\omega^i$ má výhody v symetriích ($\omega^{2^{k-1}}=-\omega$). Což vede k redukci na násobení sudých a lichých sloupců zvlášť jen v jedné polovině matice. To se navíc dá převést na problém s o 1 menším $k$ (vždy jsem myslel, že jde o Cooley-Tukey algoritmus, ale nejspíš jde o Danielson-Lanczos. CT je jeho zobecněním pro jiné rozměry matice). Na příštím cvičení budeme pokračovat.
Cvičení 6
Vyzkoušeli jsme si Fourierovu transformaci pro matice $4\times 4$, část studentů v $C$ s $\omega=i$, část v $Z_{17}$ s $\omega=4$. Trvalo nám to dost dlouho, takže jsme jentak tak stihli popis s Cooley-Tukey. K aplikacím FT jsme se nedostali.
Cvičení 7
Na cvičení jsme si nejprve povídali o aplikacích Fourierovy transformace (a o její vizualizaci). Pak jsme si povídali o hradlových sítích. Úlohu, proč jsou pouze nand a nor univerzální hradla o dvou vstupech jsme rozřešili ale nedořešili.
Pak jsme si povídali o sčítání čísel pomocí hradlových sítí (pouze poslední dva sčítance sečíst vyžaduje nekonstatní hloubku). Výpočet přenosu pomocí výpočtu výsledku skládání funkcí jsme zobecnili pro úlohu vyhodnotit výsledek výpočtu konečného automatu, detaily jsme ale neřešili. Techniku počítání funkcí místo výsledku používala i přednáška na DOD o vyhodnocování výrazů pomocí malého počtu registrů. Neubránil jsem se tomu příslušný trik v tomto kontextu předvést. Na konci hodiny jsme si začali povídat o komparátorových sítích.
Cvičení 8
Na cvičení jsme se věnovali třídícím sítím. Popsali jsme jak bitonickou, tak merge třídící síť. Měly stejné hloubky. Bitonická síť měla všechny vrstvy zcela plné, ztímco merge síť měla na krajích podsítí vynechávané komparátory.
Cvičení 9
Na cvičení jsme se věnovali NP-úplnosti. Definovali jsme si NP, i NP-úplnost, ukázali jsme, že jsou úplné problémy $K$, $KACHL$ a $SAT$. Bavili jsme se o variantách problému KACHL.
Cvičení 10
Dále jsme se věnovali NP-úplnosti. Probírali jsme 3-color, 1 in 3 SAT, HC s malými stupni vrcholů, NM a jednu aplikaci HC s malými stupni vrcholů (NP-těžkost "hada"). Většina převodů byla ze SAT či 1 in 3 SAT ve stylu, jsem schopen deklarovat booleovské proměnné a jejich negace a jsem schopen vytvořit na sobě nezávislé klausule a propojit je s literály.