FI:IB102 Automaty a gramatiky - Informace o předmětu

IB102 Automaty a gramatiky

Předmět se v období podzim 2023 nevypisuje.

Rozsah

2/2/0. 3 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Jan Strejček, Ph.D. (přednášející)
Mgr. Pavel Čadek, DiS. (cvičící)
Mgr. Adam Fiedler (cvičící)
RNDr. Miriama Jánošová (cvičící)
Mgr. Jakub Lédl (cvičící)
Mgr. Juraj Major (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Bc. Kateřina Sloupová (cvičící)
Mgr. Tatiana Zbončáková (cvičící)
Mgr. Martina Cvinčeková (pomocník)
RNDr. David Klaška (pomocník)
Mgr. Anna Řechtáčková (pomocník)
Mgr. Tereza Šťastná (pomocník)
RNDr. Vladimír Štill, Ph.D. (pomocník)
RNDr. Bc. Dominik Velan, Ph.D. (pomocník)
Mgr. Martina Vitovská (pomocník)

Garance

prof. RNDr. Jan Strejček, Ph.D.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Jan Strejček, Ph.D.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Předpoklady

( IB000 Mat. základy informatiky || PřF:M1125 Základy matematiky )&&! IB005 FJA

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

• Analýza a zpracování obrazu (program FI, N-VIZ)
• Aplikovaná informatika (program FI, B-AP)
• Bioinformatika a systémová biologie (program FI, N-UIZD)
• Bioinformatika (program FI, B-AP)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Ekonomické informační systémy (program ESF, B-SI)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Informatika a druhý obor (program FI, B-EB)
• Informatika a druhý obor (program FI, B-FY)
• Informatika a druhý obor (program FI, B-GE)
• Informatika a druhý obor (program FI, B-GK)
• Informatika a druhý obor (program FI, B-CH)
• Informatika a druhý obor (program FI, B-IO)
• Informatika a druhý obor (program FI, B-MA)
• Informatika a druhý obor (program FI, B-TV)
• Informatika (program FI, B-INF) (2)
• Informatika ve vzdělávání (program FI, B-IVV) (2)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Matematická informatika (program FI, B-IN)
• Paralelní a distribuované systémy (program FI, B-IN)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačová grafika a zpracování obrazu (program FI, B-IN)
• Počítačová lingvistika (program FF, N-PLIN_) (3)
• Počítačové sítě a komunikace (program FI, B-IN)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Počítačové systémy a zpracování dat (program FI, B-IN)
• Principy programovacích jazyků (program FI, N-TEI)
• Programování a vývoj aplikací (program FI, B-PVA)
• Programovatelné technické struktury (program FI, B-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• Služby - výzkum, řízení a inovace (program FI, N-AP)
• Sociální informatika (program FI, B-AP)
• Software Systems Development Management (program FI, N-RSSS_A)
• Software Systems (program FI, N-PSKB_A)
• Softwarové systémy (program FI, N-PSKB)
• Strojové učení a umělá inteligence (program FI, N-UIZD)
• Učitel informatiky a správce sítě (program FI, N-UCI)
• Učitelství informatiky pro střední školy (program FI, N-UCI) (2)
• Učitelství výpočetní techniky pro střední školy (program FI, N-SS)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, B-IN)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

Cíle předmětu

Na konci tohoto kurzu bude student schopen: vysvětlit základy teorie formálních jazyků a automatů; použít tuto teorii v běžné informatické praxi;

Výstupy z učení

Na konci tohoto kurzu bude student schopen: vysvětlit základy teorie formálních jazyků a automatů; použít tuto teorii v běžné informatické praxi;

Osnova

• Motivace: konečná reprezentace nekonečných jazyků.
• Konečné automaty a regulární gramatiky: pumping lemma, Myhillova-Nerodova věta, minimalizace konečných automatů, nedeterministické konečné automaty.
• Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta.
• Bezkontextové gramatiky a jazyky: transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti.
• Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám: nedeterministická syntaktická analýza shora dolů a zdola nahoru.
• Deterministické zásobníkové automaty.
• Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky.

Literatura

doporučená literatura
• ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. URL info

neurčeno
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987, 188 s. info
• HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley Publishing Company, 1979, 418 s., ob. ISBN 0-201-02988-X. info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info

Výukové metody

přednášky a cvičení

Metody hodnocení

Nepovinné domácí úkoly. Písemná zkouška během semestru a závěrečná písemná zkouška. Výsledky vnitrosemestrální písemky se započítávají do výsledného hodnocení. Všechny písemky se píší bez pomocných materiálů.

Navazující předměty

• IA006 Vybrané kapitoly z teorie automatů

Další komentáře

Předmět již není vypisován.
Výuka probíhá každý týden.

• Statistika zápisu (podzim 2023, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2023/IB102