Teoretická informatika
Kód | Zakončení | Kredity | Rozsah |
---|---|---|---|
X36TIN | Z,ZK | 5 | 2+2s |
- Předmět je náhradou za:
- Teoretická informatika (Y36TIN)
- Přednášející:
- Josef Kolář, Neurčen (gar.), Andrej Chu, Daniel Průša, Karel Zimmermann
- Cvičící:
- Josef Kolář, Neurčen (gar.), Andrej Chu, Daniel Průša, Karel Zimmermann
- 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í
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
Typ cvičení: s
Předmět je nabízen také v anglické verzi.
- Rozvrh na zimní semestr 2011/2012:
- Rozvrh není připraven
- Rozvrh na letní semestr 2011/2012:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Předmět je součástí následujících studijních plánů:
-
- Výpočetní technika- strukturované studium (povinný předmět)
- Manažerská informatika (volitelný předmět odborný)
- Inteligentní systémy (volitelný předmět odborný)