[home]
ADS I (2022/2023)
Cvičení k přednášce Algoritmy a datové struktury I
Doporučená literatura
Organizace
K získání zápočtu je nutno nasbírat 80 bodů.
Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (za vyřešení více úkolů z jednoho cvičení je stále 10 bodů). Deadline pro odevzdání úkolu je vždy 14 dní.
Aktivita na cvičení bude odměněna $2,5$ body (více aktivity na jednom cvičení je stále $2,5$ bodů).
Úkoly i získané body nalezne na poštovní sově. Token pro zapsání bude zveřejněn na první hodině a rozeslán první týden semestru hromadným mailem. Pokud jste se k našemu cvičení přidali později, napište si o token přímo mě.
Probrané příklady
- 17.2.
- Podívali jsme se na model RAM. Jak zakódovat více čísel do jedné buňky, pokud není omezena velikost čísel. Jak pomocí instrukcí RAM definovat cyklus a funkci.
- Připomněli jsme si definice $O$, $\Omega$, $\Theta$ a seředili pár základních funkcí.
- 24.2.
- 3.3.
- DFS a BFS, klasifikace hran u obou algoritmů. Ukázali jsme jaké z hran neexistují v neorientovaných grafech.
- Opakování algoritmu pro hledání mostů v grafu.
- Prohledávání grafu vs prohledávání stavového prostoru.
- 10.3.
- DAG, topologické uspořádání a kdy je jednoznačné, topologická indukce
- Opakování nalezení silně souvislých komponent. Polosouvislost grafů.
- Dijkstrův algoritmus a jak se chová na grafech se zápornými hranami a zápornými cykly. Příště budeme s Dijkstrou pokračovat.
- 17.3.
- Dijkstrův algoritmus, odkrokování a časová složitost s různými datovými strukturami.
- Obecný relaxační algoritmus, náznak důkazu, že se nakonec vždy zastaví (pokud v grafu nejsou záporné cykly).
- 24.3.
- Dokončili jsme hledání nejkratších cest. Navíc jsme ukázali Floyd-Warshallův algoritmus pro hledání minimálních vzdáleností mezi všemi vrcholy.
- Minimální kostry - Jarník, Borůvka, Kruskal. Časové složitosti, zda vadí neunikátnost vah.
- 31.3.
- 14.4.
- 21.4.
- 28.4.
- 5.5.
- 12.5.
- 19.5.