Popis předmětu - A4B01JAG

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4B01JAG Jazyky,automaty a gramatiky Rozsah výuky:2+2
Garanti:Demlová M. Role:P,V Jazyk výuky:CS
Vyučující:Demlová M. Zakončení:Z,ZK
Zodpovědná katedra:13101 Kreditů:6 Semestr:Z

Anotace:

Základní pojmy teorie konečných automatů a gramatik: deterministické a nedeterministické konečné automaty, charakterizace třídy jazyků přijímaných konečným automatem a jejich popis regulárním výrazem. Gramatiky a jazyky generované danými gramatikami s důrazem na bezkontextové gramatiky. Vztah bezkontextových gramatik a zásobníkových automatů. Pojem Turingova stroje a seznámení studentů s tím, že existují algoritmicky nerozhodnutelné problémy.

Výsledek studentské ankety předmětu je zde: A4B01JAG

Osnovy přednášek:

1. Abeceda, slova nad abecedou, zřetězení slov, jazyk.
2. Deterministický konečný automat, stavový diagram.
3. Jazyk přijímaný konečným automatem, Nerodova věta.
4. Nedeterministické konečné automaty.
5. Ekvivalence deterministických a nedeterministických konečných automatů.
6. Regulární výrazy a regulární jazyky, Kleeneova věta.
7. Algoritmická složitost úloh souvisejících s regulárními jazyky
8. Gramatiky, regulární gramatiky a bezkontextové gramatiky,
bezkontextové jazyky.
9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
10. Vlastnosti bezkontextových gramatik, lemma o vkládání.
Uzavřenost třídy bezkontextových jazyků.
11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky.
12. Turingovy stroje.
13. Algoritmicky neřešitelné úlohy.
14. Rezerva.

Osnovy cvičení:

1. Abeceda, slova nad abecedou, zřetězení slov, jazyk.
2. Deterministický konečný automat, stavový diagram.
3. Jazyk přijímaný konečným automatem, Nerodova věta.
4. Nedeterministické konečné automaty.
5. Ekvivalence deterministických a nedeterministických konečných automatů.
6. Regulární výrazy a regulární jazyky, Kleeneova věta.
7. Algoritmická složitost úloh souvisejících s regulárními jazyky.
8. Gramatiky, regulární gramatiky a bezkontextové gramatiky,
bezkontextové jazyky.
9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
10. Vlastnosti bezkontextových gramatik, lemma o vkládání. Uzavřenost
třídy bezkontextových jazyků.
11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky,
algoritmus CYK.
12. Turingovy stroje.
13. Algoritmicky neřešitelné úlohy.

Literatura:

[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata
Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001

Požadavky:

Diskrétní matematika nebo Matematika pro informatiku. Podrobné informace: http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6s

Webová stránka:

http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html

Klíčová slova:

http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BPOI2 Informatika a počítačové vědy P 3
BPOI_BO Před zařazením do oboru P 3
BPOI1 Počítačové systémy P 3
BPOI3 Softwarové systémy P 3
BPKYR1 Robotika V 3
BPKYR_BO Před zařazením do oboru V 3
BPKYR3 Systémy a řízení V 3
BPKYR2 Senzory a přístrojová technika V 3
BPKME_BO Před zařazením do oboru V 3
BPKME5 Komunikace a elektronika V 3
BPKME4 Síťové a informační technologie V 3
BPKME3 Aplikovaná elektronika V 3
BPKME2 Multimediální technika V 3
BPKME1 Komunikační technika V 3
BPEEM1 Aplikovaná elektrotechnika V 3
BPEEM_BO Před zařazením do oboru V 3
BPEEM2 Elektrotechnika a management V 3
BPSTM_BO Před zařazením do oboru V 3
BKSIT Před zařazením do oboru V 3
BPSIT Před zařazením do oboru V 3
BPSTMWM Web a multimedia V 3
BPSTMMI Manažerská informatika V 3
BPSTMIS Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) V 3
BPSTMSI Softwarové inženýrství V 3
BMI(ECTS) Manažerská informatika V 3
BWM(ECTS) Web a multimedia V 3
BIS(ECTS) Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) V 3
BSI(ECTS) Softwarové inženýrství V 3

Stránka vytvořena 21.8.2018 10:53:11, semestry: Z,L/2020-1, L/2019-20, L/2018-9, Z,L/2017-8, Z/2018-9, Z/2019-20, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.