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

Jazyky, automaty a vyčíslitelnost

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
01JAVY Z,ZK 5 3+1 česky
Přednášející:
Petr Ambrož (gar.)
Cvičící:
Petr Ambrož (gar.)
Předmět zajišťuje:
katedra matematiky
Anotace:

Konečné automaty a regulární jazyky, bezkontextové jazyky a zásobníkové automaty, jazyky typu 0 a Turingovy stroje. Algoritmy a algoritmicky vyčíslitelné funkce. Rekurzívní funkce, rekurzívní a rekurzívně spočetné množiny. Algoritmicky neřešitelné problémy.

Požadavky:
Osnova přednášek:

1. Konečné autoamaty, regulární jazyky a operace, věty o vkládání (3 přednášky)

2. Kleenova věta (2 přednášky)

3. Determinizace a minimalizace (2 přednášky)

4. Bezkontextové gramatiky a jejich redukce (2 přednášky)

5. Zásobníkové automaty a bezkontextové jazyky (2 přednášky)

6. Věta o vkládání pro bezkontextové jazyky, uzavřenost BKJ vůči operacím (2 přednášky)

7. Turingův stroj, rekurzivní a rekurzivně spočetné jazyky, metody návrhu turingových strojů (2 přednášky)

8. Nerozhodnutelnost (1 přednáška)

9. Riceova věta, Postův korespondenční problém, nerozhodnutelné vlastnosti BKJ (2 přednášky)

Osnova cvičení:

1. Kontrukce konečných automatů, použití vět o vkládání

2. Normalizované a standardní automaty, regulární operace

3. Přechod automat->regulární výraz: MNY algoritmus, BMC algoritmus, Ardenovo lemma

4. Determinizace a minimalizace konečného automatu

5. Konstrukce zásobníkových automatů, přechod zásobníkový automat - bezkontexrtová gramatika a zpět

6. Konstrukce turingových strojů, redukce nerozhodnutelných problémů

Cíle studia:

Znalosti:

Klasické výsledky teorie formálních jazyků, generativních gramatik a rozeznávacích automatů. Teorie rekurze jakožto matematické precizace intuitivního pojmu algoritmu a používané finitní a konstruktivní metody.

Schopnosti:

Orientace se ve světě finitních popisů formálních jazyků, funkcí a množin a jejich využití v praxi.

Studijní materiály:

Povinná literatura:

[1] J. Mareš: Jazyky, gramatiky a automaty. Vydavatelství ČVUT, Praha 2004.

[2] J. Mareš: Teorie vyčíslitelnosti. Vydavatelství ČVUT, Praha 2008.

Doporučená literatura:

[1] J. Sakarovitch: Elements of Automata Theory, Cambridge University Press 2009.

[2] J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley 1979.

[3] 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 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 23. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet5358406.html