Hubička 15. 5. 2026

Byl moc milý, v podstatě jsme dostali papír se zadáním, ať si k tomu sepíšem co chceme a pak za ním přijdeme.

zadání:

1. Napište algoritmus pro hlednání silně souvislých komponent a dokažte jeho správnost

2. napište kuchařkovou větu o rekurenci a použijteji pro důkaz složitosti nějakého algoritmu

3. máte orientovaný graf kde každá hrana má váhu $1$ nebo $-1$, navrhněte algoritmus který zjistí zda graf obsahuje záporné cykly

4. máte orientovaný acyklycký graf a dostanete dva vrcholy $x$ a $y$, navrhněte algoritmus který určí počet cest z $x$ do $y$.

5. Bonus: navrhněte funkce $f$ a $g$ takové že $f\ne O(g)$ a $g\ne O(f)$