Michal Opler

A PhD student of Discrete Models and Algorithms

© 2022. Hyde theme.

Algoritmy a datové struktury II

Cvičení k přednášce Algoritmy a datové struktury II [NTIN061] v zimním semestru 2018/2019. Probíhá v pátek od 12:20 v S11.

Požadavky na zápočet

Co jsme dělali

5. 10. 2018
Asymptotická složitost a porovnávání funkcí. Naivní algoritmus hledání textu je pomalý. Složitost v nejhorším případě lze zachránit amortizací. [Příklady 1-4]
12. 10. 2018
Algoritmus KMP a konstrukce zpětných hran. Aplikace KMP na rotace, zjištění periody slova a osekávání stromů. [Příklady 1-4]
19. 10. 2018
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]
26. 10. 2018
Rabin-Karpův algoritmus a volba hashovací funkce. Nejčastější výskyty, nejdelší podřetězce a hledání ve dvou dimenzích. [Příklady 1-3]
2. 11. 2018
Toky v sítích, Ford-Fulkersonův algoritmus a jeho chování na jednotkových, celočíselných a racionálních kapacitách. Hranově a vrcholově disjunktní cesty. Věže na vykousané šachovnici. [Příklady 2-7]
9. 11. 2018
Dinicův algoritmus a jeho složitost na jednotkových kapacitách. Parlamentní kluby a zaokrouhlování matice. Úvod do preflow–push algoritmu pro toky. [Příklady 1-4]
16. 11. 2018
Cvičení odpadlo.
23. 11. 2017
Goldbergův algoritmus a důkaz jeho správnosti. Komplexní čísla, $n$-té odmocniny jedničky a Fourierova transformace. Výsledek DFT aplikované na jednoduché vektory. Doporučuju zajímavé pohledy na DFT v angličtině a češtině. [Příklady 1-2]
30. 11. 2017
Inverzní DFT a její matice. Rychlá Fourierova transformace a použití DFT na násobení polynomů. Spektrální rozklad a nastínění jeho využití ke zpracování zvuku a obrazu.
7. 12. 2018
Cvičil Karel Král. Hradlové a komparátorové sítě, třídění sléváním podle Batchera. Jak udělat bubble sort, insert, findMax, insertsort. Nalezení nejlevější jedničky.
14. 12. 2018
Hradlové sítě, jak spočítat libovolnou booleovskou funkci pomocí hradel AND, OR, NOT. Binární sčítačka, binární odčítačka a jak rychle sečíst větší množství čísel. [Příklady 1, 3, 4]
21. 12. 2018
Rozhodovací problémy, třídy P a NP. Jak ukázat, že jeden problém je alespoň tak těžký jako druhý. NP-těžké a NP-úplné problémy. Různé převody mezi problémy. [Příklady 1-4]
4. 1. 2019
Získání řešení z rozhodovacích verzí problémů. Problémy jdou řešit na jednodušších podtřídách (např. nezávislá množina ve stromu). Pseudopolynomiální a aproximační algoritmy. [Příklady 1-5]
11. 1. 2019
Trocha opakování z minula. Aproximační algoritmy a aproximační schémata. Rychlý průlet geometrickými algoritmy, lokalizace bodu v rovině. [Příklady 1-4]

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 19.10.) 5b.
Najděte nejdelší prefix slova $\alpha$, který je palindromem.
2. Speciální výskyty (do 26.10) 4b.
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. Podposloupnost (do 2.11.) 5b.
Spočtěte, kolikrát se daná jehla vyskytne v daném seně jako podposloupnost: například $\mathtt{abcc}$ obsahuje celkem dva výskyty jehly $\mathtt{ac}$.
4. Minimální vrcholové pokrytí (do 9.11.) 5b.
Navrhněte algoritmus pro nalezení minimálního vrcholového pokrytí v bipartitním grafu. Pro graf $G = (V, E)$ řekneme, že $U \subseteq V$ je vrcholové pokrytí, pokud pro každou hranu $e \in E$ kde $e = (u,v)$ je aspoň jeden z vrcholů $u, v \in U$ (můžou být i oba).
5. Domino na šachovnici (do 16.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.
6. Fourierovy obrazy (do 30.11.) 6b.
Spočítejte Fourierovy obrazy následujících vektorů (každý za 2b.):
  • $(1,0,1,0, \ldots ,1,0)$,
  • $(1,-1,1,\ldots ,1,-1)$,
  • $(\omega_n^0, \omega_n^1, \ldots, \omega_n^{n-1} )$ kde $\omega_n = e^{2\pi i / n}$.
7. Hardwired net (do 14.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 síť setřízenou. (Řešení typu použiju třídící síť, která setřídí libovolnou permutaci není správné. Chceme co nejmenší komparátorovou síť pro konkrétní permutaci.) Navrhněte tuto síť, určete odhad počtu hradel a hloubku sítě (hloubka by měla být $O(\log n))$.
8. Všemocný NAND (do 21.12.) 4b.
Ukažte, že můžeme booleovské obvody definovat pomocí jediného typu hradla NAND, kde NAND je NOT z AND (tj. NAND(1, 1) = 0, jinak 1). Každá část je za 2 body:
  • Sestavte síť ze čtyř hradel NAND počítající XOR. XOR je buď nebo, tj. XOR(1, 0) = XOR(0, 1) = 1, jinak 0.
  • Ukažte, že pomocí hradel NAND lze reprezentovat libovolný booleovský obvod.
9. $k$-barevnost (do 4.1.) 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!
10. Loupežníci (do 11.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 26.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 23.11.) 6b.
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 14.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. Hamilton (do 17.2.) 6b.
Dokažte, že následující tři problémy jsou mezi sebou navzájem převoditelné:
  • $HC(G)=1$ právě tehdy když existuje hamiltonovská kružnice v $G$, tedy kružnice, která obsahuje všechny vrcholy grafu $G$.
  • $HP(G)=1$ právě tehdy když existuje hamiltonovská cesta v $G$, tedy cesta, která obsahuje všechny vrcholy grafu $G$.
  • $HP_{uv}(G,u,v)=1$ právě tehdy když existuje hamiltonovská $uv$-cesta, tedy cesta z $u$ do $v$, která obsahuje všechny vrcholy $G$.
B5. Dva středy (do 17.2.) 5b.
Je dána množina bodů v rovině. Rozložte ji na dvě disjunktní středově symetrické množiny, je-li to možné.

Tabulka výsledků

Užitečné odkazy