Fakulta elektrotechnická

MOTTO: SCIENTIA EST POTENTIA

Vyhledávání

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+2s
Garant:Demlová M. Typ předmětu:P Zakončení:Z,ZK
Vyučující:Demlová M.
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.

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

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
BPOI2 Informatika a počítačové vědy (bakalářský) P 3
BPOI1 Počítačové systémy (bakalářský) P 3
BPOI_BO Před zařazením do oboru P 3
BPOI3 Softwarové systémy (bakalářský) P 3
BPKYR2 Senzory a přístrojová technika (bakalářský) V 3
BPKYR1 Robotika (bakalářský) V 3
BPKYR_BO Před zařazením do oboru V 3
BPKYR3 Systémy a řízení (bakalářský) V 3
BPKME3 Aplikovaná elektronika (bakalářský) V 3
BPKME2 Multimediální technika (bakalářský) V 3
BPKME5 Komunikace a elektronika V 3
BPKME1 Komunikační technika (bakalářský obor) V 3
BPKME_BO Před zařazením do oboru V 3
BPKME4 Síťové a informační technologie V 3
BPEEM_BO Před zařazením do oboru V 3
BPEEM2 Elektrotechnika a management (bakalářský) V 3
BPEEM1 Aplikovaná elektrotechnika (bakalářský) V 3
BPSTM_BO Před zařazením do oboru V 3
BPSTMSI Softwarové inženýrství V 3
BMI(ECTS) Manažerská informatika (bakalářský) V 3
BPSTMIS Inteligentní systémy (bakalářský) V 3
BPSTMWM Web a multimedia (bakalářský) V 3
BPSTMMI Manažerská informatika (bakalářský) V 3
BWM(ECTS) Web a multimedia (bakalářský) V 3
BIS(ECTS) Inteligentní systémy (bakalářský) V 3
BSI(ECTS) Softwarové inženýrství V 3

Stránka vytvořena 21. 5. 2013, semestry: L/2011-2, L/2012-3, L/2010-1, Z/2011-2, Z/2010-1, Z/2013-4, 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)