FPF:UIN1006 Teorie jazyků a automatů II - Informace o předmětu

UIN1006 Teorie jazyků a automatů II

Rozsah

2/2/0. 6 kr. Ukončení: zk.

Vyučující

doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (cvičící)
RNDr. Šárka Vavrečková, Ph.D. (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 15:35–17:10 B3b

• Rozvrh seminárních/paralelních skupin:

UIN1006/A: Čt 9:45–11:19 B3b, O. Mazurek

Předpoklady

TYP_STUDIA(B)
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

• Aplikovaná matematika (program MU, B1101)
• Aplikovaná matematika pro řešení krizových situací (program MU, B1101)
• Informatika a výpočetní technika (program FPF, B1801 Inf)
• Matematické metody v ekonomice (program MU, B1101)
• Obecná matematika (program MU, B1101)

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.

Aktivity	Náročnost [h]
Cvičení	20
Konzultace	5
Přednáška	20
Příprava na zápočet	20
Příprava na zkoušku	20
Celkem	85

Další komentáře

Studijní materiály
Předmět je dovoleno ukončit i mimo zkouškové období.

• Statistika zápisu (zima 2020, nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/zima2020/UIN1006