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

Cvičení vede každé pondělí 14:00 v S11 Tomáš Gavenčiak (gavento@ucw.cz). Cvičení sleduje přednášku Martina Mareše.

Zápočet

Účast na cvičení není povinná. Zápočet je za zisk 100 70 bodů za domácí úlohy. Do 14 dnů po zadání jsou úlohy za plný počet bodů, k některým je pak na cvičení dána nápověda, všechny jsou pak do konce semestru za polovic. Zadané úlohy jsou zveřejněny níže na této stránce.

Domácí úlohy a jednotlivá cvičení

Domácí úlohy odevzdávejte elektronicky emailem jako čistý text (u jednoduchých řešení stačí tělo emailu) nebo jako PDF, neposílejte prosím scany ani fotografie textu. Výjimku mají scany a fotky ručně kreslených obrázků, ty klidně přiložte jako JPEG či PNG.

U svých řešení vždy zdůvodněte, proč je řešení správné, lemmata či vlastnosti nalezeného řešení dokažte, u algoritmu dokažte správnost a uveďte časovou i paměťovou složitost.

Za velmi pěkně sepsané řešení (důkazy korektnosti a složitosti, obrázky, sazba, ...) máte šanci získat pár bodů navíc.

7. 10.Příklady ze zkoušek ADS1

Nebyly zadány žádné domácí úlohy.

14. 10.Příklady na prohledávání textu, algoritmus KMP

Cvičil Dušan Knop. Nebyly zadány žádné domácí úlohy.

21. 10.Příklady na hledání více slov v textu, algoritmus AC

Úloha zkratky (5b, nápověda 4. 11.)

Uvažujme, že stavíme vyhledávací automat z algoritmu AC bez zkratkových hran (tedy těch hran do všech nalezených slov, které jsou suffixem aktuálního stavu) a jen si v každém stavu poznamenáme, že v daném stavu končí nějaká slova (která jsou jeho suffixem), a vždy z něj půjdeme po zpětných hranách a najdeme při tom všechna slova, která tam končí.

Ukažte, že toto je asymptoticky pomalejší, než AC ukázaný na přednášce.

Úloha frekvence (10b, nápověda 4. 11.)

Na vstupu je množina slov $S$ a text $t$, úkolem je spočítat počet výskytů každého slova v čase $O(\sum_{s_i\in S} |s_i| + |t|)$ ale nezávisející na počtu nálezů (který může být velký).

Úloha začínající (6b, nápověda 4. 11.)

Modifikujte AC tak, aby pro každou pozici v textu našel nejdelší slovo, které na dané pozici začíná, aniž byste zhoršili jeho složitost. (Na cvičení jsme si ukazovali, jak pro každou pozici najít nejdelší slovo, které tam končí.)

Úloha cenzura-a (6b, nápověda 4. 11.)

Dokončete myšlenku úlohy Cenzura ze cvičení. (Opakovaně z textu vyškrtávám nejlevěji končící slovo. Pozor na to, že vyškrtnutím slova může vzniknout jiné slovo začínající vlevo od vyškrtnutí, např. text aaaabbbb se zakázaným slovem ab se zredukuje až na prázdný řetězec.) Ve cvičení jsme se dostali k tomu, že je třeba si pro každý stav a možné následující písmenko předpočítat (nebo chytře cachovat), kam po zpětných hranách a následně po jedné dopředné dojdu.

Jak postavit tabulku takových přechodů z každého stavu pro každé znak abecedy, když je abeceda malá ($k$ písmen, např. 26)?

Úloha cenzura-b (12b, nápověda 4. 11.)

Doplňková úloha k problému cenzura-a:

Jak reprezentovat a postavit takovou "tabulku" přechodů, když by abeceda byla velká a většina jejích písmen se v seně ani nevyskytla? (Představte si třeba unicode.) Použijte nějaké vhodné datové struktury; drobné zhoršení složitosti (třeba o $\log$) je přijatelné.

28. 10.Státní svátek

4. 11.Úvod a aplikace toku v síti, Ford-Fulkerson, Dinic

Úloha menger (12b, nápověda 18. 11.)

Dokažte Mengerovu větu z věty o dualitě max. toku a min. řezu. Hint: použijte síť pro hledání vrcholově disjunktních $u$-$v$ cest v daném grafu.

Mengerova věta: Maximální počet vrcholově disjunktních $u$-$v$ cest v grafu je roven velikosti minimálního vrcholového $u$-$v$ řezu (tedy podmnožiny vrcholů grafu takových, že mezi $u$ a $v$ už mimo ně nevede žádná cesta).

Úloha domino (6b, nápověda 18. 11.)

