NTIN060 Cvičení ADS 2

Studijní texty

Stránka přednášejícího zde
Šikovná knížka sepsaná Martinem Marešem zde a užitečné informace v Grafových skriptech pro pokročilé tady.

Podmínky zápočtu

Na každém cvičení bude zadána sada úkolů, ze kterých si jeden vyberte a vyřešte. Vyhotovený úkol musíte odevzdat do začátku dalšího cvičení.
Za úkol je možné získat maximálně 5 bodů. V rámci jedné sady je možné dostat též 5 bodů (i když vyřešíte víc úkolů z dané sady).
Zápočet je možné dostat za 3/5 z celkového množství bodů.
Úkoly odevzdávejte buď přímo na dalším cičení nebo přes mail v textové podobě. Jako předmět použijte "ADS2 - [číslo sady].[číslo úkolu]". Název souboru ve formátu [příjmení] - [číslo sady].[číslo úkolu]. (bonusový úkol má číslo sady B[x]) (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).

Aplikace ADS a další zajímavosti:

V tomto seznamu jsou soutěže, ve kterých využijete poznatků získaných v průběhu ADS (a dalších předmětů)
Tyto programovací soutěže probíhají jen jednou ročně:

Pravidelné programovací soutěže a procvičování:

Zajímavé semináře na mff (probíhají oba semestry):

IPS I a IPS II
Kombinatorický seminář
Filosofické problémy informatiky
KAM úmluva kde se můžete dozvědět o spoustě zajimavých předmětech vyučovaných v daném semestru. Probíhá vždy na začátku semestru (1. týden)

Přůběh cvičení

1.10.2018: Informace o získání zápočtu a průběhu cvičení.
Zopakování notace $O,o,\ldots$ příklady algoritmů, prohledávání grafu, minimální kostry, datové struktury.
8.10.2018: Naivní algoritmus a jeho zlepšení. příklady špatných řetězců, roztace řetězců, společné podřetězce a podposloupnosti, rýmovník.
15.10.2018: Definice a rozbor AC algoritmu, vývpis výskytů přes seznamy, převod AC na automat, výpis nejdelšího/nejkratšího slova končícího na pozici $i$. Počet slov ze slovníku.
22.10.2018: Textové problémy a Rabin-Karp.
29.10.2018: Složitost FF algoritmu pro různé kapacity, kde poběží dlouho, Mnoho zdrojů a spotřebičů, kapacity ve vrcholech, hranová souvislost.
5.11.2018: Aplikace toků na hledání maximálního párování. Pokrývání políček šachovnice dominem, ohrožující se věže, továrny a obchody.
12.11.2018: Amortizace agregací, účetní metoda a potenciál. Aplikace amortizace na zásobník PUSH/POPALL, dynamické pole, přičítání jedničky. Preflow-push algoritmus a jeho důkaz.
19.11.2018: Dokončení důkazu preflow-push algoritmu. Zlepšení pomocí heuristiky a důkaz časové složitosti $O(n^3)$. Komplexní čísla a jejich vlastnosti. DFT - definice a jednoduché aplikace.
Zajímavý odkaz na fourierovy transformaci zde.
26.11.2018: Dokončení spektrálního rozkladu, algoritmus násobení polynomů pomocí DFT.
3.12.2018: Komparátor pro binární hradla a abecedu. Bubble sort, insert, findMax, insertsort. Třídění sléváním, bitonická slévačka.
10.12.2018: Hradlové sítě, definice hradla, redukce abecedy, redukce počtu vstupů a nárůst hloubky. Jak reprezentovat funkci pomocí $\wedge,\vee,\neg$, jak jen pomocí NAND a konstant? Definice IfThenElse operátoru. Binární sčítání, násobení. Sčítání $n$ čísel v $\log n$ hloubce.
17.12.2018: Optimalizační a rozhodovací úlohy. Jak mezi nimi přecházet. Test prvočíselnosti. Třídy P a NP, polynomiální převoditelnost, NP-úplnost. Převod mezi problémy: SAT, 3-SAT, 3,3-SAT, klika, Nezávislá množina. Kódování do SAT.
7.1.2018: Brute force: SAT, NzMn.
Speciální případy: 1 a 2-barvení, 2-SAT, NzMn a VP na stromech.
Aproximace: 2 aproximace VP, MaxSAT a TSP, neaproximovatelnost obecného TSP.
Číselné problémy: Batoh (s cenama), loupežníci.

