FI:IB102 Automaty a gramatiky - Informace o předmětu
IB102 Automaty a gramatiky
Fakulta informatikypodzim 2007
- Rozsah
- 2/2. 4 kr. (plus ukončení). Ukončení: zk.
- Vyučující
- prof. RNDr. Jan Strejček, Ph.D. (přednášející)
RNDr. Tomáš Babiak, Ph.D. (cvičící)
RNDr. Nikola Beneš, Ph.D. (cvičící)
RNDr. Václav Brožek, Ph.D. (cvičící)
doc. Ing. RNDr. Barbora Bühnová, Ph.D. (cvičící)
doc. RNDr. Milan Češka, Ph.D. (cvičící)
RNDr. Vojtěch Forejt, Ph.D., LL.B. (Hons) (cvičící)
prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D. (cvičící)
Mgr. Jitka Kudrnáčová (cvičící)
RNDr. Jana Tůmová, Ph.D. (cvičící)
Mgr. Lucie Brožková (pomocník)
prof. RNDr. Ivana Černá, CSc. (pomocník)
RNDr. Jakub Chaloupka, Ph.D. (pomocník)
Mgr. Pavel Moravec (pomocník) - Garance
- prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Jan Strejček, Ph.D. - Rozvrh
- Po 10:00–11:50 D3, Po 10:00–11:50 D1
- Rozvrh seminárních/paralelních skupin:
IB102/02: St 12:00–13:50 B011, N. Beneš
IB102/03: St 14:00–15:50 B410, M. Češka
IB102/04: Čt 10:00–11:50 B410, V. Brožek
IB102/05: St 18:00–19:50 B410, N. Beneš
IB102/06: Po 12:00–13:50 B007, V. Forejt
IB102/07: Po 14:00–15:50 B007, V. Forejt
IB102/08: Út 12:00–13:50 B011, J. Křetínský
IB102/09: Po 12:00–13:50 B410, J. Kudrnáčová
IB102/10: St 10:00–11:50 B003, V. Brožek
IB102/11: St 12:00–13:50 C511, J. Strejček
IB102/12: Po 12:00–13:50 B003, J. Tůmová
IB102/13: Po 14:00–15:50 B003, J. Tůmová
IB102/14: Čt 14:00–15:50 B003, B. Bühnová
IB102/15: Čt 16:00–17:50 B003, B. Bühnová
IB102/16: St 16:00–17:50 B204, J. Strejček - Předpoklady
- ( MB101 Matematika I || MB005 Základy matematiky )&& ! IB005 FJA 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
- předmět má 23 mateřských oborů, zobrazit
- Cíle předmětu
- Cíl: Rozvinout schopnost abstrakce, seznámit s možnostmi konečné specifikace nekonečných objektů, zde konkrétně jazyků, a studovat vybrané základní výpočetní modely. Vytvořit předpoklady pro schopnosti vlastní fomulace abstrakcí a jejich porozumění.
- Osnova
- Motivace - problém specifikace (nekonečných, regulárních) jazyků; základní operace nad jazyky.
- Konečné automaty a regulární gramatiky; Pumping lemma, 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
- Principy činnosti unixových programů grep, egrep,..., nástroj lex či ekvivalent.
- 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, deterministická analýza.
- 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
- 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
- SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
- Metody hodnocení
- 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 bez pomocných materiálů. Podrobné informace na http://www.fi.muni.cz/~xstrejc/IB102/
- Informace učitele
- http://www.fi.muni.cz/~xstrejc/IB102/
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (podzim 2007, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2007/IB102