Miloš Chromý

 - KTIML, MFF
-
- - Najdete mě v místnosti pro doktorandy v 5. patře na Malé straně
- - Konzultace po domluvě

Cvičení ADS2 (NTIN061)

Doba cvičení: Út 17:20--18:50
Místo cvičení: S7
Toto cvičení je k přednášce J.Hubičky (út)

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

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):

Přůběh cvičení

1.10.2019
Úvodní
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.2019
Textové problémy
Naivní algoritmus a jeho zlepšení. příklady špatných řetězců, roztace řetězců, společné podřetězce. KMP algoritmus a automat.
15.10.2019
Aho-Corrasic
Definice a rozbor AC algoritmu, vývpis výskytů přes seznamy, výpis nejdelšího/nejkratšího slova končícího na pozici $i$. Výpis všech slov včetně začátku a konce.
22.10.2019
Rabin-Karp, Ford-Fulkerson
Rabin-Karp. Definice, hashovací funkce. Pro $k$ jehel stejné délky určete počet výskytů. FF algoritmus. Zlepšující cesty, proč nefungují. (Ne)nasycené cesty. Složitost na hranách s kapacitou 1, nebo $\mathbb{N,Q,R}$. Maximální toky v sítích s kapacitou ve vrcholech.
29.10.2019
Toky v sítích, bipartitní párování
Vrcholová $k$-souvislost. Maximální párování v bipartiních grafech. Čemu odpovídá zlepšující cesta v bipartitním grafu.
Jak rozestavět co nejvíc věží na šachovnici $n\times n$ tak aby se žádné dvě neohrožovaly, šachovnice obsahuje voud, přes kterou se věže ohrožují a zdi přes které se neohrožují a na vodě ani zdi nemůžeme věž postavit.
Továrna $T_i$ vyrobí $t_i$ produktů a prodejce $P_j$ má poptávku $p_j$ produktů, zásobování prodejců z továren je dáno bipartitním grafem. Jsou všechny poptávky prodejců uspokojeny?
Algortimus, který najde minimální řez. V síti, ve které mám nalezený maximální tok, zvýším kapacitu jedné hrany o 1, jak naleznu maximální tok v nové síti co nejrychleji?
5.11.2019
Goldberg, Dinitz a další
Goldbergův algoritmus a jeho důkaz. Může být výška zdroje $h(z)=n-1$? Jednotkový goldberg a jeho složitost.
Od FF přes Edmonson-Karp k Dinitzově algoritmu. Časová složitost. Jednotokové nebo konstantní kapacity.
19.11.2018
Komplexní čísla, DFT, FFT.
Komplexní čísla a jejich vlastnosti. DFT - definice a jednoduché aplikace. DFT sinu a kosinu a spektrální rozklad.
FFT a násobení polynomů.
Zajímavý odkaz na fourierovy transformaci zde.
26.11.2019
Hradlové sítě
Definice, počet různých booleovských funkcí na $n$ proměnných, redukce $k$ árního OR na binární OR. Maximální velikost hradlové sítě pro libovolnou funkci je $O(2^n)$ a hloubka $O(n)$. Minimální velikost je $\Omega(n^k)$. Libovolnou funkci lze reprezentovat pomocí sítě s AND, OR a NOT. Dokonce nám stačí NAND. Čistě XOR ne. Libovolnou síť s $k$ árníma hradlama lze převést na obvod využívající jen binární AND, OR, NOT a se zpomalením $\log(k)\times$ a zvětšením $k\times$.
3.12.2018
Třídící sítě
Komparátorové sítě. Komparátor pro binární hradla a abecedu. Komparátorové sítě pro bubble sort, insert do setřízné posloupnosti, findMax, insertsort. Třídění sléváním, bitonická slévačka, Batcher's merge. Setřídění fixní posloupnosti s obousměrným komparátorem.
Hradlová síť pro násobení v $\log(n)$ hloubce. Mod(k).
10.12.2018
NP
Kódování vstupu. Optimalizační a rozhodovací úlohy. Jak mezi nimi přecházet. Třídy P a NP, polynomiální převoditelnost, NP-úplnost, NP-těžkost. Převod mezi problémy: SAT a 3-SAT, klika a Nezávislá množina, SAT a 3-barvení, HK a TSP.
17.12.2018
Co s NP
Ještě trochu převodů: Batoh, batoh s cenama, loupežníci, soustava celočíselných rovnic.
Brute force.
Speciální případy: 2-barvení, 2-SAT, NzMn na stromech.
Aproximace: 2 aproximace VP,.
Číselné problémy: Batoh (s cenama), loupežníci.

