FPF:UIN1005 Teorie jazyků a automatů I - Informace o předmětu

UIN1005 Teorie jazyků a automatů I

Rozsah

2/2/0. 4 kr. Ukončení: z.

Vyučující

prof. RNDr. Alice Kelemenová, CSc. (přednášející)
RNDr. Šárka Vavrečková, Ph.D. (přednášející)

Garance

RNDr. Šárka Vavrečková, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě

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)
• Aplikovaná matematika pro řešení krizových situací (program MU, B1102)
• Geometrie (program MU, M1101)
• Informatika a výpočetní technika (program FPF, B1801 Inf)
• Informatika a výpočetní technika (program FPF, M1801 Inf)
• Matematická analýza (program MU, M1101)
• Matematické metody v ekonomice (program MU, B1101)
• Obecná matematika (program MU, B1101)
• Učitelství informatiky pro střední školy (program FPF, M7504)
• Učitelství všeobecně vzdělávacích předmětů pro střední školy se specializací informatika (program FPF, M7504)

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é jazyky, jejich varianty a vlastnosti.
  Normální formy bezkontextových jazyků.
  Pumping lemma pro bezkontextové jazyky.

Literatura

povinná literatura
• VAVREČKOVÁ, Š. Prezentace (presentations). 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

Informace učitele

Aktivity	Náročnost [h]
Příprava na zápočet	12
Účast na výuce	12
Celkem	24

Další komentáře

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

• Statistika zápisu (léto 2011, nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/leto2011/UIN1005