Miloš Chromý

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

Cvičení ADS1 (NTIN060)

Doba cvičení: St 12:20--14:00
Místo cvičení: S6
Toto cvičení je k přednášce Jana Hubičky (Pátek od 9:00 v S3)

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í

23.2.2018
Shazování vajíček z mrakodrapu. Největší součet v posloupnosti. Binární vyhledávání. Najít v setřízené posloupnosti indexy $i$ a $j$, takové, že $x_i+x_j=S$.
2.3.2018 Notace $O,o,\Omega,\omega,\Theta$.
Definice.
Příklady algoritmů k jednotlivým třídám ($\Theta(1),\Theta(\log n),\ldots,\Theta(n^c),\Theta(2^n)$).
Porovnávání dvojic funkcí a setřízení množiny funkcí do přihrádek.
Důkaz/vyvrácení jednoduchých tvrzení ($f\in O(g)\iff g\in O(n)$, $f\in O(g)\implies 2^f\in O(2^g)$, $2^{O(\log n)}=O(?)$).
Problém s indukcí $f(n)=n^2, f\in O(n), f(n)=O(n)+f(n-1)=O(n)+O(n)=O(n)$.
K zamyšlení: Algoritmus se složitostí $O(n^c)$ pro různá $c$. Co nejlepší odhad $\log_n n$.
9.3.2018 BFS
Různé reprezentace grafů a jejich vlastnosti (velikost, operace).
Jak kódovat různé problémy do grafu? (stavový prostor, mapy, ...)
Pseudokód BFS, prostorová a časová složitost.
Dosažitelnost vrcholů z $v_0$.
Nejkratší cesty v neohodnoceném grafu.
Nejkratší cesty v grafu s ohodnocením $1,\ldots,K$.
16.3.2018 DFS
Algoritmus DFS a strom prohledávání. Klasifikace hran.
Linefolower s fixama v bludišti.
Detekce cyklů v orientovaných i neorientovaných grafech.
Mazání vrcholů tak, aby byl graf souvislý.
Nalézt v orientovaném grafu vrchol, ze kterého je celý graf dosažitelný.
Max NzMn ve stromu.
23.3.2018 DFS a DAG
Hledání mostů.
DAG. Jak ověřit že je graf DAG
Nalezení všech zdrojů a stoků.
Topologické číslování pomocí DFS
Počet všech cest v DAG
6.4.2018 Nejkratší cesty
BFS - minotaur, podrozdělení hran
Hledání nejkratších cest. Djikstra s použitím různých datových struktur. časová analýza
Problém s ohodnocenýi vrcholy, záporné hrany v grafu (sousedící se strartovním vrcholem), orientace grafu.
13.4.2018 Nejkratší cesty 2.0
Bellman-ford obě varianty (relaxace vrcholů i hran) Detekce a výpis záporných cyklů.
Označení všech hran které leží alespoň na jedné nejkratší cestě.
Floyd-warshall
Výpis nejkratších cyklů pro každý vrchol, detekce záporných cyklů.
Nejproustnější cesta, nejkratší nejpropustnější cesta.
20.4.2018 Minimální kostry
Kruskal, jarník a borůvka.
Problém unikátních vah pro různé grafy.
Máme nejlehčí kostru. Změníme váhu libovolné hrany. Jak updatovat nejlehčí kostru.
Jak najít 2.nejlehčí kostru.
27.4.2018 BVS
Definice BVS, implementace operací.
Vyvážené stromy, výpis všech prvků, konstrukce dokonale vyvážených BVS.
Výpis $k.$ prvku v BVS.
4.5.2018 $ab$-stromy
Definice vyhledávacích stromů, $ab$-stromů, operace find, insert delete ( i s předvídáním ), složitost.
18.5.2018 Rozděl a panuj
MergeSort a jeho úpravy, násobení čísel.
Master Theorem, jak se k ní dostat, algoritmy jednotlivých případů.
Příklady rekruzivních rovnic a jejich řešení
Najít prvek $A[i]=i$ v setřízeném poli.
25.5.2018 Zápočtové příspěvky
Amortizovaná složitost. Heshování a jeho použití.

Úkoly

1. Úkol (do 2.3.2018 12:21)
(časová a paměťová složitost, pseudokód)
1. Na vstupu je text složený z písmen české abecedy a mezer. Navrhněte algoritmus, který najde nejkratší úsek, který obsahuje všechna písmena abecedy (nerozlišujeme velká a malá písmena).
2. Na vstupu je text složený z písmen české abecedy a mezer. Navrhněte algoritmus, který najde nejdelší úsek, ve kterém se žádné písmeno neopakuje.
2. Úkol (do 9.3.2018 12:21)
Dokažte nebo vyvraťte:
1.$f(n)=\Theta (h(n))\wedge g(n)=\Theta(h(n))\implies f(n)+g(n)\in\Theta(h(n))$
2.$f(n)=O(g(n))\wedge g(n)=O(h(n))\implies f(n)=O(h(n))$
3.Charakterizujte pro která $f$ (ne)platí $f(n)=O(f(\frac{n}{2}))$.
3. Úkol (do 16.3.2018 12:21)
Pseudokód, prostrová a časová složitost, slovní popis řešení, důkaz správnosti.
1. Modifikujte algoritmus BFS tak, aby pro graf $G$ vypsal nejkratší cestu mezi $u$ a $v$. Pokud jich je víc, tak může vypsat libovolnou z nich.
2. Virus Máme uzavřený komplex laboratoří, ve kterém se pracuje s nejrůznějšími viry. Pro případ nehody, kdy by nějaký virus unikl, je v komplexu umístěno několik průduchů, ze kterých se v případu poplachu začne šířit smrtící plyn, který zabije jakýkoliv virus. Můžeme počítat, že mapu komplexu můžeme nakreslit na čtvercovou síť. Tato síť je navíc taková, že pokud políčko již zamořené, pak se v další vteřině zamoří všechna sousedící políčka (vlevo, vpravo, nahoru i dolu). Popište algoritmus, který vám řekne, za jak dlouho bude celý komplex naplněn tímto smrtícím plynem (a řekne výzkumníkům, za jak dlouho od startu poplachu musí utéct do bezpečí).
3. Navrhněte algoritmus, který spočítá počet nejkratších cest mezi vrcholy $u$ a $v$ pro graf $G$.
4. Úkol (do 23.3.2018 12:21)
Pseudokód, prostorová a časová složitost, popis a důkaz správnosti.
1. Navrhněte algoritmus, který pro orientovaný graf $G=(V,E)$ nalezne vrchol $v$, ze kterého jsou dosažitelné všechny vrcholy $V$ ale z žádného vrcholu $u\in V\setminus\{v\}$ neexistuje orientovaná cesta z $u$ do $v$.
2. Navrhněte algoritmus, který pro strom $T=(V,E)$ nalezne nejmenší vrcholové pokrytí. Vrcholové pokrytí je množina vrcholů $U\subseteq V$ takový, že $\forall v\in V \exists u\in U: \{u,v\} \in E$.
3. Algoritmus, který najde v grafu 4 cyklus?
5. Úkol (do 6.4.2018 12:21)14 dnů
Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost
1. Popište důkladně algoritmus na hledání artikulací (PSEUDOKÓD je hlavní částí)
2. Topologické číslování acyklického orientovaného grafu je funkce $f:V\rightarrow \{1,\ldots,|V|\}$ taková, že pro každou hranu $uv\in E$ platí, že $f(u)<f(v)$ a pro každé $u,v\in V: u\neq v$. (Topologické uspořádání je lineární uspořádání $\prec$ takové, že $uv\in E: u\prec v$).
Popište algoritmus, který nalezne topologické číslování (uspořádání). To, že je graf orientovaný acyklický ověřovat nemusíte. Algoritmus nesmí používat DFS ani BFS. O(m+n)
3. Eulerovské tahy. Pro libovlný graf $G$ zjistěte, jestli existuje eulerovský tah, tedy posloupnost hran $T=e_1,\ldots, e_m$ taková, že $i\neq j \implies e_i\neq e_j$, $|e_i\cap e_{i+1}|=1$ a $e\in E\iff e\in T$. Pokud graf eulerovský tah existuje, algoritmus ho vypíše (nebo vrátí ve vhodné datové struktuře).
Algoritmus slouží k tomu, jak nakreslit graf pomocí jednoho tahu, aniž bychom prošli po libovolné hraně víckrát a aby obsahoval všechny hrany.
6.úkol (do 13.4.2018 12:21)
1. Najděte graf, ve kterém pro nějaké dva vrcholy existuje $2^{\Omega(n)}$ nejkratších cest. (orientovaný nebo neorientovaný graf). Dokažte že je jich tam skutečně tolik.
2. Navrhněte datovou strukturu pro Djikstrův algoritmus se vstupním orientovaným grafem $G=(V,E,c)$, kde $c:E\rightarrow \{1,\ldots,L\}$ takovou, že algoritmus bude mít složitost $O(nL+m)$. Pokuste se i o to, abyste potřebovali pomocnou paměť $O(n+m+L)$. (Podrozdělení hran není správné řešení). Složitost dokažte.
7.úkol (do 20.4.2018 12:21)
Pokud nepoužíváte standartní algoritmy (v původní podobě), pište pseudód. Pro všechny úkoly: Časová, prostorová složitost, důkaz správnosti.
1. Mějme síť routerů, které jsou spojeny mezi sebou (ne nutně všechny). Pro každou dvojici routerů, mezi kterými je přímé spojení máme definovanou spolehlivost přenosu, což je pravděpodobnost, že zpráva projde přes toto spojení nepozměněná. Spolehlivost přenosu mezi dvěma routery po dané cestě je součin spolehlivostí přenosu po jednotlivých spojení na dané cestě. Jak najít mezi dvěma routery nejspolehlivější cestu pro přenos? (cesta s nejvyšší pravděpodobností úspěšného přenosu nepozměněné zprávy) Djikstra, pokud budete modifikovat djikstru, tak napište pseudokód, netriviální věci dokažte.
2. Máme mapu silnic a každá silnice je ohodnocena dobou průjezdu a mýtem (cena za projetí). Najděte nejlevnější z nejkratších cest pro dvě města $A$ a $B$. (Délka cesty je kladná hodnota a cena za průjezd je nezáporná.)
3. Směnárna obchoduje s $n$ měnami a máme kurzovní lístek $K$, kde na pozici $K_{ij}$ je určeno kolik za jednu jednotku měny $i$ dostaneme jednotek měny $j$. Vlastníte $b$ jednotek měny 1. (1.řádek lístku $K$). Najděte a vypište posloupnost měn $1,m_1,\ldots,m_k,1$ takovou, že postupnou výměnou $1\rightarrow m_1 \rightarrow \ldots\rightarrow n$ takovou, že budete mít co největší obnost $b'$ měny $1$.
4. Chcete vydělat na směnárně definované výše. Najděte tedy posloupnost výměn takovou, že pro libovolnou měnu $i\in\{1,\ldots,n\}$ získáte více peněz než jste měli na začátku(v dané měně).
8.úkol (do 27.4.2018 12:21)
1. Navrhněte implementaci(pseudokód) pro Borůvkův algoritmus, kde v každém kroku zkontrahujete hrany místo jejich spojování. Ukažte časovou a prostorovou složitost i správnost vašeho přístupu.
2. Pro graf $G$ známe nejlehčí kostru $K$. Pro libovolnou hranu $e\in E(G)$ vytvoříme nový graf $G_e=(V(G),E(G)\setminus{e})$. Jak transformovat kostru $K$ na nejlehčí kostru v grafu $G_e$? (algoritmus, správnost, složitosti)
3. Navrhněte algoritmus na nalezení minimální kostry $K$ v grafu $G$ takovou, že nějaká množina vrcholů $U\subseteq V$ jsou listy v kostře $K$. (algoritmus, správnost, složitost)
9.úkol (do 4.5.2018 12:21)
1. Pro dva binární vyhledávací stromy $T_1,T_2$ popište funkci $join(T_1,T_2)$, která spojí tyto stromy do jednoho binárního vyhledávacího stromu $T$ a funkci $split(T,x)$, která rozdělí strom $T$ na dva binární vyhledávací stromy $T_1$ a $T_2$ takové, že $\forall v\in T_1: v\leq x$ a $\forall v\in T_2 x\leq v$ ($x$ nemusí být prvek v $T$). Jakou mají časovou složitost?
2. Upravte hloubkově vyvážený strom tak, aby v čase $O(\log n)$ uměl vrátit $k.$ prvek v pořadí. Zároveň mušite zachovat časovou složitost všech standartních operací (FIND, INSERT, DELETE). Ukažte jak zachovat tuto složitost. Pro důkaz si zvolte buď AVL nebo červenočerný strom. Do vrcholů si můžete přidávat nějaké další informace, ale prostorová složitost musí zůstat zachována.
3. Navrhněte algoritmus, jak pro dvě setříděné posloupnosti $S_1,S_2$ najít medián jejich sjednocení v čase $O(\log(|S_1|+|S_2|))$. (Posloupnosti $S_1$ a $S_2$ jsou "orákulum" které vám v konstantním čase umí v konstatním čase vrátit $k.$ prvek.
10.úkol (do 11.5.2018 12:21)
1. Navrhněte redundatní $ab$-strom. Tedy data (struktura, která obsahuje klíč podle kterého můžu položku vyhledat a nějaký obsah) jsou uložena jen v listech (vrcholy, které mají za syny jen NULL) a vnitřní vrcholy obsahují jen klíče. Jak budou vypadat klíče ve vnitřních uzlech? Ukažte, jak budou fungovat operace Insert a Delete u těchto $ab$-stromů.
2. Mějme $ab$-stromy $X$ a $Y$ takové, že $\max(X)<\min(Y)$. Navrhněte jak naimplementovat funkci $join(X,Y)$ která vrátí opět validní $ab$-strom, který vznikne jejich slitím (ideálně v čase $o(|X|+|Y|)$)
3. Navrhněte funkci $split(X,x)$ která rozdělí $ab$-strom podle prvku $x$ na dva $ab$-stromy $S,T$ takové, že $\max(S)<x\leq\min(T)$. (ideálně v čase $o(|X|)$)
4. Pro permutaci chceme získat její pořadí vzhledem k lexikografickému uspořádání na množině $\{1,\ldots,n\}$. Jak toho docílit pomocí vyhledávacích stromů? Jak vygenerovat $k.$ permutaci (vzhledem k lexikografickému uspořadání)? V čase $O(n\log n)$.
11.úkol (do 25.5.2018 12:21)
1. Máte sadu šroubků a matiček. Pro dvojici matici šroubek jste schopni říci, zda matice pasuje na šroubek, matice je příliš velká nebo příliš malá. Jak co nejrychleji spárovat všechny šroubky a matice?
2. Navrhněte algoritmus na násobení dlouhých čísel $X,Y\leq 10^n$ ($X,Y$ mají $n$ cifer), který bude mít složitost $o(n^2)$ (tzn. $O(n^c)$ pro $c<2$). Složitost odvoďte pomocí Master theorem. Kolik pomocné paměti potřebujete?
3. Naprogramujte MergeSort bez rekurze. Součástí je i přehlednost a srozumitelnost kódu.
4. Navrhněte implementaci mergesort bez použití dalšího pomocného pole. Všechny operace musí být provedeny uvnitř tohoto pole. Časová složitost $O(n\log n)$ a pomocný prostor $O(1)$.
5. Inverze v permutaci je dvojice $i,j$ taková, že pro $i<j$ platí $x_i>x_j$. Jak spočítat počet inverzí v libovolné permutaci v čase $O(n\log n)$?
6. V setřízeném poli nalezněte prvek $A[i]=i$. (a)$\forall i,j$ $A[i]\neq A[j]$, $A[j]\in \mathbb{N}$ (unikátní přirozená čísla) (b) $\forall i, A[i]\in\mathbb{N}$ (neunikátní přirozená čísla) (c) $\forall i,j$ $A[i]\neq A[j]$ $A[i]\in\mathbb{R}$. Pokud takový prvek neexistuje pak vraťte false. Proč u některých variací nefunguje binární vyhledávání?