Úkoly

1. Úkol (do 15.10.2018 10:41)

Hledání v textu (Zadání, popis řešení, pseudokód, složitost, správnost)

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 O(|S|). Zároveň můžete využít jen pole, ve kterém je vstupní řetězec zapsán a O(1) pomocné paměti.
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? (lineární čas)
Najděte nejdelší prefix slova který je zároveň jeho suffixem.

2. Úkol (do 29.10.2018 10:41)

KMP, AC

Sestavte vyhledávací automat Aho-corrasickové pro slova: Milivoj, Milena, Vojen, Milan, Amil, Amis, Alenka, Jan, Jana, Janata, Lenka.
Pro slovník $(S_1,\ldots,S_k)$ určete počet výskytů jednotlivých slov v textu $T$. Časová složitost by měla být $O(T+\sum S_i)$. Neměla by tedy záviset na počtu výskytů (nelze použít Aho-Corasic algoritmus přímočaře).
Pseudokód, textový popis řešení, časová složitost, správnost.

3. Úkol (do 5.11.2018 10:41)

Toky v sítích

Navrhněte algoritmus na hledání vrcholové $k$-souvislosti neorientovaného grafu $G$. Časová složitost hledaného algoritmu je $o(n^2(n+m))$.
Pro síť $S=(V,E,c,z,s)$ mám maximální tok $f_m$. Jak vypočítat v čase $O(|V|+|E|)$ maximální tok $f^\prime_m$ sítě $S^\prime=(V,E,c^\prime,z,s)$ takové, že pro jednu hranu $e_1\in E$ $c^\prime(e_1)=c(e_1)-1$ a pro všechny ostatní $e\in E\setminus\{e_1\}$ $c^\prime(e)=c(e)$ (snížím kapacitu právě jedné hrany o $1$). Všechny kapacity jsou celočíselné.
Pro síť $S$ s maximálním tokem $f_m$ odstraňte z grafu $k$ hran tak, aby se maximální tok v nové síti co nejvíce zmenšil. Pro které kapacity (konstantní, celočíselné, reálné) to lze?

4. Úkol (do 12.11.2018 10:41)

Toky v sítích (použite toky v obou úkolech)

Věže podruhé.Mějme šachovnici, na které některá políčka chybí a chceme na ní postavit co nejvíc věží. Dvě věže se ohrožují pokud jsou ve stejném řádku nebo sloupci a zároveň mezi nimi není žádná díra. Jak umístit co nejvíce věží na naší šachovnici?
Projekty a zdroje. Mějme projekty $P_1,\ldots, P_k$ a zdroje $S_1,\ldots, S_l$ Za realizaci projektu $P_i$ dostaneme odměnu $o_i$, ale potřebujeme k tomu množinu zdrojů $\{S_j|i\in J_i\}$. Každý zdroj nás stojí náklady $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ší.

5. Úkol (do 19.11.2018 10:41)

Amortizace a preflow-push algoritmus

Dynamické pole.Uvažujme pole, na kterém máme definovanou operaci PUSH($x$), která přidá prvek $x$ na první prázdné místo. Pokud chci přidat prvek do pole, které je už plné, vytvoříme pole nové o dvojnásobné velikosti do kterého zkopírujeme všechny prvky z původního pole a nový prvek přidáme na konec. Dokažte pomocí potenciálové metody konstatní amortizovanou složitosti operace PUSH($x$).
Halda v poli.Uvažujme haldu implementovanou v poli, na které máme definovanou operaci INSERT($x$), která vloží prvek do haldy a operaci DELETE($i$) která smaže prvek na indexu $i$ (a zachová strukturu haldy). Pokud při operaci INSERT zjistíme, že je pole plné, vytovřím nové pole dvojnásobné velikosti, zkopíruji do něj haldu z původního pole a nový prvek vkládám do nové reprezentace. Pokud při operace DELETE zjistíme, že je prvků v haldě je jen $1/4$ kapacity pole, vytvořím nové pole poloviční velikosti a haldu zkopíruji do nového pole. Ukažte amortizovanou složitost operací INSERT($x$) a DELETE($i$). Můžete použít libovolnou metodu (agregační, účetní nebo potenciálová). Jak zkopírovat haldu do nového pole aby zůstala haldou?
Lidské toky. Ukažte, jak bude probíhat preflow-push algoritmus na grafu cesty $P=(z=p_4,p_3,p_2,p_1,p_0=s)$ s kapacitami $c(p_{i},p_{i-1})=i$ pro $i=1,2,3,4$. Zdroj a stok nemůžete prohazovat.

6. Úkol (do 26.11.2018 10:41)

Goldberg a DFT

Toky naposledy. Navrhněte implementaci goldberga tak abyste dosáhli časové složitosti $O(n^2\sqrt(m))$. Součástí řešení je algoritmus i s heuristikou, návrh datových struktur a časová analýza celého algoritmu.
Je to primitivní. Dokažte existenci primitivní $n.$ odmocniny z $1$ v $\mathbb{C}$ a zapište ji v exponenciálním tvaru. (Primitivní $n.$ odmocnina z $1$ je $\omega\in\mathbb{C}$ takové, že $\omega^n=1$ a pro všechna $0 < j < n$ $\omega^n\neq 1$.)
Inverze DFT Pro matici zobrazení $\Omega$ definovanou $\Omega_{jk}=\omega^{j,k}$ pro $0\leq j,k < n$, kde $\omega$ je primitivní $n.$ odmocnina z $1$ vypočtěte inverzní matici $\Omega^{-1}$. (Nestačí napsat tvar matice, ale součástí řešení je i postup jak jste k ní došli.)
Trocha počítání. Spočítejte fourierovy obrazy následujících vektorů: $(1,-1,1,-1,\ldots,1,-1),(1,0,1,0,\ldots,1,0),(\omega^j)_{j=0,\ldots,n-1}, (\omega^{2j})_{j=0,\ldots,n-1},(k,k,...k)$. Všechny vektory jsou délky $n$. Součástí řešení je správný výsledek a výpočet jak jste se k tomu výsledku dostali.

7. Úkol (do 3.12.2018 10:41)

DFT. Násobení polynomů

Kosiny.odvoďte DFT vektoru $(\sin (2k\pi /n))_{k=0}^{n-1}$. Řešením je nejen fourierův obraz (výsledný vektor), ale i postup, jakým jste ho dostali.
Kufříky a kódy.Máme $n$ generálů a každý z generálů dostane kufřík s nějakým číslem $k_i$. Chceme zašifrovat zprávu $N$ tak, že méně než $k$ generálů není schopna jednoznačně dešifrovat zprávu $N$ a pokud se sejde alspoň $k$ generálů tak už jednoznačně dešifrují zprávu. (Při dešifrování generálové musí zjistit kolik jich je potřeba pro úspěšné dešifrování.). Jak to generálové provedou? Jak dlouhá může být zpráva kterou chceme zašifrovat a co může obsahovat? (Můžete začít s tím, že $N$ je nějaké vhodné číslo.)
Symetrie asi metrie.Ukažte, jaká je DFT pro reálný vektor. Ukažte, jaká je DFT pro antisymetrický vektor. ($y$ je antisymetrický iff $y_j=\overline{y_{n-j}})$.)

8. Úkol (do 10.12.2018 10:41)

Třídící sítě

Bitonický separát. Čistě bitonická posloupnost je posloupnost $x_1,\ldots,x_n$ pro kterou platí, že existuje $0<k\leq n$ takové, že pro všechna $1\leq i< j \leq k$ je $x_i< x_j$ a pro všechna $k<i<j\leq n$ je $x_i> x_j$. Bitonická posloupnost je posloupnost $y_1,\ldots,y_n$ která vznikne rotací čistě bitonické posloupnosti $x_1,\ldots,x_n$.
Bitonický separátor je hradlová síť se vstupy $x_1,\ldots,x_n$ a výstupy $y_1,\ldots,y_n$, která na vstupu dostane bitonickou posloupnost $x_1,\ldots,x_n$ a na výstupu dá dvě bitonické posloupnosti $y_1,\ldots,y_{n/2}$ a $y_{n/2+1},\ldots,y_n$ takové, že pro libovolná $1\leq i\leq n/2 <j\leq n$ platí $y_i< y_j$. (levá část výstupu je menší než pravá část výstupu). Síť má $k/2$ komparátorů, kde komparátor $k_i$ spojuje $x_i,x_{i+n/2}$ (konstantní hloubka). Dokažte, že tato komparátorová síť je skutečně bitonický separátor (a separuje nejen čistě bitonické posloupnosti).
Slévání podle Batchera. 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ě.
Hardwired net.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))$.
Boosted hardwired net.K řešení předchozího příkladu můžu použít i obrácený komparátor, tedy komparátor, který má na výstupu uspořádanou dvojici $(max(x,y),min(x,y))$. Navrhněte síť s hloubkou $O(1)$ (za síť hloubky $O(\log n)$ je půl bodů.)

9. Úkol (do 17.12.2018 10:41)

Hradlové sítě.

Nekonstantní norkování. Dokažte, že libovolnou booleovskou hradlovou síť, jste schopni převést na booleovskou hradlovou síť, která využívá pouze hradel NOR (negace OR) bez konstant. Jaký bude nárůst počtu hradel a hloubky sítě? (Pokud chcete použít poznatku z cvičení, že nám stačí NAND s konstantama, musíte to dokázat též.)
?:. Definujeme booleovskou funkci tří proměnných $f(p,x_1,x_2)=x_p$. Ukažte jak vypadá hradlová síť $F$ realizující funkci $f$. Dokažte, že libovolnou booleovskou hradlovou síť, lze převést na síť, která využívá pouze podsítě $F$ a konstant $0$ a $1$.
Trocha principu. Navrhněte booleovskou hradlovou síť, která realizuje odčítání dvou čísel v binárním zápisu. Sčítání binárních čísel můžete použít z přednášky. Pokud budete potřebovat násobení, musíte ještě dokázat redukci u sčítání $X+Y+Z=A+B$. Odhadněte počet hradel a houbku sítě.

10. Úkol (do 7.1.2019 10:41)

Máme blackbox NzMn($G$,$k$), který vrací 1 právě tehdy, když je v grafu $G$ nezávislá množina velikosti alespoň $k$. Navrhněte algoritmus, který bude využívat balckboxu NzMn($G$,$k$) k nalezení a vypsání maximální nezávislé množiny v grafu $G$ a použije k tomu jen polynomiálně mnoho volání blackboxu NzMn($G$,$k$). (Pokud vezememe složitost T=NzMN($G$,$k$), pak by složitost algoritmu měla být polynomiální vzhledem k $T$ a velikosti grafu $G$).
Uvažme následující tři problémy:
1. $HC(G)=1$ právě tehdy když existuje hamiltonovská kružnice v $G$, tedy kružnice, která obsahuje všechny vrcholy grafu $G$.
2. $HP(G)=1$ právě tehdy když existuje hamiltonovská cesta v $G$, tedy cesta, která obsahuje všechny vrcholy grafu $G$.
3. $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$.($u$ a $v$ jsou krajními vrcholy cesty.)
Dokažte buď všechny 3 problémy jsou NP-úplné nebo všechny tři problémy jsou mezi sebou převoditelné.
Vrcholové pokrytí grafu $G$ je množina vrcholů taková, že každá hrana je incidentní alespoň jednomu vrcholu z pokrytí. Definujte rozhodující problém, který lze využít pro řešení optimalizační úlohy nalezení minimálního vrcholového pokrytí (vzhledem k počtu vrcholů) a dokažte jeho NP-úplnost.

Bonusové úkoly

1. Bonus
: Vlakem na výlet
V sobotu ráno chceme jet na výlet do přírody. Ve vlaku nechceme strávit moc času a taky nemáme rádi přestupy. V naší zemi naštěstí máme rychlíky, které jedou jen z města A do města B a nikde cestou nestaví. Doba jízdy mezi konkrétními dvěma městy se nemění a vlaky mají nulové zpoždění.
Známe tedy pro každé město časy odjezdů vlaků do jiných měst a dobu cesty mezi městy $A$ a $B$ pro každá města spojená vlakem. Vyjíždíme v čas $T$ a chceme se dostat z DOMU do PŘÍRODY za co nejmenší čas a s co nejmenším počtem přestupů (primární je délka jízdy). Navrhněte algrotimus, napište pseudokód, časovou analýzu a ukažte že váš algoritmus najde optimální řešení. (4 body)
Co kdybychom povolili vlakům zastavovat, v mezistanicích? (1 bod)