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	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.

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
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
BPKYR1	Robotika	V	3
BPKME5	Komunikace a elektronika	V	3
BPKME4	Síťové a informační technologie	V	3
BPKME3	Aplikovaná elektronika	V	3
BPKME1	Komunikační technika	V	3
BPKME2	Multimediální technika	V	3
BPKME_BO	Před zařazením do oboru	V	3
BPEEM_BO	Před zařazením do oboru	V	3
BPEEM1	Aplikovaná elektrotechnika	V	3
BPEEM2	Elektrotechnika a management	V	3
BKSIT	Před zařazením do oboru	V	3
BPSTMMI	Manažerská informatika	V	3
BPSTMWM	Web a multimedia	V	3
BPSIT	Před zařazením do oboru	V	3
BPSTMSI	Softwarové inženýrství	V	3
BPSTM_BO	Před zařazením do oboru	V	3
BPSTMIS	Inteligentní systémy (bakalářský, dobíhající pro nástupní ročníky před 2013)	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
BMI(ECTS)	Manažerská informatika	V	3
BWM(ECTS)	Web a multimedia	V	3

---

Stránka vytvořena 23.6.2017 17:54:25, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, 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)