FI:IA006 Automaty - Informace o předmětu
IA006 Vybrané kapitoly z teorie automatů
Fakulta informatikypodzim 2024
- Rozsah
- 2/1/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučováno kontaktně - Vyučující
- prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
Mgr. Juraj Major (cvičící)
prof. RNDr. Jan Strejček, Ph.D. (cvičící)
RNDr. Miriama Jánošová (pomocník)
RNDr. Martin Jonáš, Ph.D. (pomocník)
RNDr. David Klaška (pomocník) - Garance
- prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Mojmír Křetínský, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky - Rozvrh
- St 25. 9. až St 18. 12. St 10:00–11:50 A218
- Rozvrh seminárních/paralelních skupin:
- Předpoklady
- Znalost problematiky v rozsahu předmětu IB005 - Formální jazyky a automaty a IB107 - Vyčíslitelnost a složitost
- Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 256 stud.
Momentální stav registrace a zápisu: zapsáno: 10/256, pouze zareg.: 0/256, pouze zareg. s předností (mateřské obory): 0/256 - Mateřské obory/plány
- Analýza a zpracování obrazu (program FI, N-VIZ)
- Bioinformatika a systémová biologie (program FI, N-UIZD)
- 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)
- Diskrétní algoritmy a modely (program FI, N-TEI)
- 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)
- Information Security (program FI, N-PSKB_A)
- Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
- Počítačová grafika a vizualizace (program FI, N-VIZ)
- Počítačové sítě a komunikace (program FI, N-PSKB)
- Principy programovacích jazyků (program FI, N-TEI)
- Ří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)
- Software Systems Development Management (program FI, N-RSSS_A)
- Softwarové systémy (program FI, N-PSKB)
- Strojové učení a umělá inteligence (program FI, N-UIZD)
- 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
- Cílem je seznámit studenty s pokročilejšími partiemi teorie automatů, a to jak aplikacemi klasické teorie automatů a gramatik (metody syntaktické analýzy deterministických bezkontextových jazyků), problematikou použití automatů pro specifikaci procesů (bisimulační ekvivalence, vztah automatů a MSO logiky), tak i s automaty nad nekonečnými slovy a jejich použitím. Na konci tohoto kurzu bude student schopen předkládat odůvodněná rozhodnutí o modelech relevatních pro danou oblast a porozumět metodám a technikám jejich použití.
- Výstupy z učení
- Na konci tohoto kurzu bude student schopen demostrovat plné porozumění vybraných pokročilých partií z teorie automatů a předkládat odůvodněná rozhodnutí o modelech relevatních pro danou oblast a porozumět metodám a technikám jejich použití.
- Osnova
- Deterministické bezkontextové jazyky (DCFL) a jejich syntaktická analýza.
- LL(k) gramatiky a jazyky; vlastnosti a analyzátory.
- LR(k) gramatiky a jazyky; vlastnosti a analyzátory.
- Vztahy mezi LL, LR a DCFL. (Ne)rozhodnutelné problémy z oblasti DCFL.
- Nekonečně stavové přechodové systémy a nedeterminismus - modelováníé procesů, bisimulace, vybrané rozhodnutelné problémy se vztahem k verifikaci procesů.
- Konečné automaty a MSO logika (monadická logika 2. řádu)
- Automaty nad nekonečnými slovy: nekonečná slova, regulární (racionální) množiny nekonečných slov.
- Automaty: deterministické a nedeterministické Büchiho automaty, Mullerovy Rabinovy a Streetovy automaty. McNaughtonova věta. Vzájemné vztahy.
- Literatura
- CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
- KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
- Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
- Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
- SIPPU, Seppo a Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
- další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.
- Výukové metody
- přednášky, cvičení, samostudium. Volitelné domácí úlohy.
- Metody hodnocení
- Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou 25%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.
- Navazující předměty
- Informace učitele
- http://www.fi.muni.cz/usr/kretinsky/fja2.html
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2024/IA006