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

UIINK15 Teorie jazyků a automatů II

Rozsah

Přednáška 12 HOD/SEM. 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ě

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 otevřen studentům libovolného oboru.

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 dovoleno ukončit i mimo zkouškové období.

• Statistika zápisu (nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIINK15