1. | | Teoretické modely, neorientované grafy, základní vlastnosti |
2. | | Orientované grafy, silná souvislost, topologické uspořádání |
3. | | Způsoby reprezentace grafu, procházení do šířky a do hloubky |
4. | | Eulerovy grafy, dominující a nezávislé podmnožiny, vzdálenost |
5. | | Stromy, kostry, kružnice, minimální kostry, binární stromy |
6. | | Algoritmy Borůvky a Jarníka, Huffmanovo kódování |
7. | | Algoritmy hledání nejkratších cest, dynamické programování |
8. | | Toky v sítích, určení maximálního toku v síti |
9. | | Stavový prostor úloh, prohledávání, heuristické hledání |
10. | | Regulární jazyky a konečné automaty |
11. | | Turingovy stroje - struktura a chování |
12. | | Zobecnění Turingova stroje, nerozhodnutelné problémy |
13. | | Třídy složitosti P a NP, NP-úplnost |
14. | | Rezerva |
1. | | Použití základních matematických nástrojů (důkazy, indukce, rekurze) |
2. | | Operační složitost algoritmů, počítání s rekurencemi |
3. | | Neorientované grafy - základní vlastnosti |
4. | | Procházení grafů, rozklad na komponenty, zadání semestrální úlohy |
5. | | Orientované grafy - základní vlastnosti, prohledávání do hloubky |
6. | | Rozklad na silné komponenty, acykličnost, konzultace k semestrální úloze |
7. | | Dominance, nezávislost, stromy |
8. | | Kostry, minimální kostry |
9. | | Nejkratší cesty |
10. | | Úlohy vhodné pro dynamické programování |
11. | | Určování maximálního toku v síti, algoritmy heuristického hledání |
12. | | Regulární jazyky a konečné automaty |
13. | | Nedeterminizmus, konzultace k semestrální úloze |
14. | | Odevzdávání semestrální úlohy, zápočet |