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í)
prof. RNDr. Alice Kelemenová, CSc. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (cvičící)
prof. RNDr. Alice Kelemenová, CSc. (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

každý lichý pátek 8:05–11:20 B4

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

UIN1006/A: Po 12:15–13:50 B4, 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 2019, nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/zima2019/UIN1006