Teoretická informatika

Předmět nesmí být zapsán současně s:

Teoretická informatika (Y36TIN)

Předmět je náhradou za:

Teoretická informatika (Y36TIN)

Přednášející:

Daniel Průša (gar.)

Cvičící:

Karel Zimmermann, Daniel Průša (gar.)

Předmět zajišťuje:

katedra kybernetiky

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, bezkontextové jazyky, Turingovy stroje, třídy složitosti P a NP).

Požadavky:

Postačuje znalost některého z programovacích jazyků (Java, C++).

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. Dominující a nezávislé podmnožiny, vzdálenost, stromy, kostry, kružnice.

5. Minimální kostry, binární stromy, Algoritmy Borůvky a Jarníka, Huffmanovo kódování.

6. Algoritmy hledání nejkratších cest, dynamické programování.

7. Toky v sítích, určení maximálního toku v síti.

8. Stavový prostor úloh, prohledávání, heuristické hledání.

9. Regulární jazyky a konečné automaty.

10. Gramatiky, Chomského hierarchie, bezkontextové jazyky.

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.

5. Orientované grafy - základní vlastnosti, prohledávání do hloubky.

6. Rozklad na silné komponenty, acykličnost.

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. Bezkontextové gramatiky.

14. Nedeterminismus, NP-úplnost.

Cíle studia:

Cílem kurzu je podat teoretické základy informatiky a rozvíjet abstraktní myšlení studentů při návrhu algoritmů. Hodně využívaným aparátem jsou grafy - z důvodu snadné představitelnosti a širokého uplatnění v praktických úlohách. Kurz lze chápat jako přípravu na přednášky, které zahrnují pokročilejší partie z teoretické informatiky.

Studijní materiály:

1. Kolář, J.: Teoretická informatika. Praha: Česká informatická společnost. 2004.

2. Stránka předmětu: http://cw.felk.cvut.cz/doku.php/courses/a7b33tin/start

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-126 Zimmermann K. 09:15–10:45 (přednášková par. 1 paralelka 101) Karlovo nám. Trnkova posluchárna K5místnost KN:E-126 Zimmermann K. 11:00–12:30 (přednášková par. 1 paralelka 102) Karlovo nám. Trnkova posluchárna K5mí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)