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
- Na každém cvičení bude zadán (alespoň) jeden úkol s odevzdáním do začátku příštího cvičení.
- Na zápočet je třeba dosáhnout 60% celkového počtu bodů z regulérních domácích úkolů.
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.
Užitečné odkazy