Cvičení z Algoritmů a datových struktur 2

Studijní texty

1. Teta wiki.
2. Slidy.
3. Článek rozebírající nejmenší příklady.

Podmínky zápočtu

• Na každém cvičení bude zadán jeden úkol s odevzdáním do začátku dalšího cvičení.
• Všechny úkoly budou bodovány stejně (5b) a na zápočet je potřeba dosáhnout 3/5 z celkového počtu bodů.
• Nepravidelně budu zadávat zajímavější úkoly. Po dvou týdnech od zadání poskytnu nějakou nápovědu. Bez nápovědy budou tyto úkoly za 5b a s nápovědou za polovic.
• Úkoly odevzdávejte buď přímo na dalším cičení nebo přes mail miloschromy(at)gmail.com jako nakskenované (vyfocené) obrázky/pdf nebo v pdf. Jako předmět použijte ADS2. (ideálně vysázené v $\LaTeX u$. Pokud začínáte s $\LaTeX em$ pak zkuste wysiwyg editor LyX. Další možností je word(libre, microsoft, open).

Úkoly

1. Úkol (do 18.10.2017 17:20h)
   Mějme řetězec $t$. Navrhněte algoritmus, který zjistí jestli lze $t$ zapsat jako $s^k$, kde $s$ je řetězec a $k> 1$ je přirozené číslo, tedy že řetězec $t$ je periodický.
   Výsledek zapište ve formě pseudokódu a odhadněte časovou složitost i pomocnou paměť programu. Zároveň by mělo být zřejmé, že váš algoritmus funguje (pokud to není zřejmé, tak to je třeba dokázat).
2. Úkol (do 25.10.2017 10:11h)
   Vyberte si jednu z následujících úloh (můžete odevzdat obě, ale body dostanete jen za tu, která bude lepší, tedy max):
   1. V textu $T=3141592653589793238462$ hledáme vzor $S=26$. Kolik neúspěšných testů provede Rabin-Karp algoritmus pracující modulo $q=11$? Součástí řešení je i výpis kolizních řetězců a zdroják(pokud tento úkol řešíte implementací) .
   2. Cenzura. Jako zkušení cenzoři máme slovník zakázaných slov $s_1,\ldots, s_k$. Na vstupu dostaneme text $T$ a naším úkolem vymazat všechny výskyty slov $s_1,\ldots,s_k$. Protože chceme pracovat systematicky, najdeme nejlevější zakázané slovo v textu $T$ a to vystřihneme, čímž dostaneme nový text, ve kterém mohlo tímto zásahem vzniknout další zakázané slovo. Tento proces opakujeme dokud v textu nebude žádné zakázané slovo.
      Navrhněte algoritmus na tento problém. Ukažte časovou složitost (měla by být lineární) a správnost vašeho algoritmu.
3. Úkol (do 1.11.2017 10:11h)
   Pro graf $G=(V,E)$ a vrcholy $s,t\in V$ nalezněte maximální množinu hranově disjunktních cest mezi $s$ a $t$.
   Algoritmus na hledání maximálního toku můžete použít jako BlackBox. Výstupem by měla být maximální množina hranově disjunktních cest. Součástí řešení je časová analýza (samozřejmě i to proč vaše řešení funguje).
4. Úkol (do 15.11.2017 10:11h)
   Mějme šachovnici $m\times n$ s množinou zakázaných políček $Z=\{z_1,\ldots,z_k\}$. Jak na šachovnici (na nezakázaná políčka) rozmístit co největší množství věží, které se navzájem neohrožují (věže se navzájem ohrožují pokud na sebe vidí v horizontálním nebo vertikálním směru)?
   1. Zakázaná políčka jsou díry a věže se přes ně ohrožují.
   2. Zakázaná políčka jsou zdi a věže se přes ně neohrožují.
5. Úkol (do 22.11.2017 10:41h)
   Komparátové sítě. K dispozici máte komparátor, tedy obvod který na vstupu dostane dvojici $x,y\in \Sigma$ a výstup 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))$.
