Teoretická informatika

Přednášející:

Cvičící:

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. 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).

Požadavky:

http://service.felk.cvut.cz/courses/36TI

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. 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

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 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

Cíle studia:

Studijní materiály:

[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

Poznámka:

Rozsah výuky v kombinované formě studia: 19+4

Typ cvičení: s

Tento předmět je nabízen také v anglické verzi

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ů: