Algoritmy a datové struktury 2, cvičení podzim 2014

Cvičení vede každou středu 17:20 v S11 Tomáš Gavenčiak (gavento@ucw.cz). Cvičení sleduje přednášku Ondřeje Čepka.

Zápočet

Účast na cvičení není povinná. Zápočet získáte za zcela správné vyřešení alespoň jedné úlohy z každé série a za zápočtový program či esej ve druhé části semestru.

Domácí úkoly odevzdávejte nejlépe elektronicky ve formátu PDF nebo i jen jako text emailu, pokud je popis dost jednoduchý. Obrázky můžou být i nafocené a jsou vítány pokud objasní vaše řešení. Nafocený text psaný rukou mi prosím neposílejte.

Na úkolu je velmi důležité velmi dobré vysvětlení a zdůvodnění. To může být krátké, ale mělo by být přesné, výstižné a dávat smysl i když čtenář řešení nezná. Přečtěte si ho po sobě. Úkolů bude letos málo, dejte si s nimi proto prosím záležet :-)

První sada domácích úkolů

Instrukce: Hoďte si 3-stěnnou kostkou a začněte řešit ten příklad, jehož číslo vám padne. Pracujte na něm alespoň den. Pokud vás ani potom řešení nenapadne, hoďte si znovu. Příklady jsou přibližně stejně těžké, ale rád bych, aby byla ditribuce řešení rovnoměrná :-)

Deadline na první sérii je 29. 10. 2014. Pokud si řešením nejste jisti, pošlete mi jej dříve.

Úloha 1.1: Definujme Fibonacciho slova takto: $F_0 = a$, $F_1 = b$, $F_{n+2} = F_nF_{n+1}$, kde $a$ a $b$ jsou libovolná různá písmena. Jak v zadaném řetězci (nad potenciálně velkou abecedou) najít nejdelší Fibonacciho podslovo v lineárním čase? Hint: Pokud bych stavěl automat pro aktuální $F_i$, do jakého stavu se můžu dostat při nečekaném písmenku?

Úloha 1.2: Zjistěte, který podřetězec délky $k$ se v textu $S$ vyskytuje nejčastěji v průměrně lineárním čase s velikostí vstupu. Hint: Hashovací posuvné okénko, ale pozor na to, kam hashovat a co pak.

Úloha 1.3: Daný řetězec $S$ zrotujte na místě o $k$ znaků doprava v čase $O(s)$, $s=|S|$ (nezávisle na $k$). Na místě zde znamená, že krom samotného řetězce (jako modifikovatelného pole znaků) smíte použít jen $O(1)$ paměti navíc, nezávisle na $s$ a $k$.

Druhá sada domácích úkolů

Instrukce: Hoďte si 2-stěnnou kostkou (s rovnoměrným rozdělením) a začněte řešit příklad, jehož číslo vám padne. Pracujte na něm alespoň den. Pokud vás ani potom řešení nenapadne, hoďte si znovu. Příklady jsou řádově stejně těžké, ale rád bych, aby byla ditribuce řešení rovnoměrná :-)

Deadline na druhou sérii je 12. 11. 2014. Pokud si řešením nejste jisti, pošlete mi jej o týden dříve, ať vám můžu dát vědět.

Úloha 2.1: Na děravou šachovnici (na vstupu; některá pole chybí) rozestavte maximalní možný počet šachových věží tak, aby se navzájem neohrožovaly. Na děravé pole nesmíte věž položit, ale útočí přes něj.

Popište řešení úlohy jako tok či řez v nějaké síti a dokažte přímo, proč to úlohu řeší (proč je optimální řešení vytvořené sítě ekvivalentní s optimem původní úlohy). Dejte si záležet se zdůvodněním.

Úloha 2.2: Dokažte, že Dinicův algoritmus na síti s kapacitami nanejvýš $O(1)$ (tedy nějaká konstanta, představte si třeba 5 ;-) doběhne v čase $O(mn)$. Pozor na možné kapacity sítě rezerv až 2 i při původním omezení kapacit na 1.

Náměty na zápočtové práce

Jedna z možných inspirací je seznam námětů Martina Mareše. Ne všechny úlohy se vztahují k aktuální látce nebo jsou adekvátní (a to na obě strany), ale pro inspiraci je určitě vhodný. Samozřejmě můžete přijít i s vlastním nápadem.

Rád bych aby se řešené úlohy lišily, a po zkušenosti s kvalitami náhodných generátorů čísel 1-3 a 1-2 na to více dohlédnu osobně.

Až si vyberete, napište mi, jaký úkol chcete řešit, jakým zhruba způsobem, v jakém jazyce či prostředí. Domluvíme se pak na rozhraní (ideální je "knihovnička" s 1-3 veřejnými funkcemi) a jak to otestovat (tedy jak tomu dáte testovací data na ověření). Jak jsem psal, "dokumentace" stačí popisem těch funkcí v kódu.

Termín pro odevzdání je buď alespoň týden před tím, než budete chtít zápočet, nebo do konce zimního zkouškového. Počítejte s tím, že možná budu chtít nějaká vysvětlení či opravy, a může se též stát, že nebudu ve zkouškovém moc dostupný.

Výsledky

Nechcete-li být uvedeni pod svým jménem, napište mi přezdívku či to, že nechcete být uvedeni vůbec.

Alex Mansurov 1.3: OK, 2.1: OK
Edmondsův algoritmus: hotovo
Z
David Tomandl 1.2: OK, 2.1: OK
Dinic a s ním bip. max. párování: hotovo
Z
Gergely Tóth 1.2: OK, 2.1: OK
Nejdelší palindrom: hotovo
Z
Jakub Sosnovec 1.3: OK, 2.1: OK
Konvexní obal 2D/3D: hotovo
Z
Jana Novotná 1.3: OK, 2.1: OK
Rychlý A-C s počítáním výskytů: hotovo
Z
Jaroslav Brabec 1.1: OK, 2.1: OK
Algoritmus tří indů: zadáno
Jiří Hörner 1.2: ot., 1.3: OK, 2.1: OK,
Determ. prvočíselné testy: hotovo
Z
Lukáš Jelínek 1.2: ot., 1.3: OK, 2.1: OK
Srovnání a testy Splay a RB-stromů: hotovo
Z
Lukáš Meduna 1.3: OK, 2.1: OK
Genetický alg. na Mastermind vs bruteforce: hotovo
Z
Martin Červeň 1.3: OK, 2.1: otázky
Matej Baláž 1.3: OK, 2.1: OK
Srovnání třídících alg. a přesný medián: zadáno
Matúš Námešný 1.3: OK, 2.1: OK
Dinic a s ním bip. max. párování: hotovo
Z
Michal Staruch 1.3: OK, 2.1: OK,
Edmondsův algoritmus: hotovo
Z
Rastislav Galvánek1.3: OK, 2.2: OK
Rychlý A-C s počítáním výskytů: hotovo
Z
Robin Drahovsky 1.3: OK, 2.1: OK
Hranová souvislost a Dinic: hotovo
Z
Standa Kučera 1.3: OK, 2.1: OK,
Cenzor textu: hotovo
Z
Štěpán Šimsa 1.1: OK, 1.2: OK, 1.3: OK, 2.1: OK
Van Emde Boas: hotovo
Z
Tomáš Pavlín 2.1: OK, 2.1: OK
Nerekurzivní verze FFT: hotovo
Z
Veronika Klapová 1.3: OK, 2.1: OK
Goldberg, min. řezy a náhodné testování: zadáno
Vít Habada 1.3: OK, 2.1: OK,
FFT a testy: hotovo
Z

Zatím se spíše zdá, že někteří používáte dost neuniformní náhodné generátory :-/

Obsah cvičení

1. 10.Úvod, příklady ze zkoušek ADS1

Příklady ze zkoušek 2012/2013 a 2010/2011.

8. 10.Vyhledávání v textu

Teorie vyhledávání jednoho slova v textu, algoritmus Knuth–Morris–Pratt. Naivní algoritmus může být pomalý, i když nic nenajde. Jak poznat, že je jeden řetězec rotací druhého? Jak poznat, že je řetězec periodický? Algoritmus Rabin-Karp a vhodné posuvné hashovací okénko.

15. 10.Vyhledávání v textu

Zaskakuje Pavel Veselý.

Další cvičení na hledání více slov v textu a aplikace algoritmu Aho-Corasicové. Počítání výskytů, nejčastější slovo, význam zpětných hran v A-C a další jeho úpravy.

22. 10.Toky v sítích

Opakování: síť rezerv, algoritmy Ford-Fulkerson a Edmond-Karp.

Grafy, kge F-F nedoběhne (nad $\R$) a kde běží velmi dlouho. Maximální množina hranově disjunktních a vrcholově disjunktních $u-v$ cest v grafu. Toky v síti s kapacitami vrcholů. Max. párování v bipartitním grafu pomocí toků v sítích. Pokrývání (děravé) šachovnice kostičkami 2x1 pomocí párování.

29. 10.Toky v sítích - Dinitz

Podrobné rozebrání hledání blokujícího toku, jeho složitost. Hledání zlepš. cesty ve vrstevnatém grafu slepým průchodem, čištění sítě rezerv předem a průběžně. Amortizace čištění.

5. 11.Toky v sítích - Goldberg

Obecné preflow algoritmy na toky. Push-relabel a jeho varianty. Cvičení amortizace složitosti, rozebírání kroků Goldbergova algoritmu a několika variant.

12. 11.Děkanský den

19. 11.Fourierova transformace

