UIAI219 Základy teoretické informatiky II

Filozoficko-přírodovědecká fakulta v Opavě
zima 2021
Rozsah
6/0/0. Přednáška 6 HOD/SEM. 7 kr. Ukončení: zk.
Vyučující
doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
Garance
doc. RNDr. Lucie Ciencialová, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
Probíraná témata vyžadují jisté předběžné znalosti, proto je třeba aby každý student předem absolvoval buď Teorii jazyků a automatů I, nebo Základy teoretické informatiky I.
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
Přecházíme ke složitějším teoretickým modelům struktur a postupů, tedy zásobníkovým automatům, Turingovým strojům a složitějším formám gramatik. Ke konci kurzu se studenti seznámí také s paralelními systémy včetně jejich praktického použití. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášky.
Osnova
  • Transformace bezkontextových gramatik.
    Kritéria bezkontextovosti.
    Zásobníkové automaty, varianty, typy akceptování.
    Uzávěrové vlastnosti bezkontextových jazyků.
    Deterministické bezkontextové jazyky.
    Gramatiky typu 0, Turingovy stroje.
    Gramatiky typu 1, Lineárně ohraničené automaty.
    Chomského hierarchie - souhrn.
Literatura
    doporučená literatura
  • MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000. info
  • GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. 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
  • WOOD, D. Theory of computation. New York: John Wiley & Sons, 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 je na webu zkoušejícího.
AktivityNáročnost [h]
Domácí příprava na výuku30
Konzultace9
Přednáška6
Příprava na zápočet20
Příprava na zkoušku20
Celkem85
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 2013, léto 2014, zima 2014, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2022.