Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
36TI Teoretická informatika Rozsah výuky:3+2
Přednášející (garant):Kolář J. Typ předmětu:Z Zakončení:Z,ZK
Zodpovědná katedra:336 Kreditů:6 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. Dalšími zahrnutými tématy jsou hledání ve stavovém prostoru, matematické modely programů a výpočtů, matematická sémantika programů (teorie pevného bodu) a teorie složitosti (třídy P a NP, NP-úplnost).

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. Modely programů, počítačů a výpočtů, ekvivalence programů
11. Algoritmy a univerzální stroje, nerozhodnutelné problémy
12. Definice funkcí pomocí rekurze, teorie pevného bodu
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 sem. úloze
7. Dominance, nezávislost, stromy
8. Kostry, minimální kostry
9. Nejkratší cesty
10. Konzultace k semestrální práci
11. Úlohy vhodné pro dynamické programování
12. Toky v síti - řešení základní a odvozených úloh, konzultace
13. Prohledávání stavového prostoru úloh, heuristické hledání
14. Odevzdávání semestrální úlohy, zápočet

Literatura Č:
[1] Kolář, J.: Teoretická informatika. ČIS, Praha 1996
[2] Kolář, Chytil, Štěpánková: Logika, algebra a grafy. SNTL, Praha 1989
[3] Cormen, T.H. et al. : Introduction to Algorithms. MIT Press, Cambridge, Mass. 1990

Literatura A:
[1] Cormen, T.H. et al. : Introduction to Algorithms. MIT Press, Cambridge, Mass. 1990

Požadavky:

Rozsah výuky v kombinované formě studia: 19+4
Typ cvičení: s
Tento předmět je nabízen také v anglické verzi

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
*VTBE Výpočetní technika Z 5
*VTBEB Výpočetní technika Z 5


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)