Algoritmy a datové struktury II

Cvičení k přednášce Algoritmy a datové struktury II [NTIN061] v zimním semestru 2019/2020. Probíhá v úterý od 14:00 v S7

Požadavky na zápočet

Co jsme dělali

1. 10. 2019
Opakování - asymptotika a master theorem. Složitost v nejhorším případě lze zachránit amortizací. Naivní algoritmus hledání textu je pomalý. [Příklady 1-5]
8. 10. 2019
Algoritmus KMP a konstrukce zpětných hran. Aplikace KMP na rotace, zjištění periody slova a osekávání stromů. Nejdelší slovo jako podposloupnost. [Příklady 1-4]
15. 10. 2019
Algoritmus AC a konstrukce zkratkových hran. Proč nemůžeme hlásit výskyty průchodem zpětných hran ani je mít předpočítané jako množiny u každého stavu. Frekvence výskytů hledaných slov. [Příklady 1-5]
22. 10. 2019
Algoritmus Rabin-Karp a jeho aplikace na hledání v textu. Úvod do toků, Ford-Fulkersonův algoritmus a jeho chování na celočíselných a racionálních sítích. [Příklady 1-7]
29. 10. 2019
Dinicův algoritmus a jeho časová složitost na jednotkových a celočíselných sítích. Věže na šachovnici, dopravní problém a jak zaokrouhlit matici. [Příklady 1-7]
5. 11. 2019
Goldbergův algoritmus a jeho analýza. [Příklady 1-2]
19. 11. 2019
Cvičil Karel Král. Komplexní čísla, $n$-té odmocniny jedničky a Fourierova transformace. Výsledek DFT aplikované na jednoduché vektory. Inverzní DFT a její matice. [Příklady 1-5]
26. 11. 2019
Poslední ohlédnutí za Fourierovou transformací. Různé definice hradlových sítí a jejich ekvivalence. Počítání obecné booleovské funkce hradlovou sítí a proč potřebujeme velkou síť. [Příklady 1-6]
3. 12. 2019
Porovnání dvou čísel, sčítání a testování dělitelnosti. Úvod do hradlových sítí, maximum a zatřídění prvku do posloupnosti. [Příklady 1,2,4,5]
10. 12. 2019
Úvod do rozhodovacích problémů a složitosti. Převody mezi různými problémy. [Příklady 1-3]
17. 12. 2019
Poslední převody. Jak řešit těžké problémy v praxi - začali jsme omezenými vstupy. [Příklady 1-6]

Domácí úkoly

Úkoly odevzdávejte buď osobně před začátkem cvičení nebo pomocí emailu. Pokud je to alespoň trochu možné, neodevzdávejte prosím přes mail naskenované ruční řešení (ideálně sázejte v $\LaTeX \text{u}$).

1. Palindromický prefix (do 15.10.) 5b.
Najděte nejdelší prefix slova $\alpha$, který je palindromem.
2. Speciální výskyty (do 22.10) 5b.
Navrhněte algoritmy, které dostanou na vstupu slova $J_1, \ldots ,J_k$ a text $S$. Výstupem algoritmu pak je pro každou pozici,
  • index pozice a nejdelší slovo, které na ní končí,
  • index pozice a nejkratší slovo, které na ní končí,
  • index pozice a nejdelší slovo, které na ní začíná,
  • index pozice a nejkratší slovo, které na ní začíná.
3. Maximální cirkulace (do 29.10.) 5b.
Cirkulace v síti je tok nulové velikost - tj. pro všechny vrcholy (včetně zdroje a stoku) platí, že jejich přítok je roven odtoku. Najděte v zadané síti cirkulaci, která maximalizuje tok přes hranu $e$. Podstatná je redukce na problém maximálního toku, tentokrát není potřeba optimalizovat časovou složitost (jelikož závisí na konkrétním algoritmu pro hledání maximálního toku).
4. Domino na šachovnici (do 5.11.) 5b.
Mějme šachovnici $r \times s$ se seznamem zakázaných políček. Chceme na povolená políčka rozmístit kostky domina velikosti $1 \times 2$ políčka tak, aby každé povolené políčko bylo pokryto právě jednou kostkou. Kostky je povoleno otáčet.
5. Fourierovy obrazy (do 26.11.) 6b.
Spočítejte Fourierovy obrazy následujících vektorů (každý za 2b.):
  • $(1,0,1,0, \ldots ,1,0)$,
  • $(\omega^0, \omega^1, \ldots, \omega^{n-1} )$,
  • $(\omega^0, \omega^2, \ldots, \omega^{2(n-1)} )$ kde $\omega = e^{2\pi i / n}$.
6. Výhybka (do 3.12.) 5b.
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$. Poskládejte výhybku z hradel AND, OR, NOT, a ukažte, že libovolnou $k$-vstupovou booleovskou funkci lze spočítat obvodem složeným pouze z výhybek a konstant.
7. Hardwired net (do 10.12.) 5b.
K dispozici máte komparátor, tedy obvod který na vstupu dostane dvojici $x,y\in \Sigma$ a výstupem je uspořádaná dvojice $(\min(x,y),\max(x,y))$. Na vstupu dostanete pevnou permutaci $\sigma$ na množině $x_1,\ldots,x_n$. Postavte komparátorovou síť, která na výstupu vydá tuto permutaci setřízenou. Jediný způsob jak prohodit dva prvky je použít komparátor, a všechny komparátory posílají $\max(x,y)$ na svůj pravý výstup. Navrhněte tuto síť, určete odhad počtu hradel a hloubku sítě (hloubka by měla být $O(\log n))$.
8. $k$-barevnost (do 17.12.) 5b.
Převeďte problém $k$-barevnosti na $k$-SAT pro $k \geq 2$. Správné řešení obsahuje popis redukce a důkaz její správnosti!
9. Loupežníci (do 7.1.) 5b.
Máte algoritmus pro rozhodovací verzi loupežníků. Jak naleznete rozdělení mezi loupežníky? Zde se nám jedná o to najít řešení, pokud můžete položit polynomiálně mnoho dotazů rozhodovací verzi loupežníků.

Bonusové domácí úkoly

B1. Zašifrované seno (do 29.10.) 5b.
Substituční šifra funguje tak, že zpermutujeme znaky abecedy: například permutací abecedy $\mathtt{abcdeo}$ na $\mathtt{dacebo}$ zašifrujeme slovo $\mathtt{abadcode}$ na $\mathtt{dadecoeb}$. Zašifrovaný text je méně srozumitelný, ale například vyzradí, kde v originálu byly stejné znaky a kde různé. Buď dáno seno zašifrované substituční šifrou a nezašifrovaná jehla. Najděte všechny možné výskyty jehly v originálním seně (tedy takové pozice v seně, pro něž existuje permutace abecedy, která přeloží jehlu na příslušný kousek sena).
B2. Doly a továrny (do 26.11.) 5b.
Uvažujeme o vybudování dolů $D_1,\ldots,D_p$ a továren $T_1,\ldots,T_q$. Vybudování dolu $D_i$ stojí cenu $d_i$ a od té doby důl zadarmo produkuje neomezené množství $i$-té suroviny. Továrna $T_j$ potřebuje ke své činnosti zadanou množinu surovin a pokud jsou v provozu všechny doly produkující tyto suroviny, vyděláme na továrně zisk $t_j$. Vymyslete algoritmus, jenž pro zadané ceny dolů, zisky továren a bipartitní graf závislostí továren na surovinách stanoví, které doly postavit, abychom vydělali co nejvíce.
B3. Rotace (do 10.12.) 5b.
Nechť $y$ je vektor, který vznikl rotací $x$ o $k$ pozic $y_j = x_{(j+k) \mod n}$. Jak spolu souvisí $DFT(x)$ a $DFT(y)$?
B4. Rychlejší formule (do 7.1.) 5b.
Dokažte, že každou booleovskou formuli lze přeložit na booleovský obvod jehož hloubka je logaritmická v délce formule.

Tabulka výsledků

Užitečné odkazy