460-6003/02 – Teorie jazyků a automatů (TJA)

Garantující katedraKatedra informatikyKredity10
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětudoc. Ing. Zdeněk Sawa, Ph.D.
Úroveň studiapostgraduálníPovinnostpovinně volitelný
RočníkSemestrzimní + letní
Jazyk výukyangličtina
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studiadoktorské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
JAN59 prof. RNDr. Petr Jančar, CSc.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zkouška 28+0
kombinovaná Zkouška 28+0

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Student po úspěšném absolvování předmětu: - rozumí základním pojmům v oblasti teorie jazyků a automatů - umí volit vhodný formální jazyk k popisu praktických problémů a chápe možnosti i omezení různých tříd automatů v souvislosti s jejich řešením - prokáže schopnost samostatně zvládnout a odprezentovat pokročilou partii v dané oblasti (např. u verifikace programů)

Vyučovací metody

Přednášky
Individuální konzultace
Projekt

Anotace

Předmět nejdříve rekapituluje základní znalosti týkajici se konečných automatů, bezkontextových jazyků a Turingových strojů, se kterými se studenti seznámili v magisterském studiu. Klade se ovšem důraz na exaktní přístup a hlubší pochopení. Dále je kurs věnován pokročilejším partiím v těchto a dalších oblastech (např. vztahu jazyků, automatů a logiky, stromovým jazykům apod.).

Povinná literatura:

M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006

Doporučená literatura:

D. Kozen: Automata and Computability, Springer 1997 D. Kozen: Theory of Computation; Springer 2006 J.E.Hopcroft, R. Motwani, J.D.Ullman: Introduction to Automata Theory, Languages and Computation. Addison Wesley, 2001 H. Comon et al.: Tree Automata Techniques and Applications; http://tata.gforge.inria.fr/ (2007) Handbook of formal languages, Vol 1,2,3 (ed. G.Rozenberg) (Springer 1997) M.Demlová, V.Koubek: Algebraická teorie automatů. Matematický seminář SNTL, Praha, 1990 M.Chytil: Automaty a gramatiky. Matematický seminář SNTL, Praha, 1984

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Student sepíše stručný, ale výstižný a srozumitelný, článek o vybraném pokročilém tématu, které v rámci kurzu odprezentuje.

E-learning

Další požadavky na studenta

Žádné další požadavky na studenta nejsou kladeny.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Pojem formálního jazyka. Operace s jazyky. Regulární jazyky. Specifikace jazyků. Přepisovací systémy a gramatiky. Chomského klasifikace gramatik. Konečné automaty: deterministické, nedeterministické, zobecněné nedeterministické. Jazyky rozpoznávané konečnými automaty. Kleeneho věta. Automatové morfismy a minimalizace konečných automatů. Konečné automaty a regulární gramatiky. Bezkontextové gramatiky. Zásobníkové automaty. Jazyky generované bezkontextovými gramatikami a rozhodované zásobníkovými automaty. Kontextové jazyky generované kontextovými gramatikami a rozpoznávané lineárně omezenými automaty. Turingovy stroje. Jazyky rozpoznávané a rozhodované Turingovými stroji /rekurzivně spočetné a rekurzivní jazyky/. Postova věta. Algoritmická řešitelnost. Turingova /Churchova/ téze. Další partie teorie konečných automatů (dvoucestné automaty, automaty s váhami, ...) Další partie teorie bezkontextových jazyků (deterministické bezkontextové jazyky, ...) Stromové jazyky Vztah jazyků, automatů a logických teorií Další vybrané partie

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2015/2016 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Zkouška Zkouška   3
Rozsah povinné účasti:

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2023/2024 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2022/2023 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2022/2023 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.