Teoretická informatika
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
Y36TIN | Z,ZK | 5 | 2+2s | česky |
- Předmět nesmí být zapsán současně s:
- Teoretická informatika (A7B33TIN)
- Předmět je náhradou za:
- Teoretická informatika (A7B33TIN)
- Přednášející:
- Josef Kolář, Neurčen (gar.)
- Cvičící:
- Josef Kolář, Neurčen (gar.), Andrej Chu
- Předmět zajišťuje:
- katedra počítačů
- Anotace:
-
Předmět poskytuje základní přehled o pojmech a úlohách teorie grafů,
zaměřuje se především na algoritmické otázky a řešení grafových problémů,
přičemž významně využívá znalostí z programovacích technik. Přehledově jsou
zahrnuta další témata (např. konečné automaty, Turingovy stroje, třídy
složitosti P a NP).
- Požadavky:
- Osnova přednášek:
-
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
- Osnova cvičení:
-
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í
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
- Cíle studia:
- Studijní materiály:
-
1. Kolář, J.: Teoretická informatika. Praha: Česká informatická společnost.
2000
2. Cormen, T.H. et al. : Introduction to Algorithms. Cambridge, Mass.: MIT
Press. 1990
- Poznámka:
-
Rozsah výuky v kombinované formě studia: 14+6
- Další informace:
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů: