UIN1105 Teorie jazyků a automatů I

Filozoficko-přírodovědecká fakulta v Opavě
léto 2020
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
prof. RNDr. Alice Kelemenová, CSc. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (cvičící)
prof. RNDr. Alice Kelemenová, CSc. (cvičící)
Mgr. Ondřej Mazurek (cvičící)
Garance
doc. RNDr. Lucie Ciencialová, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Rozvrh
Út 16:25–18:00 B2
  • Rozvrh seminárních/paralelních skupin:
UIN1105/A: Čt 8:05–9:40 B4, O. Mazurek
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
V tomto kurzu se zabýváme především teoretickými základy metod požívaných pro modelování struktur a postupů, tedy konečnými automaty, regulárními jazyky, regulárními výrazy a bezkontextovými gramatikami. Na teoretický základ navazují také příklady využití v praxi. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášek.
Osnova
  • Abeceda, formální jazyky, operace s formálními jazyky.
    Konečný automat.
    Regulární jazyky, Pumping lemma pro regulární jazyky, regulární výrazy, regulární gramatiky.
    Uzávěrové vlastnosti regulárních jazyků.
    Chomského hierarchie jazyků.
    Bezkontextové gramatiky, jejich varianty a vlastnosti.
Literatura
    povinná literatura
  • Vavrečková, Šárka. WWW stránky předmětu, skripta. URL info
    doporučená literatura
  • GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. info
  • DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990. info
  • MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: Alfa, 1987. info
  • MEDUNA, A. MEDUNA, A. Gramatiky, automaty a kompilátory. Brno: VUT, 1987. info
  • HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987. info
  • CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. info
Výukové metody
Přednáška s aktivizací
Přednáška s diskusí
Přednáška s analýzou videozáznamu
Metody hodnocení
Písemná zkouška
Zkouška
Informace učitele
Teoretické a praktické zvládnutí témat předmětu.
Zápočet: dvě písemky, účast na cvičeních min. 75 %.
Zkouška: písemná a ústní část, seznam možných otázek na webu vyučujícího.
AktivityNáročnost [h]
Cvičení20
Přednáška20
Příprava na zápočet15
Příprava na zkoušku15
Celkem70
Další komentáře
Studijní materiály
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích léto 2012, léto 2013, léto 2014, léto 2015, léto 2016, léto 2017, léto 2018, léto 2019, léto 2021, léto 2022, léto 2023.