Úvod do teoretické informatiky

Garant předmětu:

Petr Ambrož

Přednášející:

Petr Ambrož

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Základní pojmy teoretické informatiky: algoritmy, různé typy automatů, úvod do teorie složitosti.

Požadavky:

Osnova přednášek:

1. Konečné automaty a regulární jazyky.

2. Uzávěrové vlastnosti regulárních jazyků.

3. Rozhodování regularity jazyka.

4. Bezkontextové jazyky a zásobníkové automaty.

5. Turingovy stroje.

6. Matematické základy složitosti.

7. Výpočetní složitost algoritmů a problémů.

8. Třídy P a NP.

Osnova cvičení:

Cíle studia:

Studijní materiály:

Povinná literatura:

[1] P. Jančar: Úvod do teoretické informatiky. Skripta. Ediční středisko VŠB-TUO, 2007.

[2] J. Mareš: Jazyky, gramatiky a automaty. Skripta. Vydavatelství ČVUT, Praha 2004. (Část.)

[3] J. Mareš: Teorie vyčíslitelnosti. Skripta. Vydavatelství ČVUT, Praha 2008. (Část.)

Doporučená literatura:

[4] M. Sipser: Introduction to the Theory of Computation (3rd ed.), Cengage Learning, 2012.

[5] J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd ed.), Pearson 2013.

Poznámka:

Rozvrh na zimní semestr 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

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

• Aplikovaná informatika (povinný předmět programu)