Kdy a kde:
Zapocet je za zapoctovou praci a prakticke ulohy.
- Zapoctova prace: sepsat povidani o reseni nejake zajimave programatorske ulohy, doplnene
programem (az na vyjimky, kde program nedava smysl). Tema na pozadani pridelim, vlastni temata vitam, ale vyzaduji schvaleni
predem. Tema byste meli mit zadano do konce dubna.
- Ulohy: behem semestru budou zadany dve prakticke ulohy, odevzdavane v Codexu.
- Ucast na cviceni neni povinna; na druhou stranu, pokud po me bude
chtit zapocet nekdo, koho jsem na cviceni nikdy nevidel, asi bude mit problem.
Obsah cviceni:
- Jednoduche priklady na dokazovani spravnosti a urcovani slozitosti algoritmu.
- RAM, slozitost nsd, dalsi priklady na spravnost a slozitost.
- O-notace. Aplikace hledani cest v grafu. Hledani nejkratsi cesty s logaritmickou
pametovou slozitosti.
- Prohledavani do hloubky, topologicke usporadani a jeho aplikace.
- Hranova a vrcholova 2-souvislost, mosty, artikulace, komponenty.
- Bellman-Forduv algoritmus a jeho modifikace.
- Dijkstra a Floyd-Warshall.
- Minimalni kostry.
- Binarni vyhledavaci stromy.
- Cerveno-cerne stromy, trie, hashovani.