IB005 Formální jazyky a automaty
Fakulta informatikyjaro 2020
- Rozsah
- 4/2/0. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
- Vyučující
- prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
RNDr. David Klaška (cvičící)
Mgr. Juraj Major (cvičící)
prof. RNDr. Jan Strejček, Ph.D. (cvičící)
RNDr. Miriama Jánošová (pomocník)
Mgr. Michael Koudela (pomocník)
Mgr. Jakub Lédl (pomocník)
Mgr. Anna Řechtáčková (pomocník)
Mgr. Bc. Kateřina Sloupová (pomocník)
Mgr. Tereza Šťastná (pomocník)
RNDr. Vladimír Štill, Ph.D. (pomocník)
RNDr. Bc. Dominik Velan, Ph.D. (pomocník)
Mgr. Tatiana Zbončáková (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
- Po 17. 2. až Pá 15. 5. St 10:00–11:50 D2, Čt 10:00–11:50 D1
- Rozvrh seminárních/paralelních skupin:
IB005/02: Po 17. 2. až Pá 15. 5. Út 12:00–13:50 A318, J. Strejček
IB005/03: Po 17. 2. až Pá 15. 5. Út 12:00–13:50 A320, D. Klaška
IB005/04: Po 17. 2. až Pá 15. 5. St 14:00–15:50 A320, J. Major
IB005/05: Po 17. 2. až Pá 15. 5. Čt 14:00–15:50 A320, J. Major - Předpoklady
- IB000 Mat. základy informatiky && ! IB102 Automaty a gramatiky
Znalost problematiky v rozsahu předmětu IB000 Matematické základy informatiky - 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-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 veřejné správě (program FI, B-AP)
- 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é 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)
- 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
- Kurs by měl u studenta rozvinout schopnost abstrakce, seznámit ho s možnostmi konečné specifikace nekonečných objektů, zde konkrétně jazyků, a naučit se aktivně pracovat se základními abstraktn9mi výpočetními modely a vytvořit předpoklady pro schopnosti vlastní formulace abstrakcí a jejich porozumění.
- Výstupy z učení
- Na konci tohoto kurzu bude student schopen:
Prokázat hluboké porozumění konceptům a technikám teorie automatů a jejich vztah k výpočtům.
Navrhnout abstraktní stroje modelující reálné systémy a specifikovat chování těchto strojů. Analyzovat výpočetní sílu těchto strojů
Porozumět pojmu vyčíslitelnosti na úrovni různých typů automatů a demostrovat jejicvh vlastnosti
Aplikovat tuto teorii v běžné informatické praxi a při návrhu relevatních softwarových systémů. - Osnova
- Pojem jazyka a problém specifikace (nekonečných) jazyků; základní operace nad jazyky. Přepisovací systémy a gramatiky. Chomského hierarchie.
- Konečné automaty a regulární gramatiky; Pumping lemma, Myhillova--Nerodova věta, minimalizace. Nedeterministické konečné automaty, vztah k regulárním gramatikám.
- Vlastnosti regulárních jazyků; uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost. Nástin aplikací (grep, ..., lex).
- Bezkontextové gramatiky a jazyky; transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti; konečnost a regularita.
- Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám; nedeterministická syntaktická analýza shora dolů a zdola nahoru.
- Turingovy stroje (TS). Rekursivní a rekursivně vyčíslitelné jazyky a funkce, uzávěrové vlastnosti. Lineárně ohraničené automaty.
- Nerozhodnutelnost, problém zastavení TS, princip redukce, Postův korespondenční problém, nerozhodnutelné problémy z teorie jazyků.
- 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
- GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. 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
- 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
- SIPSER, Michael. Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 2006, xix, 431. ISBN 0534950973. info
- Výukové metody
- přednášky, cvičení, samostudium. Volitelné domácí úlohy.
- Metody hodnocení
- 1 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í s vahou 20%. Všechny písemky bez pomocných materiálů.
- Navazující předměty
- Informace učitele
- http://www.fi.muni.cz/usr/kretinsky/fja1.html
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně. - Nachází se v prerekvizitách jiných předmětů
- Statistika zápisu (jaro 2020, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2020/IB005