Úkoly

1. Úkol (do 15.10.2019 17:21)
Hledání v textu (Zadání, popis řešení, pseudokód, složitost, správnost)
  1. 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.
  2. Najděte nejdelší prefix slova který je zároveň jeho suffixem.
  3. 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)
2. Úkol (do 29.10.2019 10:41)
AC
  1. Sestavte vyhledávací automat Aho-corrasickové pro slova: Milivoj, Milena, Vojen, Milan, Amil, Amis, Alenka, Jan, Jana, Janata, Lenka.
  2. Pro slovník $(S_1,\ldots,S_k)$ určete počet výskytů jednotlivých slov v textu $T$. Časová složitost $O(T+\sum S_i)$ a není tedy závislá 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 29.10.2019 17:21)
Rabin-Karp. Toky v sítích
  1. Použitím Rabin-Karpa najděte všechny výskyty matice $m\times m$ v matici $n\times n$.
  2. Máte BlackBox algoritmus, který pro dva vrcholy $u,v$ zjistí, zda mezi nimi vede $k$ hranově disjunktních cest. (FF algoritmus s časovou složitostí $O(k(m+n))$. Pomocí tohoto algoritmu zjistěte zda je neorientovaný graf $G$ hranově $k$-souvislý. (Graf je hranově $k$-souvislý pokud mezi každými dvěma vrcholy vede $k$ hranově disjunktních cest.) Váš algoritmus nemá dostatek času na to, aby zavolal $\Theta(n^2)$ krát náš BlackBox algoritmus. Časová složitost hledaného algoritmu je tedy $o(n^2k(n+m))$.
  3. Navrhněte algortimus, který pro graf $G$ a dva vrcholy $u$ a $v$ nalezne a vrátí $k$ hranově disjunktních cest. FF algoritmus na hledání maximálního toku v síti popisovat nemusíte. Určete časovou složitost vašeho algoritmu.
4. Úkol (do 5.11.2019 17:21)
Toky v sítích (použijte toky)
  1. Domino. Máme šachovnici $n\times n$ s dírama. Navrhněte algoritmus, který zjistí zda lze takovouto šachovnici pokrýt kouskama domina. Kousek domina zakryje vždy dve sousední políčka, žádné dva kousky domina se nesmí překrývat a domino nesmí zakrývat díru ani přečuhovat z okrajů.
  2. Změna sítě. Mějme síť $S=(V,E,z,s,c)$ s celočíselnými kapacitami a její maximální tok $F$. Novou síť $S'=(V,E',z,s,c')$ získáme tak, že pro jednu libovolnou hranu $e\in E$ snížíme její kapacitu o 1, tedy $c'(e)=c(e)-1$. Navrhněte algoritmus, který upraví tok $F$ v $S$ na maximální tok $F'$ v síti $S'$ v čase $O(|V|+|E|)$.
  3. Minimini řezy. Pro síť $S=(V,E,z,s,c)$ nalezněte řez minimální kapacity, který obsahuje minimální počet hran.
5. Úkol (do 19.11.2019 17:21)
Goldberg, Dinitz a ti další
  1. Malý goldberg.Na začátku Goldbergova algoritmu nastavíme výšku zdroje na $h(z)=n-i$. Dokažte pro jaká $i\in\{2,3,4\}$ Takto upravený algoritmus vrátí po skončení maximální tok. (Pokud nevrátí, tak je nejlepší uvést protipříklad.)
  2. Omezený Dinitz.Mějme síť $S=(V,E,z,s,c)$, kde pro všechny hrany platí $c(e)\leq K$, pro pevně zvolenou konstantu. Jakou časovou složitost bude mít Ditintzův algoritmus na takovéto síti. (Jak rychle jste schopni udělat čištění sítě? V řešení můžete brát v potaz základní verzi, která běží v $O(mn^2)$.)
  3. Meč na Karpa. Edmonson-Karpův algoritmus funguje téměř stejně jako FF algoritmus, ale při výběru zlepšující cesty vybírá tu nejkratší (počet hran). Tento algoritmus má časovou složitost $O(m^2n)$ a narozdíl od FF najde řešení i pro síť s reálnými kapacitami. Postavte síť na které ukážete, že i s tímto zlepšením potřebujeme hledat zlepšující cestu i "proti směru" hran?
6. Úkol (do 26.11.2019 17:21)
DFT, FFT
  1. Troška 4 počítání. Spočítejte fourierovy obrazy následujících vektorů: $(1,0,1,0,\ldots,1,0),(k,k,\ldots,k),(\omega^{kj})_{j=0,\ldots,n-1},(\sin(2jk\pi/n))_{j=0,\ldots,n-1}$. Všechny vektory jsou délky $n$, $k$ je přirozené číslo. Součástí řešení je správný výsledek a výpočet jak jste se k tomu výsledku dostali.
  2. 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? Popište i jak budou šifrovat a dešifrovat. 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.)
  3. Symetrie asi metrie.Dokažte, že DFT reálného vektoru je antisymetrický vektor a DFT antisymetrického vektoru je reálný vektor. ($y$ je antisymetrický iff $y_j=\overline{y_{n-j}})$.)
7. Úkol (do 3.12.2019 17.21)< /dt>
Hradlové sítě
  1. Norníci. Dokažte, že libovolnou booleovskou funkci lze reprezentovat jen pomocí binárních hradel NOR.
  2. Odčítání hradlu. Navrhněte hradlovou síť která realizuje odčítání dvou $n$ bitových čísel $x$ a $y$ hloubky $O(n)$ a s $O(n)$ hradly. Hloubku sítě i počet hradel odhadněte přesně (i na konstanty). Síť může používat jen binární booleovská hradla AND, OR, unární hradlo NOT a konstanty 0 a 1. (Pro zlehčení můžete používat binární booleovské funkce, které umíte pojmenovat.)
8. Úkol (do 10.12.201 17:21)
Třídící sítě
  1. Mějme následující 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ě.
  2. Binární komp. Navrhněte síť s binárními hradli a binární abecedou realizující komparátor dvou čísel. Tedy hradlou síť, která má jen binární hradla a na vstupu dostane dvě čísla $x,y$ v binárním zápisu délky $n$ a na levém výstupu bude binárně zapsané $min(x,y)$ a na pravém výstupu $max(x,y)$.
  3. Celý Log. Navrhněte síť která na vstupu dostane binární zápis čísla $n$ a na výstupu bude $\lfloor \log n\rfloor$
9. Úkol (do 17.12.2019 17:21)
NP
  1. 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 všechny tři problémy jsou mezi sebou převoditelné.
  2. Vrcholové pokrytí grafu $G$ je množina vrcholů taková, že každá hrana je incidentní alespoň jednomu vrcholu z pokrytí. Rozhodovací verze: hledáme množinu vrcholů velikosti maximálně $k$ která je vrcholovým pokrytím grafu G. Dokažte jeho NP-úplnost. (Nezávsilá množina i Klika jsou NP-úplné.)
10. Úkol (do 7.1.2020 17:21)
Co s NP
  1. Vrcholky stromů.Dokažte, že problém vrcholového pokrytí na stromech je v P.
  2. Hladoví loupežníci. Pokusíme se řešit problém dvou loupežníků hladovým algoritmem. Probíráme předměty od nejdražšího k nejlevnějšímu a každý dáme tomu loupežníkovi, který má zrovna méně. Je nalezené řešení optimální?
  3. Problém tří loupežníků. Je dána množina předmětů s cenami, chceme ji rozdělit na 3 části o stejné ceně. Navrhněte pseudopolynomiální algoritmus.