Pomocí toků v síti navrchněte algoritmus zjišťující, kolik nejvíce kostiček domina (1x2) lze umístit na šachovnici bez některých políček (šachovnice je na vstupu). Kostičky se nesmějí překrývat ani ležet na dírách.

Úloha projekty (12b, nápověda 18. 11.)

Mějme projekty $P_1, \dots, P_k$. Za realizaci projektu $P_i$ dostaneme odměnu $r_i$, ale potřebujeme k tomu množinu zdrojů $S_i$. Každý zdroj nás stojí náklady $c_i$, ale jakmile ho jednou koupíme, můžeme ho použít ve více projektech.

Navrhněte algoritmus, který pomocí toků v síti zjistí, které projekty realizovat a jaké zdroje si koupit, aby byl celkovy zisk co největší.

11. 11.Opakování a modifikace Goldbergova algoritmu

Úloha věže (6+2b, nápověda 25. 11.)

Na vstupu budiž děravá šachovnice, úkolem je zjistit, jaký je maximální počet šachových věží, které můžeme postavit mimo díry, když a) se ohrožují i přes díry (tedy na celém řádku či sloupci), nebo b) se přes díry neohrožují (nestřílí přes díry).

18. 11.Hradlové a třídící sítě

Úloha XOR (4b, nápověda 2. 12.)

Sestrojte hradlo XOR ze 4 hradel NAND (a dokažte správnou funkci).

Úloha vstupy (5b, nápověda 2. 12.)

Dokažte, že $n$-vstupé hradlo OR sestrojené z 2-vstupých hradel OR potřebuje alespoň $\Omega(\log n)$ hladin.

Úloha permutace (8b, nápověda 2. 12.)

Popište, jak pro zadanou permutaci $n$ čísel vytvoříte komparátorovou síť hloubky $O(\log n)$, která ji setřídí. Výsledná komparátorová síť nemusí třídit žádnou jinou permutaci.

Například permutaci $5,6,7,8,1,2,3,4$ setřídí síť s jedinou vrstvou obsahující komparátory (čísla vodičů jsou 1-8): 1 a 5, 2 a 6, 3 a 7, 4 a 8.

Úloha dělitelnost (11b, nápověda 2. 12.)

Pro zadané $k$ a $n$ navrhněte hradlovou síť, která pro $n$-bitové číslo na vstupu (ve dvojkové soustavě) rozhodne, zda je dělitelné $k$ v $O(\log n)$ hladinách a s $O(n)$ hradly ($k$ bereme jako konstantu). Část bodů (7) získáte i jen za konstrukci takové sítě, která rozhoduje dělitelnost trojkou.

Úloha násobení (12b, nápověda 2. 12.)

S pomocí úloh ze cvičení (násobení konstantou; převod součtu tří čísel na součet dvou čísel v konst. hloubce) sestrojte hradlový obvod násobící dvě $n$-bitová binární čísla na vstupu v $O(\log n)$ hladinách.

25. 11.Bitonické třídění a zametací algoritmy

Úloha obal-a (8b, nápověda 9. 12.)

Navrhněte, jak spočítat konvexní obal $n$ bodů v čase $O(nh)$, kde $h$ je velikost výsledného konvexního obalu. Body na vstupu nejsou nijak setříděny. Můžete předpokládat, že číslo $h$ dostanete na vstupu.

Hint: Přímkou lze zametat i jinak, než nudným posuvem.

Úloha obal-b (12b, nápověda 9. 12.)

Inspirováni řešením úlohy obal-a navrhněte algoritmus, který najde konvexní obal $n$ bodů v čase $O(n\log h)$. Můžete předpokládat, že číslo $h$ dostanete na vstupu.

Hint: Spočtěte konv. obaly pro $n/h$ skupin po $h$ bodech a pak jejich obaly spojte variantou řešení obal-a.

Úloha obsah (10b, nápověda 9. 12.)

Spočítejte obsah obecného (tedy ne nutně konvexního) $n$-úhelníku na vstupu. Zadán je posloupností souřadnic jeho bodů v pořadí jak jsou na obvodu. Optimální řešení je v $O(n)$, za řešení v $O(n\log n)$ je 8 bodů.

2. 12.Zametací algoritmy a lokalizace bodu ve 2D (a 3D), perzistentní AVL stromy

Nebyly zadány žádné domácí úlohy.

9. 12.Diskrétní a rychlá fourierova transformace

Úloha fffunkce (13b, nápověda 6. 1.)

Uvažujme reálnou funkci $f$ definovanou na intervalu $[0, 2\pi)$. Pokud její hodnoty navzorkujeme v $n$ pravidelně rozmístěných bodech, získáme vektor ${\bf f}\in\R^n$ o složkách ${\bf f}_j = f(2\pi j/n)$. Jak vypadá Fourierova transformace tohoto vektoru pro následující funkce:

a. $e^{ikx}$ pro $k\in\N$,

b. $\cos kx$ pro $k\in\N$ a

c. $\sin kx$ pro $k\in\N$.

Úloha ffffunkce (12b, nápověda 6. 1.)

Podobně jako v předchozím cvičení dokažte, že pro libovolnou reálnou funkci na $[0, 2\pi)$ existuje lineární kombinace funkcí $\sin kx$ a $\cos kx$, která při vzorkování v $n$ bodech není od zadané funkce rozlišitelná.

Tedy že pro každý vektor ${\bf f}\in\R^n$ (který výše získáme jako ${\bf f}_j=f(j*2\pi/n)$) existují vektory $a,b\R^n$ takové, že pro každé $0\leq j\leq n-1$ platí:

$${\bf f}_j=\sum_{k=0}^{n-1}\left( {\bf a}_k\sin\frac{jk2\pi}{n} + {\bf b}_k\cos\frac{jk2\pi}{n} \right)$$

Koeficienty ${\bf a}_k$ a ${\bf b}_k$ lze přítom snadno získat z Fourierova obrazu vektoru ${\bf f}$

16. 12.Převody NP-úplných problémů

Cvičil Tomáš Masařík.

Úloha fourierka (9b, bez nápovědy)

Najděte transformace následujících typů vektorů:

a. $(0,\dots,0)$, $(1,\dots,1)$ a $(k,\dots,k)$

b. $(\omega^0,\omega^1,\dots,\omega^{n-1})$, $(\omega^0,\omega^2,\dots,\omega^{2(n-1)})$ a obecně $(\omega^{0k},\omega^{1k},\dots,\omega^{k(n-1)})$.

c. $(1,0,0,\dots,0)$ a obecně $(0,0,\dots, 0, 1, 0, \dots, 0)$ (jednička na $k$-té pozici).

Úloha na-stromy (7b, bez nápovědy)

Určete výpočetní složitost problému nezávislé množiny na stromech. Vstupem jsou graf $G$, který je strom, a čislo $k$. Výstupem je informace, zda má $G$ nezávislou množinu velikosti alespoň $k$.

Úloha kvadratická (12b, bez nápovědy)

Dokažte, že problém řešení soustavy kvadratických rovnic je NP-těžký. Vstupem je soustava kvadratických rovnic s celočíselnými koeficinety, výstupem odpověď, zda má soustava řešení v $\R$.

Příklad takové soustavy je třeba: $x_1^2+42x_1-x_1x_2=0$, $5x_3-5x_1x_3=x_2+1$.

Hint: Převeďte na tento problém instanci SATu a zakódujte booleovské hodnoty jako speciální hodnoty proměnných.

23. 12.Vánoční svátky

30. 12.Vánoční svátky

6. 1.NP-těžké problémy, aproximace, speciální případy

Úloha hamilton (10b, bez nápovědy)

Pro daný graf $G$ popište, jak vytvořit graf $H$, že platí: $G$ má hamiltonovskou cestu právě když $H$ má hamiltonovskou kružnici. Dokažte obě implikace. Převod musí být algoritmicky proveditelný v polynomiálním čase (nemusíte ale převod popsat jako přesný algoritmus, jen nesmí být příliš náročný).

Co z toho plyne o vztahu složitosti problému hamiltonovské cesty a hamiltonovské kružnice?

Úloha subsetsum (8b, bez nápovědy)

V problému SubsetSum je dána množina celých čísel $M$ a číslo $k$, otázkou je rozhodnout, zda existuje podmnožina $M'\subseteq M$ se součtem právě $k$. Unární SubsetSum je stejný problém, kde je každé číslo $x$ na vstupu reprezentováno $x$ jedničkami (tedy vstup 1,5,3 by byl zakódován jako 101111101110).

Dokažte, že unární SubsetSum je řešitelný v polynomiálním čase.

Úloha setcover (8b, bez nápovědy)

V problému SetCover je na vstupu systém množin $\mathcal{S}=\{M_1,\dots M_k\}$, $M_i\subseteq\{1,2,\dots n\}$. Otázkou je, kolik nejméně množin $\mathcal{S'}\subseteq\mathcal{M}$ je potřeba, aby jejich sjednocení byla všechna čísla $\{1,2,\dots n\}.

Navrhněte 5-aproximační algoritmus pro případ, že každá $|M_i|\leq 5$.

Výsledky

Získaný počet bodů najdete v online tabulce:

Pokud nesouhlasíte se zveřejněním pod svým skutečným jménem (např. nechcete být vyhledatelní), dejte mi vědět, jaký chcete použít pseudonym (a pak ho uvádějte i na svých řešeních) či zda nechcete být uvedeni vůbec.

Materiály

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

Jaj