Vlastnosti obecné Fourierovy transformace, násobení, sčítání, mocnění, odmocňování, dělení polynomů pomocí hodnot v několika bodech. Primitivní $n$-tá odmocnina z 1 a definice Fourierky jako vyhodncení polynomu v daných bodech $x_i=\omega^i$: $$\left(F(a_0, \dots, a_n)\right)_i=A(x_i)=A(\omega^i)=\sum_{j=0}^n a_j x_i^j=\sum_{j=0}^n a_j \omega^{ij}.$$

Fourierova transformace některých vektorů, linearita Fourierovy transformace. Počítání mocniny polynomu, podílu dělitelných polynomů, odmocniny odmocnitelného polynomu pomocí Fourierovy transformace.

26. 11.Rychlá fourierova transformace

Velké opakování Fourierovy transformace. Fourierova transformace jako projekce do ortogonální báze z vektorů $\vec{\omega_i}=(\omega^ij)_{j=0}^{n-1}$ skalárním součinem s vektory této báze. (Tyto sice nejsou normalizované (mají délku $n$), vyjde nám tedy $\sqrt{n}$-násobek souřadnic, což se ale zohlední dělwním $n$ při zpětné transformaci.)

Cvičení, že ortogonalita a normalita (nebo alespoň stejná délka) jsou nutné pro funkci projekce skalárním součinem. Cvičení, že $\vec{\omega_i}$ jsou ortogonální.

Výklad FFT jako rozděl a panuj na sudé a liché mocniny: $f(z)=f_S(z^2)+z f_L(z^2)$. Ukázka toho, jak toto nepomůže pro jedinou hodnotu $z$, ale pro $z\neq z'$ ale s $z^2=z'^2$ už nám to ušetří práci. Pro $z^n=1$, tedy $n$-tou primitivní odmocninu z jedné a $n=2^k$ to umožní ušetřit práci na všech $\log(n)$ hladinách.

Fourierova transformace vektorů $\vec{y_j}=(e^{2\pi i \frac{jk}{n} })_{k=0}^{n-1}$ na vektory $(0,0,\dots,0,n,0,\dots,0)$, důsledek, že lib. vektor jde vyjádřit lin. kombinací hodnot funkcí $\sin(jx)$ a $\cos(jx)$ v bodech $(0, 2\pi/n, 4\pi/n, \dots, (n-1)2\pi/n)$.

3. 12.Hradlové obvody, kombinační obvody a třídící sítě

Opakování hradlových a kombinačních obvodů. Počet $k$-vstupých hradel, klasifikace 2-vstupých hradel, důkaz, že stačí mít 2-vstupé AND, OR a NOT, stačí i NAND, ale pouze AND a OR nestačí. Pro $n$-vstupé hradlo OR je potřeba alespoň $\log_2 n$ vrstev sítě z 2-vstupých hradel.

Třídící sítě, even-odd mergesort z přednášky, výklad pomocí 0-1 lemmatu.

Lemma: Komparátorová síť třídí každý vstup právě když třídí každý vstup z $\{0,1\}$.

10. 12.Začátek složitosti a NP problémů

Zaskakuje Pavel Veselý.

Úvod do NP-těžkosti a základní převody. Ukázky převodů: Vrcholove pokryti grafu (komplementem z nezavisle mnoziny). Problém batohu. Řešení soustavy kvadratických rovnic (těžké už pro hodnoty $\{+1,-1\}$).

17. 12.Složitost a NP

Opakování definic NP, převodů, NP-těžkosti a NP-úplnosti. Zoo NP-úplných problémů a některé převody mezi nimi.

7. 1.Aproximační algoritmy

Opakování aproximace a ukázka neaproximovatelnosti. Konkrétní problémy:

Najděte $\Delta$-apx algoritmus pro max. nezávislou množinu vrcholů v grafech stupně $\leq\Delta$. Najděte 2-apx algoritmus pro vrcholové pokrytí (vertex cover). Najděte 2-apx algoritmus pro metrický TSP (problém obchodního cestujícího na úplných grafech splňujících trojúhelníkovou nerovnost mezi hranami). Hint: Dokažte, že vel. min. kostry je nanejvýš optimum TSP. Z takové kliky vyrobte aproxiamci.

Vše za předpokladu $NP\neq P$: Dokažte, že neexistuje lepší než $1.3$-apx algoritmus pro barevnost (jinak by šla přesně řešit 3-barevnost). Dokažte, že neexistuje žádná $k$-aproximace pro obecný TSP (jinak jde řešit Hamiltonovský cyklus). Dokažte, že neexistuje $(+k)$-aproximace pro max. kliku (alg. s aditivní chybou $\leq k$) (jinak jde nafouknutím grafu řešit klika přesně).

Materiály

Skripta k ADS 1+2 od Martina Mareše (pracovní verze).

Stránka Kuby Černého se skriptíčky k přednášce Základní grafové algoritmy.

Martin Mareš: Krajinou grafových algoritmů (lahůdky pro pokročilé; v první kapitole teorie toků v sítích)

Jaj