- Úkol
Dokažte $f(n)\in \Omega(g(n))\Rightarrow g(n)\in O(f(n))$
- Úkol
Upravte vyvážený binární vyhledávací strom (uzel obsahuje klíč a ukazatel na syny a rodiče) tak,
aby poskytoval funkci vrat_prvek(r,k),
kde r je kořen struktury a k je pořadí prvku podle velikosti.
(Funkce vrátí k. nejmenší prvek obsažený ve stromu.)
Složitost této funkce by měla být $O(\log n)$ a ostatní funkce si svou složitost musí zachovat (find, insert, delete $\in O(log n))$.
- Úkol
Nechť $T_1$ a $T_2$ jsou dva binární vyhledávací stromy se stejnou množinu $n$ klíčů. Dokažte, že $T_1$ lze na $T_2$ převést pomocí $O(n)$ rotací.
- Úkol
Inverze v permutaci $f:X\rightarrow X$ je dvojice prvků $i,j\in X$ taková, že $i<j \wedge f(i)> f(j)$.
Na cvičení jsme si popsali algoritmus pro hledání počtu inverzí v $O(n^2)$. Pokuste se algortimus zlepšit použitím AVL stromů.
Chceme tedy algoritmus, který pro permutaci zadanou polem $A=[a_1,a_2,\ldots,a_n]$ spočte počet inverzí permutace v čase $O(n\log n)$.
Hint:
V algoritmu z cvičení procházíme pro každý index $i$ všechny $j> i$ a zjišťujeme, jestli prvky $i,j$ nejsou inverzí tedy $a_j< a_i$.
Ve vyhledávacím stromu, jak jsme si v 2. Úkolu ukázali umíme doplnit nějakou informaci, o velikosti podstromu a navíc jsme schopni extrahovat k. nejmenší prvek.
Nešel by každý ze zmíněných postupů obrátit a pak jich využít k řešení?
-
Velikonoční bonus
Fibonacciho posloupnost je posloupnost, která splňuje $F_0=0$, $F_1=1$ a pro všechna $n\geq 2:F_n=F_{n-1}+F_{n-2}$. Vypočtěte $n$. prvek fibonacciho posloupnosti (tedy číslo $F_n$) v čase $O(\log n)$. (Můžete zkusit vyřešit alespoň verzi pro $n=2^i$ pro $i\in\mathbb{N}$).
Hint: Zkuste si pohrát s maticí
$\left(
\begin{array}{ c c }
1 & 1 \\
1 & 0
\end{array} \right)$
- Úkol
Popište algoritmus pro nalezení nejdelší cesty ve stromě $T=(V,E)$ v času $O(|V|+|E|)$. Součástí řešení by mělo být rozebráno i to, že cesta nalezená algoritmem je vskutku nejdelší.
- Úkol
Popište algoritmus na hledání artikulací v neorientovaném souvislém grafu $G=(V,E)$.
(artikulace je vrchol $v\in V(G)$ takový, že $G=(V\setminus\{v\},E\cap{V\setminus\{v\} \choose 2}$ je nesouvislý. Algoritmus popište v pseudokódu.
- Úkol
Pro orientovaný acyklický graf $\vec{G}=(V,\vec{E})$ popište dva různé algoritmy pro nalezení topologického uspořádání. Hint: jeden z možných přístupů na to jde přes prohledávání, ale lze se obejít i bez toho. Algoritmy by měli být lineární vzhledem k velikosti grafu ($O(|V(\vec{G})|+|\vec{E}(\vec{G})|)$).
- Úkol
Graf je polosouvislý právě tehdy, když $\forall u,v\in G$ existuje orientovaná cesta $u\rightarrow v$ nebo $v\rightarrow u$. Popište algoritmus, který zjistí o orientovaném grafu $G$, zda je polosouvislý s časovou složitostí $O(|E|+|V|)$. Pokud budete používat algoritmus na silně souvislé komponenty, pak alespoň stručně popište jak a proč algoritmus funguje i s časovou složitostí.
- Úkol
Mějme nějakou mapu, na jaké se silnice kříží jen ve městech. Každá silnice je nějak dlouhá a na každé silnici máme váhové omezení pro auta, která po ní chtějí projet. Chceme nalézt nejkratší cestu mezi městy $A,B$ (abychom ušetřili na benzínu), ale zároveň chceme mít auto naložené co nejvíc (pašujeme fyzikální tabulky).
Formálně: Pro ohodnocený neorientovaný graf $G=(V,E,c,p)$, kde $c:E\rightarrow\mathbb{R^+}$ je délka hrany, $p:E\rightarrow\mathbb{R^+}$ je průtok hrany, nalezněte nejkratší cestu mezi vrcholy $u$ a $v$ s největším průtokem. Pro cestu $i=v_1,\ldots,v_n$ je délka cesty $c_i=\sum_{i=1}^{n-1} c(i,i+1)$ průtok cesty $p_i=\min_{i=1}^{n-1} p(i,i+1)$.
- Úkol
Floyd-Warshallův algorimus funguje v jednotlivých cyklech nad maticí vzdáleností $D$ a spočítá pro ohodnocený orientovaný graf $G$ matici délek nejkratších cest mezi každými dvěma vrcholy $u,v\in V(G)$. Formulaci a některé vlastnosti lze nalézt kupříkladu ve skriptech od Martina Mareše
zde.
Za použití F-W algoritmu navrhněte algoritmus pro detekci záporných cyklů.
- Úkol
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.)
Bonusové úkoly do začátku zkouškového