XD36TIN | Teoretická informatika | Rozsah výuky: | 14+6 | ||
---|---|---|---|---|---|
Přednášející (garant): | Kolář J. | Typ předmětu: | Z | Zakončení: | Z,ZK |
Zodpovědná katedra: | 336 | Kreditů: | 5 | Semestr: | Z |
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).
Osnovy 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 |
Osnovy 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í | |
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 |
Literatura Č:
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 |
Literatura A:
1. | Kolář, J.: Theoretical Computer Science. Prague: CTU Publishing House. 1998 | |
2. | Cormen, T.H. et al. : Introduction to Algorithms. Cambridge, Mass.: MIT Press. 1990 |
Požadavky:
Studenti zpracují semestrální úlohu, jejíž kvalita spolu s průběžnou aktivitou a výsledky testů na cvičeních ovlivňuje výsledek závěrečné zkoušky.
Předmět je zahrnut do těchto studijních plánů:
|
Stránka vytvořena 25. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |