ADS II (2020/2021)

Cvičení k přednášce Algoritmy a datové struktury II

Doporučená literatura

Průvodce labyrintem algoritmů
Pro zájemce o složitější grafové algoritmy - Krajinou grafových algoritmů

Organizace

K získání zápočtu je nutno nasbírat 90 bodů.

Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (za vyřešení více úkolů z jednoho cvičení je stále 10 bodů).

Aktivita na cvičení bude odměněna $\frac{10}{3}$ body (více aktivity na jednom cvičení je stále $\frac{10}{3}$ bodů).

Vzhledem k současné situaci jsou cvičení prováděna online přes Zoom.

Body

Body budou zapsané v SISu.

Probrané příklady

30.9.
7.10.
14.10.
21.10.
4.11.
11.11.
18.11.
25.11.
2.12.
9.12.
16.12.
6.1.

Úkoly

Na řešení úkolů jsou vždy dva týdny. Úkoly je možné odevzdávat mailem (preferovaná varianta) nebo na papíru na cvičení. Každý úkol musí obsahovat zdůvodnění, proč je řešení korektní (např. samotný pseudokód nestačí). Pokud je úkolem navrhnout algoritmus, pak je také vždy zapotřebí uvést časovou a prostorovou složitost, včetně zdůvodnění.

30.9. (do 14.10.)

Inverze matice: Navrhněte algoritmus typu Rozděl a panuj na výpočet inverze trojúhelníkové matice $n \times n$ v čase lepším než $\Omega(n^3)$. Jako podprogram se může hodit Strassenovo násobení matic. Můžete předpokládat, že $n$ je mocnina dvojky.
Dokažte nebo vyvraťte alespoň 2 z následujících tvrzení:
a. $f(n) \in O(g(n))$, potom $g(n) \in O(f(n))$

b. $f(n) \in O(g(n))$, potom $2^{f(n)} \in O(2^{g(n)})$

c. $f(n \in O(g(n))$, právě tehdy když $g(n) \in \Omega(f(n))$
Hrdina Théseus se vypravil do hlubin labyrintu a snaží se najít poklad. Chodbami labyrintu se ovšem pohybuje hladový Mínótauros a snaží se najít Thésea. Labyrint má tvar čtvercové sítě, jejíž každé políčko je buďto volné prostranství, anebo zeď. Známe mapu labyrintu a počáteční polohy Thésea, Mínótaura a pokladu. Théseus se v jednom tahu pohne na vybrané sousední políčko. Poté se vždy dvakrát pohne o políčko Mínótauros: pokaždé se pokusí zmenšit o 1 rozdíl své a Théseovy x-ové souřadnice, pokud to nejde, pak y-ové, pokud nejde ani to, stojí. Poraďte Théseovi, jak má dojít k pokladu a vyhnout se Mínótaurovi.
V Tramtárii jezdí po železnici samé rychlíky, které nikde po cestě nestaví. V jízdním řádu je pro každý rychlík uvedeno počáteční a cílové nádraží, čas odjezdu a čas příjezdu. Nyní stojíme v čase $t$ na nádraží $a$ a chceme se co nejrychleji dostat na nádraží $b$. Navrhněte algoritmus, který najde takové spojení. Co když chceme mezi všemi nejrychlejšími spojeními najít takové, v němž je nejméně přestupů.

7.10. (do 21.10.)

Navrhněte algoritmus, který v lineárním čase nalezne tu z rotací zadaného řetězce, jež je lexikograficky minimální.
Je dáno slovo. Chceme nalézt jeho nejdelší vlastní prefix, který je současně suffixem.
Pestrý budeme říkat takovému řetězci, jehož všechny rotace jsou navzájem různé. Kolik existuje pestrých řetězců v $\Sigma^n$ pro konečnou abecedu $\Sigma$ a prvočíslo $n$?

14.10. (do 28.10.)

Ukažte, jak pro dané dva řetězce najít jejich nejdelší společný podřetězec.
Pro daný slovník chceme vytvořit datovou strukturu, která bude umět odpovídat na dotazy typu "je ve slovníku rotace slova X"?
Pěstovaný strom říkejme zakořeněnému stromu, jehož hrany k synům mají v každém vrcholu určené uspořádaní zleva doprava. Strom se osekává tak, že si vybereme kořen podstromu, vše mimo podstrom odstraníme a pak ještě můžeme odseknout některé hrany zleva a zprava v kořeni (zbude tedy souvislý úsek hran z kořene podstromu dolu a podstromy, které pod nimi visí). Jak zjistit o dvou pěstovaných stromech, zda lze jeden získat osekáním druhého?

21.10. (do 4.11.)

Uvažujme, že algoritmus pro hledání maximálního toku hledá zlepšující cesty pouze po směru hran. Takovýto algoritmus obecně nefunguje. Zachránilo by ho, kdyby se braly postupně nejkratší zlepšující cesty?
Pokračujeme v předchozím cvičení. Existuje vždy nějaká posloupnost zlepšujících cest po směru hran, která zaručí maximální tok?
Pro daný neorientovaný graf nalezněte co největší $k$ takové, že graf je hranově $k$-souvislý. (To znamená, že je souvislý i po odebrání nejvýše $k - 1$ hran.)

4.11. (do 18.11.)

Mějme šachovnici $r \times s$, z níž políčkožrout sežral některá políčka. Chceme na nesežraná políčka rozmístit kostky velikosti $1 \times 2$ políčka tak, aby každé nesežrané políčko bylo pokryto právě jednou kostkou. Kostky je povoleno otáčet.
Svišti: Na louce je n svišťů a m děr v zemi (obojí je zadáno jako body v rovině nebo raději body v nepříliš velké celočíselné mřížce). Když se objeví orel, zvládne svišť uběhnout pouze $d$ metrů, než bude uloven. Kolik maximálně svišťů se může zachránit útěkem do díry, když jedna díra pojme nejvýše jednoho sviště? A co když pojme $k$ svišťů?
Sestrojte vrstevnatou síť, v níž hledání blokujícího toku trvá $\Omega(nm)$.

11.11. (do 25.11.)

Sestavte hradlovou síť ze čtyř hradel nand (negovaný and), která počítá xor dvou bitů.
Definujeme výhybku – to je analogie operátoru ?: v jazyce C, tedy ternární booleovské hradlo se vstupy $x_0$, $x_1$ a $p$, jehož výsledkem je $x_p$. Ukažte, že libovolnou k-vstupovou booleovskou funkci lze spočítat obvodem složeným pouze z výhybek a konstant. Jak by se naopak skládala výhybka z binárních hradel?
Sestrojte hradlovou síť hloubky O(log n), která porovná dvě n-bitová čísla x a y a vydá jedničku, pokud $x < y$.

18.11. (do 2.12.)

Modifikujte sčítací síť, aby odčítala.
Dokažte nula-jedničkový princip: pro ověření, že komparátorová síť třídí všechny vstupy, ji postačí otestovat na všech posloupnostech nul a jedniček.
Sestrojte hradlovou síť, která pro zadané dvojkové číslo $x_{n-1} \dots x_0$ spočítá dolní celou část z jeho dvojkového logaritmu, čili nejvyšší $i$ takové, že $x_i = 1$.

25.11. (do 9.12.)

Spočítejte Fourierovy obrazy následujících vektorů z $\mathbb{C}^n$ pro sudé $n$:
- $(1, -1, 1, -1, \dots , 1, -1)$
- $(\omega^0, \omega^{2},\omega^{4}, \dots ,\omega^{2n-2})$
Volba $\omega$: Ve Fourierově transformaci máme volnost v tom, jakou primitivní odmocninu $\omega$ si vybereme. Ukažte, že Fourierovy obrazy pro různé volby $\omega$ se liší pouze pořadím složek.

2.12. (do 16.12.)

Zvolme pevné $n$ a $\omega = e^{2\pi i/n}$. Označíme $s^k$ a $c^k$ vektory získané navzorkováním funkcí $sin (2k\pi x)$ a $cos (2k\pi x)$ (sinus a cosinus s frekvencí $k$) v $n$ bodech intervalu $[0, 1)$. Ukažte, že Fourierův obraz vektorů $s^k$ a $c^k$ vypadá pro $0 < k < n/2$ následovně:
- $F(s^k) = (0, \dots , 0, n/2i, 0, \dots , 0, -n/2i, 0, \dots , 0),$
- $F(c^k) = (0, \dots , 0, n/2, 0, \dots , 0, n/2, 0, \dots , 0),$
přičemž vektory mají nenulu na pozicích $k$ a $n - k$. Pozor na speciální případy $s^0$, $s^{n/2}$, $c^0$ a $c^{n/2}$.
Konvoluce vektorů $x$ a $y$ je vektor $z = x * y$ takový, že $z_j = \sum_k x_k y_{j-k}$, přičemž indexujeme modulo $n$. Tuto sumu si můžeme představit jako skalární součin vektoru $x$ s vektorem $y$ napsaným pozpátku a zrotovaným o $j$ pozic. Konvoluce nám tedy řekne, jak tyto "přetočené skalární součiny" vypadají pro všechna $j$. Dokažte následující vlastnosti:
- $x * y = y * x$ (komutativita)
- $x * (y * z) = (x * y) * z$ (asociativita)
- $x * (\alpha y + \beta z) = \alpha(x * y) + \beta(x * z)$ (bilinearita)
- $F(x * y) = F(x) \odot F(y)$, kde $\odot$ je součin vektorů po složkách.
Vyberte si nějaké praktické využití Frourierovy transformace (spektrální analýza, zpracování obrazu, zpracování signálu, kompresní formáty, ...) a popište ho (= krátký referát na cca 1 stránku).

9.12. (do 23.12.)

Pro 1 libovolný následující rozhodovací problém dokažte, že je NP-Ú. To můžete ukázat tak, že na něj převedete nějaký jiný NP-Ú problém a ukážete, že je zároveň v NP. Převody, které jsme ukázali na cviku neberu.
- SAT: splnitelnost logických formulí v CNF
- 3-SAT: každá klauzule obsahuje max. 3 literály
- 3,3-SAT: navíc se každá proměnná vyskytuje nejvýše třikrát
- Nezávislá množina: existuje množina alespoň $k$ vrcholů, mezi nimiž nevede žádná hrana?
- Klika: existuje úplný podgraf na $k$ vrcholech?
- Barvení grafu: lze obarvit vrcholy $k$ barvami (přidělit každému vrcholu číslo od $1$ do $k$) tak, aby vrcholy stejné barvy nebyly nikdy spojeny hranou)? To je NP-úplné už pro $k = 3$.
- Hamiltonovská cesta: existuje cesta obsahující všechny vrcholy?
- Hamiltonovská kružnice: existuje kružnice obsahující všechny vrcholy?
- Součet podmnožiny: má daná množina přirozených čísel podmnožinu s daným
- Batoh: jsou dány předměty s váhami a cenami a kapacita batohu, chceme najít co nejdražší podmnožinu předmětů, jejíž váha nepřesáhne kapacitu batohu. Aby se jednalo o rozhodovací problém, ptáme se, zda existuje podmnožina s cenou větší nebo rovnou zadanému číslu.
- Dva loupežníci: lze rozdělit danou množinu čísel na dvě podmnožiny se stejným součtem?
- $Ax = 1$ (soustava nula-jedničkových lineárních rovnic): je dána matice $A \in \{0, 1\}^{m \times n}$. Existuje vektor $x \in \{0, 1\}^n$ takový, že $Ax$ je rovno vektoru samých jedniček?

16.12. (do 30.12.)

Problém MaxCut: vrcholy zadaného grafu chceme rozdělit do dvou množin tak, aby mezi množinami vedlo co nejvíce hran. Jinými slovy chceme nalézt bipartitní podgraf s co nejvíce hranami. Rozhodovací verze tohoto problému je NP-úplná, optimalizační verzi zkuste v polynomiálním čase 2-aproximovat.
Hledejme vrcholové pokrytí následujícím hladovým algoritmem. V každém kroku vybereme vrchol nejvyššího stupně, přidáme ho do pokrytí a odstraníme ho z grafu i se všemi již pokrytými hranami. Je nalezené pokrytí nejmenší? Nebo alespoň $O(1)$-aproximace nejmenšího?
Uvažujme následující algoritmus pro nejmenší vrcholové pokrytí grafu. Graf projdeme do hloubky, do výstupu vložíme všechny vrcholy vzniklého DFS stromu kromě listů. Dokažte, že vznikne vrcholové pokrytí a že 2-aproximuje to nejmenší.

6.1. (do neomezeně)

V rovině je dána množina červených a množina zelených bodů. Sestrojte přímku, která obě množiny oddělí. Na jedné její straně tedy budou ležet všechny červené body, zatímco na druhé všechny zelené. Navrhněte algoritmus, který takovou přímku nalezne. Body mohou ležet i na přímce samotné.
Je dána množina obdélníků, jejichž strany jsou rovnoběžné s osami souřadnic. Spočítejte obsah jejich sjednocení. Pozor na to, že obdélníky se mohou překrývat.
Máme zadané dva konvexní mnohoúhelníky. Jak zjistit, zda se protínají?