Opakování \(\mathcal{O}\) (složitost)
Nechť \(f_1, f_2, f, g: \mathbb{N} \to \mathbb{R}^+\). Dokažte nebo vyvraťte tato tvrzení:
- \(f_1 \in \mathcal{O}(g) \wedge f_2 \in \mathcal{O}(g) \implies f_1 \cdot f_2 \in \mathcal{O}(g ^ 2)\),
- \(f_1 \cdot f_2 \in \mathcal{O}(g ^ 2) \implies f_1 \in \mathcal{O}(g) \wedge f_2 \in \mathcal{O}(g)\),
- \(f \in \mathcal{O}(f^2)\).
Definice si můžete připomenout na stránce 3. cvičení.
Úlohy na procvičení – grafy
Cesta králem na šachovnici (délka)
Řešte úlohu Cesta králem na šachovnici (délka) v ReCodExu. Program bude hledat nejkratší cestu šachovým králem na šachovnici \(8 \times 8\), kde na některá políčka nelze vstoupit.
Můžete použít šablonu, která za vás vyřeší načítání vstupu (v původním vstupu jsou souřadnice políček 1 až 8, ale v reprezentaci v šabloně jsou 0 až 7). Do šablony stačí doplnit procházení možných tahů krále (metoda get_neigbors) a dokončit předpřipravený kód pro bfs.
Nejkratší cesta v ohodnoceném grafu
Problém nejkratší cesty lze zobecnit na grafy s nezáporným ohodnocením hran, kde je délka cesty měřena součtem ohodnocení hran.
Nalezne algoritmus BFS nejkratší cestu i v tomto případě? Pokud ano, vysvětlete proč, pokud ne, sestrojte protipříklad.