6. Úkol (do 29.11.2017 10:41h)
   Hradlové sítě Navrhněte hradlovou síť s $m$ vstupy, která spočítá dolní celou část dvojkového logaritmu vstupního čísla. Pro číslo $N < 2^m$ v binárním zápisua spočítá hradlová síť $\log(N)$. Výstup může být v binárním zápisu (bude mít $\log(m)$ výstupních hradel) nebo v "unárním" zápisu ($m$ výstupních hradel a výstupní hradlo $i=1 \Leftrightarrow \log(N)=i$) nebo nějaká vlastní vhodná reprezentace. (hloubka $O(\log m)$)
7. Úkol (do 6.12.2017 10:41h)
   Diskrétní Fourierova Transformace (DFT) je zobrazení $\mathcal{F}:\mathbb{C}^n\rightarrow\mathbb{C}^n$, které vektoru $x$ (vektor odpovídající koeficientům polynomu) přiřadí vektor $y$ (vyhodnocení polynomu v bodech $\omega^j$ daný předpisem $y_j = \sum_{k=0}^{n-1} x_k \omega ^{jk}$, kde $\omega$ je pevně zvolená primitivní odmocina z 1. Vektor $y$ nazveme Fourierův obraz.
   Z následujících příkladů vyřešte 2. Součástí řešení není jen výsledek, ale i to, jak jste se k řešení dostali:
   1. Máme polynom $K=(k,k,k,\ldots,k)$. Jaký bude výsledek pokud na tento polynom použijeme DFT? ($\mathcal{F}(K)$)
   2. Jak dopadne DFT polynomu s reálnými koeficienty? (Bude reálný, $e_j$, nulový, konstantní, symetrický ($x_i=x_{n-i (mod n)}$), antisymetrický ($ x_i=\overline{x}_{n−i(mod n)}), ...?)$
   3. DFT je lineární zobrazení s maticí zobrazení $\Omega$. Ukažte jak vypadá inverze tohoto zobrazení, tedy matice $\Omega^{-1}$.
   4. Najděte polynom(vektor), jehož fourierův obraz má na místě $j$ 1 ($y_j=1$) a všude jinde 0($\forall k\neq j: y_k=0$). Hledáme tedy $P$, takové, že $\mathcal{F}(P)=e_j$, kde $e_j=(0,0,\ldots,0,1,0,\ldots,0,0)$.
8. Úkol (do konce semestru)
   Definice:Nechť $A,B$ jsou rozhodovací problémy. $A\rightarrow B$ ($A$ lze převést na $B$) právě tehdy, když existuje funkce $f:\{0,1\}^*\rightarrow\{0,1\}^*$ taková, že pro všechna $x\in\{0,1\}^*$ platí $A(x)\Leftrightarrow B(f(x))$ a $f(x)$ lze spočítat v čase $\mathcal{O}(|x|^c)$ pro vhodnou konstantu $c$.
   Dokažte následující lemma: Pokud $A\rightarrow B$ a $B$ lze řešit v polynomiálním čase, pak i $A$ lze řešit v polynomiálním čase.
9. Úkol (do konce semestru)
   Nechť $G$ je graf a $u,v\in V(G)$ jeho 2 vrcholy. Hamiltonovská $uv$-cesta je cesta, která prochází každý vrchol grafu $V(G)$ právě jednou a konce této cesty jsou vrcholy $u$ a $v$. Ukažte, že rozhodovací problém zda existuje v grafu $G$ Hamiltonovská $uv$-cesta HAM$(G,u,v)$ je NP-úplný. (Můžete předpokládat že problémy hamiltonovská kružnice je NP-úplný, pokud budete předpokládat že hamiltonovská cesta (bez definovaných krajních vrcholů) je též NP-úplná, je úkol za 4b. Další NP-úplné problémy, které můžete využít jsou libovlné varianty SATU, Problém batohu s cenami, loupežníci, Klika a nezávislá množina.)
10. Úkol (do konce semestru)
    Dynamické programování. Máme zadanou množinu předmětů $P=\{p_1,\ldots,p_n\}$ a každý předmět má danou svojí váhu $m_i$ a cenu $c_i$, $p_i=(m_i,c_i)$. Chceme se rozdělit se svým kamarádem. Kamarád má jediné kritérium. Chce, abychom si rozdělili předměty tak, že cena jeho předmětů bude stejná jako cena mých předmětů. Vaším cílem je rozdělit předměty do dvou skupin $M$(oje) a $K$(amarádovo) tak, abyste měli svůj balíček co nejlehčí a ceny předmětů na kopičkách se rovnali. Za 1 bonusový bod ukažte, proč je daný algoritmus pseudopolynomiální (ukažte tedy, že je rozhodovací verze tohoto problému NP-úplná (hledáme rozdělení takové, že má hromádka má váhu nejvýš nějaké $k$)).

Bonusové úkoly

1. 5b
   Pro graf $G=(V,E)$ a vrcholy $s,t\in V(G)$ definujeme množinu $P$ jako množinu všech cest z $s$ do $t$. (dvě cesty z $P$ můžou sdílet jak vrcholy tak hrany, ale liší se vždy alespoň v jedné hraně nebo vrcholu)
   1. Navrhněte algoritmus, který spočítá počet všech cest, tedy velikost množiny $|P|$.
   2. Navrhněte algoritmus, který nalezne množinu $P$.
   U obou problémů určete časovou složitost a určete do jestli jsou problémy v P,NP nebo ani v jedné (NP-úplné, NP-těžké, ...).
2. 5b
   Toky v sítích Mějme projekty P_1...P_k. Za realizaci projektu P_i dostaneme odměnu o_i, ale potřebujeme k tomu množinu zdrojů S_i. Kazdy zdroj nas stoji naklady n_i, ale jakmile ho jednou koupíme, můžeme ho použít ve více projektech. Navrhněte algoritmus, který zjistí, které projekty realizovat a jaké zdroje si koupit, aby byl celkový zisk co největší.
3. 5b
   Komparátorové sítě. K dispozici máte dva druhy hradlových gadgetů. Komparátor, tedy obvod který na vstupu dostane dvojici $(x,y)\in \Sigma$ a výstup je uspořádaná dvojice $(min(x,y),max(x,y))$ a "obrácený" komparátor, tedy obvod, který na vstupu dostane dvojici $(x,y)\in \Sigma$ a výstup je uspořádaná dvojice $(max(x,y),min(x,y))$. Pokud v komparátorové síti uvážíme možnost používat i "obrácené" komparátory dostaneme rozšířenou komparátorovou síť. Navrhněte algoritmus, který na vstupu dostane permutaci $\sigma$ na množině $x_1,\ldots, x_n$ a jehož výstup bude rozšířená komparátorová síť konstantní hloubky O(1). Proč potřebujeme "obrácené" komparátory a nestačí nám klasická komparátorová síť k dosažení této hloubky?
4. 5b
   Vyřešte zbylé dva body ze 7. úkolu.
5. 5b
   Konvexní obal. Popište algoritmus na hledání konvexního obalu, pokud předem víte, že konvexní obal je složen z $k$ bodů. (Pro $k< \log n$ bude takový algoritmus vhodný, $n$ počet bodů uvnitř konvexního obalu). Navržený algoritmus by měl běžet v čase $O(nk)$.
6. 5b
   Aproximační algoritmy. Máme podzemní základnu, která se skládá z místností a chodeb mezi místnostmi. Chceme detekovat jakékoliv narušení perimetru (pohyb v chodbách). Toho můžeme docílit jediným způsobem. V každé místnosti můžeme umístit detektor pohybu, který je schopný ohlásit pohyb v libovolné chodbě, která ústí do této místnosti (a jen v takových chodbách). Protože takováto zařízení nejsou úplně levná, chceme jich umístit maximálně 2x tolik, než je minimální počet, který by byl potřeba. Jak zvolíme místnosti do kterých cheme umístit detektory, pokud to chceme zvládnout v polynomiálním čase? Dokažte i to, že umístíte maximálně 2x tolik detektorů než je nezbytné.

Další možnosti jak získat body