Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024

Úvod do teoretické informatiky

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
01UTEI ZK 3 2P+0C česky
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ů:
Platnost dat k 18. 5. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6346606.html