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

Miloš Chromý
Doba cvičení: út 12:20--13:50
Místo cvičení: S10

Studijní texty

Stránky přednášky Luďka Kučery jsou zde.
Šikovná skripta Martina Mareše zde a užitečné informace v Grafových skriptech pro pokročilé tady.
Moc pěkně vysvětlená fourierova transformace je zde.

Podmínky zápočtu

Úkoly

  1. Úkol (do 11.10.2016 17:20h)
    Napište algoritmus, který na vstupu dostane řetězec $S$ a číslo $k$. Na výstupu algoritmu chceme řetězec rotovaný o $k$ pozic(řetězec na pozici $k$ rozřízneme a přilepíme začátek za konec). Algoritmus by měl běžet v čase $\mathcal{O}(|S|)$. Zároveň můžete využít jen pole, ve kterém je vstupní řetězec zapsán a $\mathcal{O}(1)$ pomocné paměti.
    V plném řešení by měl být pseudokód, časová a paměťová složitost vašeho algoritmu. Zároveň by mělo být zřejmé že je algoritmus korektní a úplný.
  2. Úkol (do 18.10.2016 17:20h)
    Sestavte automat Aho-corrasickové (nakreslete strom včetně všech zpětných i zkratkových hran) pro slova: Milivoj, Milena, Vojen, Milan, Amil, Amis, Alenka, Jan, Jana, Janata, Lenka.
  3. Úkol (do 25.10.2016 17:20h)
    Mějme ohodnocený graf $G=(V,E,w)$ kde $w:E\rightarrow\{1,\ldots,K\}$ je váhová funkce, která každé hraně přiřadí přirozené číslo $1,\ldots,K$. Jak rychle poběží Jarníkův algoritmus na hledání minimální kostry na takovémto grafu? (Navrhněte vhodnou implementaci (pseudokód) a vhodné datové struktury a ukažte časovou složitost.)
  4. Úkol (do 1.11.2016 17.20h)
    (a) Navrhněte algoritmus, který rozmístí maximální počet věží na šachovnici $n\times m$ s dírama (na díru se nesmí věž položit, ale může přes ní útočit)
    (b) Upravte algoritmus pro případ, že věž neumí přes díru útočit. (1b)
  5. Úkol (do 15.11.2016 17.20h) (2xbody)
    Mějme síť $S=(V,E,z,s,c)$ a $k\in \mathbb{N}$ a maximální tok sítě $S$ je $f_S$. Vytvořte novou síť $S'=(V,E',z,s,c)$, kde $E'\subset E$ a $|E\setminus E'| \leq k$, s maximálním tokem $f'$ takovou, že pro libovolnou síť $S''=(V,E'',z,s,c)$, kde $E''\subset E$ a $|E\setminus E''| \leq k$, s maximálním tokem $f''$ platí $f'\leq f''$. (Odstraňte ze sítě $S$ maximálně $k$ hran, tak aby se maximální tok co nejvíce zmenšil.)
    (a) $\forall e\in E: c(e)=1$(všechny hrany mají jednotkové kapacity).
    (b) kapacity nejsou omezeny. Dokažte že přístup z (a) bude fungovat i v tomto případě nebo nalezněte protipříklad. Zkuste si rozmyslet, zda by šel přístup z (a) nějak rozšířit.
  6. Úkol (do 29.11.2016 17.20h)
    1. Ukažte, že 1 má v komplexních číslech $n$ různých odmocnin (Hint: kdy se $e^{i\varphi}$ rovná 1?)
    2. Mějme matici $\Omega\in\mathbb{C}^{n\times n}$ takovou, že $\Omega_{jk}=\omega^{jk}$, kde $\omega$ je primitivní $n$ odmocnina z 1, tedy $\omega^n=1$ a pro $1\leq j\leq n-1 :\omega^j\neq 1 $
      Ukažte, jak z komplexně združené matice $\overline{\Omega}$, kde $\overline{\Omega_{jk}}=\overline{\omega^{jk}}$ dostat inverzní matici $\overline{\Omega}_I$ k $\Omega$ ($\Omega\overline{\Omega}_I=I$) (Hint: jak vypadá $\Omega_{jk}$ pro $j=k$ a $j\neq k$?)
    3. Co udělá DFT s vektorem $(k,k,\ldots,k)$ pro $k\in\mathbb{N}$? (Hint: zkuste to nejdřív pro $(1,1,\ldots,1)$)
    4. Jak vypadá DFT reálného vektoru?
    5. Jak vypadá DFT antisymetrického vektoru? (Antisymetrický vektor je vektor, pro který platí $x_i=\overline{x}_{n-i(mod n)}$
    6. Co dostaneme z DFT navzorkováním funkce $s(x)=\sin 2k\pi x$, tedy s vektorem $(\sin 2k\pi*\frac{0}{n},\sin 2k\pi*\frac{1}{n},\ldots, \sin 2k\pi*\frac{n-1}{n})$.
  7. Úkol (do 6.12.2016 17.20h)
    Dokažte, že libovolnou booleovskou fromuli hloubky $h$ (maximálně $h$ do sebe vnořených závorek) a délky $l$ lze reprezentovat booleovským obvodem (hradlová síť, jejíž hradla počítají booleovské funkce) s $h$ vrstvami a velikosti (počet hradel) $\mathcal{O}(l).$
    Booleovskou formuli můžeme definovat induktivně
    1. libovolná booleovská proměnná je booleovská formule
    2. pro booleovské formule $\phi$ a $\psi$ $\phi\wedge\psi,\phi\vee\psi$ a $\neg\phi$ jsou booleovské formule.
    Pokud chcete použít jinou definici booleovských formulí tak musíte ukázat ekvivalenci s touto definicí (včetně nárůstu/poklesu velikosti formule).
  8. Úkol (do 13.12.2016 17.20h)
    Navrhněte hradlovou síť, která pro číslo $x$ v binárním zápisu vypočte dolní celou část z jeho dvojkového logaritmu ($\lfloor\log_2(x)\rfloor$). Než začnete navrhovat síť, rozmyslete si co je vstupem a výstupem a jak vlastně výstup vypadá.
  9. Úkol (do 20.12.2016 17.20h)
    Popište algoritmus na hledání konvexního obalu, pokud předem víte, že konvexní obal je složen s $k$ bodů. (Vhodné pokud platí, že $k<<n$, $n$ počet bodů uvnitř konvexního obalu). Algoritmus by měl pracovat v čase $\mathcal{O}(nk)$.
  10. Úkol (do posledního cvičení)
    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.

Bonusové úkoly

  1. Úkol (2.5b)
    Pěstovaný strom říkejme zakořeněnému stromu, jehož hrany k synům mají v každém vrcholu určené uspořádání zleva doprava. Strom se osekáva 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 (zbyde tedy souvislý úsek hran z kořene podstromu dolů a podstromy, které pod nimi visí). Jak zjistit o dvou pěstovaných stromech, zda lze jeden získat osekáním druhého?
    Problém se dá vyřešit pomocí KMP algoritmu.
  2. Úkol (2.5b)
    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. Úkol (5b)
    6. Sada úkolů výše. 5b je za všechny, takže $\frac{5}{6}$b za jeden podpříklad.
  4. Úkol (5b do 20.12.2016)
    Uvažte následujíci algoritmus:
    BMERGE$((x_0,\ldots,x_{n-1}),(y_0,\ldots,y_{n-1}))$
    Vstup: Setřízené posloupnosti $(x_0,\ldots,x_{n-1})$ a $(y_0,\ldots,y_{n-1})$, $n=2^k$ pro nějaké $k\in\mathbb{N}$.
    1. $n\leq 2$ vyřešíme triviálně.
    2. $(a_0,\ldots,a_{n-1})\leftarrow BMERGE((x_0,x_2,\ldots,x_{n-2}),(y_0,y_2,\ldots,y_{n-2}))$
    3. $(b_0,\ldots,b_{n-1})\leftarrow BMERGE((x_1,x_3,\ldots,x_{n-1}),(y_1,y_3,\ldots,y_{n-1}))$
    Výstup: $(a_0,\min(a_1,b_0),\max(a_1,b_0),\min(a_2,b_1),\max(a_2,b_1),\ldots,b_{n-1})$.
    (a) Dokažte, že algoritmus vrátí setřízenou posloupnost a ukažte, jak se vyřeší triviální příklad $n\leq 2$.
    (b) Zapište algoritmus ve formě třídící sítě.
  5. Úkol (5b)
    Navrhněte algoritmus na řešení zadání 9.Úkolu, který pracuje v čase $\mathcal{O}(n\log k)$.