Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
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ů:
Plán Obor Role Dop. semestr
BVT-D Výpočetní technika Z 3


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)