Teoretická informatika

Přednášející:

Neurčen (gar.), Josef Kolář, Daniel Průša, Karel Zimmermann

Cvičící:

Neurčen (gar.), Andrej Chu, Josef Kolář, 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:

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

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á	místnost KN:E-107 Průša D. 12:45–14:15 (přednášková par. 1) Karlovo nám. Zengerova posluchárna K1

Předmět je součástí následujících studijních plánů:

• Softwarové inženýrství (povinně volitelný předmět)
• Web a multimedia (povinně volitelný předmět)