UIMOIBP009 Teorie jazyků a automatů II

Filozoficko-přírodovědecká fakulta v Opavě
zima 2024
Rozsah
2/2/0. 5 kr. Ukončení: zk.
Vyučující
doc. RNDr. Lucie Ciencialová, Ph.D. (přednášející)
RNDr. Radka Poláková, Ph.D. (cvičící)
Garance
doc. RNDr. Lucie Ciencialová, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Rozvrh
St 14:45–16:20 B4
  • Rozvrh seminárních/paralelních skupin:
UIMOIBP009/A: St 17:15–18:50 B2, R. Poláková
Předpoklady
Probíraná témata vyžadují jisté předběžné znalosti, proto je třeba aby sevkaždý student předem obeznámil s obsahem kurzu Teorie jazyků a automatů 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.
Výstupy z učení
Student bude po absolvování předmětu schopen: - definovat důležité pojmy teoretické informatiky - používat abstraktní výpočetní modely - aplikovat získané poznatky na konkrétních příkladech.
Osnova
  • 1.-2. Opakování – konečné automaty a regulární gramatiky. Kritéria regulárnosti jazyka.
  • 3.-4. Transformace bezkontextových gramatik. Kritéria bezkontextovosti.
  • 5.-7. Zásobníkové automaty, varianty, typy akceptování.
  • 8. Uzávěrové vlastnosti bezkontextových jazyků.
  • 9. Deterministické bezkontextové jazyky.
  • 10.-11. Gramatiky typu 0, Turingovy stroje.
  • 12. Gramatiky typu 1, Lineárně ohraničené automaty.
  • 13. Gramatiky a gramatické systémy neodpovídající Chomského hierarchii.
Výukové metody
Přednáška s aktivizací
Přednáška s diskusí
Cvičení
Metody hodnocení
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 vyučujícího.
Další komentáře
Studijní materiály
Předmět je zařazen také v obdobích zima 2020, zima 2021, zima 2022, zima 2023.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIMOIBP009