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 14:00--15:40
Místo cvičení: S7
K přednášce, kterou vede Jan Hric (Úterý od 10:40 v S5)

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.
Anglická kniha o algoritmech zde.

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í

20.2.2019 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í
Důkaz/vyvrácení jednoduchých tvrzení.
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$.
27.2.2019 Složitost 2.0
Důkazy jednoduchých tvrzení. Analýza jednoduchých problémů - součet dvou indexů, součet souvislého úseku, .... Co by se stalo kdybychom uměli rychle násobit?
6.3.2019 BFS a DFS
BFS (cesta z MS na hostivař), DFS (linefollower s fixem), strom prohledávání, Klasifikace hran. paměťová a prostorová složitost.
Problém střeleného koně (kůň po vykousané šachovnici s pohybem jednou jak kůň a jednou jak král má nalézt cestu do domečku.
Rozebrání grafu na komponenty souvislosti.
Nejkratší cesty v neohodnocených grafech a v grafech s omezenými kapacitami.
13.3.2019 Prohledávání
Theseus a minotaur.
Auto na manhattnu s odbočkama rovně a doprava.
Počet nejkratších cest.
Hledání mostů.
NzMn ve stromu.
20.3.2019 DAG
Problém orientovaných acyklických grafů.
Topologické číslování/uspořádání.
Nejdelší cesta v DAG.
Komponenty silné souvislosti
27.3.2019 Nejkratší a ještě kratší cesty
Djisktra, bellman-ford, FW algoritums. Jak fungujou, pseudokód složitost.
Halda a operace na ní.
Jak se vypořádat se zápornými cykly/hranami.
3.4.2019 Nejkratší cesty a Minimální kostry
Hledání spojení, spolehlivost routerů, silnice s nejvyšší průjezdností, nejkratší silnice s průjezdností a jiné aplikace nejkratších cest.
Minimální kostyr - Jarník.
10.4.2019 Minimální kostry
Kruskal na Borůkách. Druhá nejlehčí kostra.
17.5.2019 BVS, ab-stromy
Definice vyhledávacích stromů, $ab$-stromů, operace find, insert delete, složitosti, datová struktura pro nalezení maxima z intervalu. Rotace a vyváženost stromů.
24.4.2019 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í. Substituční metoda.
15.5.2018 Hash.
Amortizovaná složitost. Hash.

Úkoly

1. Úkol (do 27.2.2019 14:01)
O, $\Theta$, a tak...
1.Dopočítejte konstanty $c,n_0$ pro $f(n)=O(g(n))$ kde $f(n)=1/2n^3+15n^2-12n+5$.
2.Nechť $n$ je proměnná a $c$ je konstanta. Setřiďte následující funkce pomocí O a $\Theta$: $n!, 2^n, 1, n^2, 4^{\log_2 n}$. (Čím víc správných zatřízení tím víc bodů.)
3.Dokažte nebo vyvraťte: $f(n)=\Theta (h(n))\wedge g(n)=\Theta(h(n))\implies f(n)+g(n)\in\Theta(h(n))$
4.Dokažte nebo vyvraťte: $f(n)=O(g(n))\wedge g(n)=O(h(n))\implies f(n)=O(h(n))$
5.Pro kterou funkci $f(n)$ neplatí a proč: $f(2n)=O(f(n))$.
6.Dokažte nebo vyvraťte $2^{O(\log n)}=O(n)$.
2. Úkol (do 6.3.2019 14:01)
Složitost 2.0
1. Dokažte:$f\in O(h)\wedge g\in O(i)\implies fg\in O(hi)$.
2. Dokažte $f\in \Theta(h)\wedge g\in o(f)\implies f+g\in\Theta(f)$.
3. 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).
4. 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.
5. Vajíčka a mrakodrap. Máte 2 stejná vajíčka, a mrakodrap s $n$ patry. Pro obě vajíčka platí, že existuje patro $k$, takové, že při pádu z patra $i\leq k$ se nerozbijí a při pádu z patra $j\geq k+1$ se rozbijí. Jak nalézt toto rozhraní pro co nejméně shození vajíčka z mrakodrapu? Dokažte složitost a zkuste ukázat že to lépe nejde.
6. Hodně vajec a mrakodrap. Stejně jako v úkolu č 5, ale máte $l$ vajíček.
3. Úkol (do 13.3.2019 14:01)
Pseudokód, prostrová a časová složitost, slovní popis řešení, důkaz správnosti.
1. Cyklus? Tady je. Popište algoritmus, který v lineárním čase ($O(n+m)$) detekuje libovolný cyklus v grafu a vypíše ho.
2. Cyklus!!! Popište algoritmus, který v čase $O(n)$ rozhodne, zda v grafu existuje cyklus.
3. Zvídavý student. Popište algoritmus, jak z grafu $G$ postupně odebírat vrcholy tak, aby se neporušila souvislost grafu. ($O(n+m)$)
4. Labyrint a theseus. Theseus se snaží utéct z labyrintu, kde je Minotaur. Za každý jeden krok Thesea se Minotaur snaží přiblížit k Theseovi 2 kroky a to tak, že nejdřív snižuje $x$ vzdálenost, když nemůže tak snižuje vzdálenost $y$ a když ani to nemůže tak stojí. Navrhněte algoritmus, který pomůže najít Theseovi bezpečtnou cestu z bludiště, pokud existuje.
5. Dvojčata. Dostali jsme 2 bludiště (různá) s identickými roboty a několika východy. Máme jeden ovladač, na který reagují oba roboti stejně a umí jít jedním ze čtyř směrů (S,J,Z a V). Naším cílem je dostat oba roboty bezpečně z bludiště některým z východů. Najděte sekvenci která je dostane ven.
4. Úkol (do 20.3.2019 14:01)
Pseudokód, prostorová a časová složitost, popis a důkaz správnosti.
1. Policajti. Pro graf $G=(V,E)$ je vrcholové pokrytí množina vrcholů $S\subseteq V$ taková, že každá hrana $e\in E$ je hlídaná alespoň jedním vrcholem z $S$, takže $\exists v\in S: v\in e$. Popište algoritmus, který najde minimální (velikost) vrcholové pokrytí pro graf $T=(V,E)$, který je strom.
2. Rozpad mluvy. Pro souvislý graf $G$ je $v$ artikulace právě tehdy, když $G\setminus\{v\}$ (odebereme z $G$ vrchol $v$ a všechny incidentní hrany) je nesouvislý. Najděte a popište algoritmus, který všechny artikulace grafu $G$ najde a vypíše. Algoritmus musí být lineární $O(m+n)$.
3. Šéf šéfů. 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$.
4. Zase ty cykly. Algoritmus, který najde v grafu 4 cyklus?
5. Úkol (do 27.3.2019 14:01)
Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost
1. Silné kompoty. Mějme orientovaný graf $G=(V,E)$. Silně souvislá komponenta $K\subseteq V$ je množina vrcholů taková, že mez libovolnými dvěma vrcholy $u,v\in K$ existuje orientovaná cesta. Z komponent souvislosti orientovaného grafu, lze udělat DAG (orientovaný acyklycký graf), jehož vrcholy odpovídají komponentám silné souvsilosti. Navrhněte algoritmus který v lineárním čase $O(n+m)$ nalezne stokovou komponentu silné souvislosti a označí všechny vrcholy z této komponenty.
2. Do stoky je cesta. Pro orientovaný acyklycký graf $G=(V,E)$ navrhněte algoritmus, který spočítá počet všech cest pro dva dané vrcholy $u$ a $v$.
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 3.4.2019 14:01)
Za použití algoritu specifikovaném ve jméně úlohy vyřešte.
1.Djikstra na speedu. 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.
2.BF (ne brute force). Navrhněte algoritmus (paeudokód, popis, složitost, správnost), který pro daný orientovaný graf $G=(V,E,c)$ najde a vypíše záporný cyklus.
3.FW šmelina. Chcete vydělat na směnárně, která má kurzy zadané v tabulce, kde na pozici $i,j$ je hodnota, kolik peněz měny $j$ dostanete za jednu jednotku měny $i$. 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ě).
7.úkol (do 17.4.2019 14:01)
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á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á.)
2. Pro graf $G$ a dva vrcholy $s,t$ nalezněte všechny hrany, které se nachází alespoň na jedné z nejkratších cest.
3. Pro neorientovaný ohodnocený graf $G=(V,E,c)$ a množinu vrcholů $S\subseteq V$ navrhněte algoritmus, který najde minimální kostru grafu $G$, u které jsou všechny vrcholy z množiny $S$ listy nalezené kostry.
8.úkol (do 24.4.2019 14:01)
1.Meditující Dřevorubec. Pro dva binární vyhledávací stromy $T_1,T_2$ popište funkci $split(T,x)$, která rozdělí binární vyhledávací 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< v$ ($x$ nemusí být prvek v $T$). Jakou mají časovou složitost? (4b) $T,T_1,T_2$ musí být vyvážené stromy (+1b)
2. Modificient BVS. 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. Orákulum v lese. Pro $a,b$-strom navrhněte proceduru INSERT s předvídáním, tedy proceduru, která vloží prvek na správné místo a navíc neštěpí vrcholy při výstupu z rekurze, ale už při zanořování do rekurze. Procedura tedy načte každý uzel jen při zanořování do rekurze.
9.úkol (do 15.5.2019 14:01)
1.substituce. Vyřešte pomocí substituční metody následující rekurentní rovnice. $T_1(n)=T_1(n/3)+T_1(n/2)+O(n^2)$, $T_2(n)=2T_2(n/2)+O(n\log n)$, $T_3=\sqrt{n} T_3(\sqrt{n})+O(n)$.
2.Drátky. Mějme dlouhý kabel, z jehož obou konců vystupuje po $n$ drátech. Každý drát na levém konci je propojen s právě jedním na konci druhém a my chceme zjistit, který s kterým. K tomu můžeme používat následující operace: (1) přivést napětí na daný drát na levém konci, (2) odpojit napětí z daného drátu na levém konci, (3) změřit napětí na daném drátu na pravém konci. Navrhněte algoritmus, který pomocí těchto operací zjistí, co je s čím propojeno. Snažte se počet operací minimalizovat.
3.Je to složitý. Násobení komplexních čísel lze zapsat jako $(ai+b)(ci+d)=(ad+bc)i+(bd-ac)$. Můžeme si povšimnout, že potřebujeme 4 násobení. Protože násobení je drahé, chtěli bychom násobit komplexní čísla pouze s 3 násobeními (asi nám vzroste počet sčítání a odčítání). Jak to provedeme?
4.Ultra Merge. Popište MergeSort bez rekurze s konstantní pomocnou pamětí. Hlavní částí je čitelný a srozumitelný pseudokód. Časová složitost $O(n\log n)$ a pomocný prostor $O(1)$.
5.Slévání inverze. 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)$? (problém byste měli vyřešit pomocí metody Rozděl a panuj a přístupem podobn?ým MergeSrot)
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í?
10.úkol (do 22.5.2019 14:01)
1.Advanced matrix search. V matici přirozených čísel $n\times n$, takové, že $A[i,j]<A[i+1,j]$ a $A[i,j]<A[i,j+1]$ najděte $i,j$ takové, že $A[i,j]=i+j$(3b). chceme najít minimální $i,j$ (1b) Co když je to matice celých čísel? (1b)
2.Hash brown. Pro množinu $S$ a číslo $x$ najděte dvojici $x,y\in S$ takovou, že $s=x+y$. Čísla v množině $S$ nemůžete použít na index pole (jsou reálná a neomezené velikosti). Použijte hashování.
3.Dynamické pole. Mějme datovou strukturu dynamické pole, která podporuje 2 operace: insert a delete. Pole je statické, takže pokud ho naplníme, musíme alokovat nové pole větší velikosti a překopírujeme do něj všechny prvky. Pokud pomocí delete vyprázdníme pole příliš, necheme zabírat zbytečné místo, takže pokud je nesmí být naplněno s poměrem menším než $1/8$ kapacity (stejně jako u insert a rozšiřování musíme pole realokovat do menšího pole). Ukažte že pro vhodně zvolené zvětšení/zmenšení pole jsou operace insert a delete amortizovaně konstantní.
4.Master theorem. Master theorem známe pro rekurentní vztah $T(n)=aT(n)+n^c$. Nalezněte příklad algoritmu, který se chová tak, že je jeho složitost $O(n^c)$, tedy podle chování $a/b^c<1$.