UIN1006 Teorie jazyků a automatů II

Filozoficko-přírodovědecká fakulta v Opavě
zima 2017
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
prof. RNDr. Alice Kelemenová, CSc. (přednášející)
RNDr. Šárka Vavrečková, Ph.D. (přednášející)
prof. RNDr. Alice Kelemenová, CSc. (cvičící)
Mgr. Lenka Resslerová (cvičící)
RNDr. Šárka Vavrečková, Ph.D. (cvičící)
Garance
prof. RNDr. Alice Kelemenová, CSc.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
UIAI012 Zákl. teoretické informatiky I || UIAI212 Základy teoretické informatiky || UIBUC56 Teorie jazyků a automatů I || UINK115 Teorie jazyků a automatů I || UIN1105 Teorie jazyků a automatů I
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]
Cvičení20
Konzultace5
Přednáška20
Příprava na zápočet20
Příprava na zkoušku20
Celkem85
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 1993, zima 1994, zima 1995, zima 1996, zima 1997, zima 1998, zima 1999, zima 2003, zima 2004, zima 2005, zima 2006, zima 2007, zima 2008, zima 2009, zima 2010, zima 2011, zima 2012, zima 2013, zima 2014, zima 2015, zima 2016, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022.