Popis předmětu - AD4B01JAG

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
AD4B01JAG Jazyky,automaty a gramatiky Rozsah výuky:14+6
Garanti:  Role:P,V Jazyk výuky:CS
Vyučující:  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

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

Plán Obor Role Dop. semestr
BKEEM1 Aplikovaná elektrotechnika V 3
BKEEM_BO Před zařazením do oboru V 3
BKEEM2 Elektrotechnika a management V 3
BKOI1 Počítačové systémy P 3
BKOI_BO Před zařazením do oboru P 3
BKOI3 Softwarové systémy P 3
BKOI2 Informatika a počítačové vědy P 3
BKKYR1 Robotika V 3
BKKYR_BO Před zařazením do oboru V 3
BKKYR3 Systémy a řízení V 3
BKKYR2 Senzory a přístrojová technika V 3
BKKME1 Komunikační technika V 3
BKKME_BO Před zařazením do oboru V 3
BKKME4 Síťové a informační technologie V 3
BKKME3 Aplikovaná elektronika V 3
BKKME2 Multimediální technika V 3
BIS(ECTS)-D Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) V 3
BKSTMWM Web a multimedia V 3
BKSTMSI Softwarové inženýrství V 3
BKSTMMI Manažerská informatika V 3
BKSTMIS Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013) V 3
BKSTM_BO Před zařazením do oboru V 3
BSI(ECTS)-D Softwarové inženýrství V 3
BWM(ECTS)-D Web a multimedia V 3
BMI(ECTS)-D Manažerská informatika V 3


Stránka vytvořena 11.11.2019 17:50:47, semestry: Z,L/2020-1, L/2018-9, Z,L/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.