Informace o předmětu

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2019

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

Rozvrh

Po 10:00–11:50 D3, Po 10:00–11:50 D1, kromě Po 16. 12. ; a Po 16. 12. 10:00–11:50 D3

Rozvrh seminárních/paralelních skupin:

IB102/01: St 8:00–9:50 B204, P. Čadek
IB102/02: Čt 10:00–11:50 A320, A. Fiedler
IB102/03: Čt 16:00–17:50 C416, J. Lédl
IB102/04: St 16:00–17:50 A319, J. Major
IB102/05: Čt 12:00–13:50 A319, V. Řehák
IB102/06: Út 8:00–9:50 B410, M. Jánošová
IB102/07: Po 16:00–17:50 C525, K. Sloupová
IB102/08: Út 10:00–11:50 A217, J. Strejček
IB102/09: St 12:00–13:50 C525, T. Zbončáková
IB102/10: Čt 8:00–9:50 A319, T. Zbončáková
IB102/11: Po 12:00–13:50 B410, P. Čadek
IB102/12: Út 18:00–19:50 A319, M. Jánošová

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

předmět má 62 mateřských oborů, zobrazit

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Studijní materiály
Předmět je vyučován každoročně.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2018

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í)
Mgr. Martina Cvinčeková (cvičící)
Mgr. Pavel Čadek, DiS. (cvičící)
Mgr. Tadeáš Kučera (cvičící)
Mgr. Juraj Major (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
RNDr. Miriama Jánošová (cvičící)
Mgr. Bc. Kateřina Sloupová (cvičící)
Mgr. Martina Vitovská (cvičící)
Mgr. Tatiana Zbončáková (cvičící)
Mgr. Lukáš Másilko (cvičící)
Mgr. Ondřej Nečas (cvičící)
RNDr. Petra Budíková, Ph.D. (pomocník)
Mgr. Adam Fiedler (pomocník)
RNDr. Martin Jonáš, Ph.D. (pomocník)
RNDr. David Klaška (pomocník)
RNDr. Vladimír Štill, Ph.D. (pomocník)
RNDr. Bc. Dominik Velan, Ph.D. (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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Po 17. 9. až Po 10. 12. Po 10:00–11:50 D3, Po 10:00–11:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/01: Čt 16:00–17:50 C416, M. Cvinčeková
IB102/02: Út 18:00–19:50 C416, P. Čadek
IB102/03: Út 8:00–9:50 C525, T. Kučera
IB102/04: Po 17. 9. až Po 10. 12. Po 16:00–17:50 B410, J. Major
IB102/05: Po 17. 9. až Po 10. 12. Po 14:00–15:50 C525, V. Řehák
IB102/06: Pá 8:00–9:50 C511, V. Řehák
IB102/07: Čt 18:00–19:50 C416, M. Jánošová
IB102/08: Po 17. 9. až Po 10. 12. Po 12:00–13:50 B410, K. Sloupová
IB102/09: St 10:00–11:50 A319, J. Strejček
IB102/10: Čt 14:00–15:50 C511, M. Vitovská
IB102/11: Po 17. 9. až Po 10. 12. Po 18:00–19:50 C416, T. Zbončáková

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

předmět má 22 mateřských oborů, zobrazit

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2017

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. Marek Chalupa, Ph.D. (cvičící)
RNDr. Martin Jonáš, Ph.D. (cvičící)
RNDr. Henrich Lauko (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. Martina Vitovská (cvičící)
Mgr. Lukáš Másilko (cvičící)
Mgr. Ondřej Nečas (cvičící)
Mgr. Zuzana Baranová (pomocník)
RNDr. František Blahoudek, Ph.D. (pomocník)
RNDr. Petra Budíková, Ph.D. (pomocník)
RNDr. Miriama Jánošová (pomocník)
RNDr. David Klaška (pomocník)
Mgr. Tadeáš Kučera (pomocník)
Bc. Tomáš Lamser (pomocník)
Mgr. et Mgr. Dominika Lauko (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

Rozvrh

Po 10:00–11:50 D3, Po 10:00–11:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/01: Pá 8:00–9:50 C525, M. Chalupa
IB102/02: St 16:00–17:50 C511, M. Jonáš
IB102/03: Po 12:00–13:50 C511, M. Jonáš
IB102/04: St 14:00–15:50 C511, H. Lauko
IB102/05: Po 14:00–15:50 B410, J. Major
IB102/06: Čt 16:00–17:50 A318, kromě Čt 9. 11. ; a Čt 9. 11. 16:00–17:50 A319, V. Řehák
IB102/07: Čt 8:00–9:50 A319, V. Řehák
IB102/08: Čt 18:00–19:50 C525, K. Sloupová
IB102/09: Čt 14:00–15:50 B410, J. Strejček
IB102/10: St 10:00–11:50 B410, M. Vitovská
IB102/11: Út 18:00–19:50 B410, M. Vitovská

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

předmět má 22 mateřských oborů, zobrazit

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty, gramatiky a složitost

Fakulta informatiky
podzim 2016

Rozsah

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

Vyučující

prof. RNDr. Jan Strejček, Ph.D. (přednášející)
RNDr. František Blahoudek, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
RNDr. Martin Jonáš, Ph.D. (cvičící)
Mgr. Karel Kubíček (cvičící)
RNDr. Henrich Lauko (cvičící)
Mgr. Juraj Major (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Martina Vitovská (cvičící)
Mgr. Lukáš Másilko (cvičící)
Mgr. Ondřej Nečas (cvičící)
Mgr. Zuzana Baranová (pomocník)
Mgr. Bc. Tomáš Janík (pomocník)
RNDr. David Klaška (pomocník)
Mgr. Tadeáš Kučera (pomocník)
Bc. Tomáš Lamser (pomocník)
Mgr. Bc. Kateřina Sloupová (pomocník)
RNDr. Vladimír Štill, Ph.D. (pomocník)
Mgr. Eva Tesařová (pomocník)
RNDr. Bc. Dominik Velan, Ph.D. (pomocník)

Garance

Rozvrh

Po 9:00–11:50 D1, Po 9:00–11:50 D3

Rozvrh seminárních/paralelních skupin:

IB102/T01: Po 19. 9. až Čt 22. 12. Po 13:00–15:30 KOM 106, Út 20. 9. až Čt 22. 12. Út 13:00–14:35 KOM 110, L. Másilko, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB102/T02: Po 19. 9. až Čt 22. 12. Po 13:00–15:30 KOM 114, O. Nečas, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB102/01: Pá 8:00–9:50 B410, F. Blahoudek
IB102/02: Čt 8:00–9:50 C525, F. Blahoudek
IB102/03: St 8:00–9:50 B410, P. Budíková
IB102/04: Čt 16:00–17:50 B204, M. Jonáš
IB102/05: St 16:00–17:50 C525, M. Jonáš
IB102/06: Po 16:00–17:50 C525, K. Kubíček, M. Vitovská
IB102/07: Po 18:00–19:50 A319, K. Kubíček
IB102/08: Út 10:00–11:50 C511, H. Lauko
IB102/09: Út 14:00–15:50 C525, J. Major
IB102/10: Čt 14:00–15:50 A217, V. Řehák
IB102/11: Čt 12:00–13:50 A217, V. Řehák
IB102/12: St 10:00–11:50 C525, J. Strejček

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

předmět má 22 mateřských oborů, zobrazit

Cíle předmětu

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

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, 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.
Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky, rozhodnutelnost problémů, redukce.
Výpočetní složitost algoritmů a problémů.
Složitostní třídy: polynomiální redukce, úplnost a težkost problémů, NP-úplné problémy.

Literatura

doporučená literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

neurčeno

MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty, gramatiky a složitost

Fakulta informatiky
podzim 2015

Rozsah

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

Vyučující

prof. RNDr. Jan Strejček, Ph.D. (přednášející)
RNDr. František Blahoudek, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
RNDr. Martin Jonáš, Ph.D. (cvičící)
Mgr. Karel Kubíček (cvičící)
RNDr. Henrich Lauko (cvičící)
Mgr. Juraj Major (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Eva Tesařová (cvičící)
Mgr. Martina Vitovská (cvičící)
Mgr. Zuzana Dankovčíková (pomocník)
Mgr. Bc. Tomáš Janík (pomocník)
Mgr. Lukáš Másilko (pomocník)
RNDr. Vladimír Štill, Ph.D. (pomocník)

Garance

Rozvrh

Po 9:00–11:50 D3, Po 9:00–11:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/T01: Po 13:40–16:10 KOM 116, St 23. 9. až Út 22. 12. St 9:40–11:15 KOM 116, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB102/01: Po 12:00–13:50 A319, F. Blahoudek
IB102/02: Út 12:00–13:50 A218, F. Blahoudek
IB102/03: Út 8:00–9:50 A319, P. Budíková
IB102/04: St 18:00–19:50 C525, M. Jonáš
IB102/05: St 16:00–17:50 C525, M. Jonáš
IB102/06: Út 18:00–19:50 A218, K. Kubíček, M. Vitovská
IB102/07: Čt 18:00–19:50 C525, H. Lauko
IB102/08: Čt 14:00–15:50 B410, J. Major
IB102/09: Čt 12:00–13:50 B204, V. Řehák
IB102/10: Čt 8:00–9:50 A320, V. Řehák
IB102/11: St 14:00–15:50 A218, J. Strejček
IB102/12: Po 16:00–17:50 A218, E. Tesařová
IB102/13: Čt 16:00–17:50 C511, E. Tesařová

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

předmět má 22 mateřských oborů, zobrazit

Cíle předmětu

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

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, 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.
Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky, rozhodnutelnost problémů, redukce.
Výpočetní složitost algoritmů a problémů.
Složitostní třídy: polynomiální redukce, úplnost a težkost problémů, NP-úplné problémy.

Literatura

doporučená literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

neurčeno

MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty, gramatiky a složitost

Fakulta informatiky
podzim 2014

Rozsah

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

Vyučující

prof. RNDr. Jan Strejček, Ph.D. (přednášející)
RNDr. František Blahoudek, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
RNDr. Martin Jonáš, Ph.D. (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
RNDr. Mária Svoreňová, Ph.D. (cvičící)
RNDr. Vladimír Štill, Ph.D. (cvičící)
Mgr. Eva Tesařová (cvičící)
Mgr. Pavel Čadek, DiS. (pomocník)
Mgr. Zuzana Dankovčíková (pomocník)
Mgr. Bc. Tomáš Janík (pomocník)
Mgr. Karel Kubíček (pomocník)
RNDr. Henrich Lauko (pomocník)
Mgr. Juraj Major (pomocník)
Mgr. Karolína Malá (pomocník)
Mgr. Lukáš Másilko (pomocník)
doc. RNDr. Petr Novotný, Ph.D. (pomocník)
Mgr. Jiří Uhlíř (pomocník)

Garance

Rozvrh

Po 9:00–11:50 D3, Po 9:00–11:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/T01: Po 15. 9. až Pá 19. 12. Po 9:40–11:15 Učebna S5 (31), Út 16. 9. až Pá 19. 12. Út 12:40–14:15 Učebna S4 (35a), T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB102/01: St 8:00–9:50 C525, F. Blahoudek
IB102/02: Po 14:00–15:50 C525, F. Blahoudek
IB102/03: Čt 8:00–9:50 C525, P. Budíková
IB102/04: Čt 10:00–11:50 C525, P. Budíková
IB102/05: Po 12:00–13:50 C525, M. Jonáš
IB102/06: Čt 16:00–17:50 C511, M. Jonáš
IB102/07: Út 16:00–17:50 A319, V. Řehák
IB102/08: Pá 8:00–9:50 A218, V. Řehák
IB102/09: Pá 10:00–11:50 A218, V. Řehák
IB102/10: Út 10:00–11:50 A319, J. Strejček
IB102/11: Po 18:00–19:50 A218, M. Svoreňová
IB102/12: Po 16:00–17:50 A218, M. Svoreňová
IB102/13: Út 18:00–19:50 B410, E. Tesařová
IB102/14: Út 12:00–13:50 A319, V. Štill
IB102/15: St 18:00–19:50 C525, V. Štill

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

předmět má 22 mateřských oborů, zobrazit

Cíle předmětu

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

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, 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.
Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky, rozhodnutelnost problémů, redukce.
Výpočetní složitost algoritmů a problémů.
Složitostní třídy: polynomiální redukce, úplnost a težkost problémů, NP-úplné problémy.

Literatura

doporučená literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

neurčeno

MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty, gramatiky a složitost

Fakulta informatiky
podzim 2013

Rozsah

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

Vyučující

prof. RNDr. Jan Strejček, Ph.D. (přednášející)
RNDr. František Blahoudek, Ph.D. (cvičící)
doc. RNDr. Tomáš Brázdil, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
Mgr. Pavel Čadek, DiS. (cvičící)
Mgr. Karolína Malá (cvičící)
Mgr. Miroslav Klimoš (cvičící)
Mgr. Zuzana Petruchová (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
RNDr. Vladimír Štill, Ph.D. (cvičící)
Mgr. Bc. Tomáš Janík (cvičící)
Mgr. Jan Fikejs (pomocník)
RNDr. Martin Jonáš, Ph.D. (pomocník)
Mgr. Lukáš Másilko (pomocník)
doc. RNDr. Petr Novotný, Ph.D. (pomocník)
Mgr. Eva Tesařová (pomocník)
Mgr. Jiří Uhlíř (pomocník)
RNDr. Martin Ukrop, Ph.D. (pomocník)

Garance

Rozvrh

Po 9:00–11:50 D3, Po 9:00–11:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/A: St 14:00–15:50 B411, J. Strejček
IB102/T01: Út 17. 9. až Pá 20. 12. Út 14:00–15:55 Učebna S9 (55), St 18. 9. až Pá 20. 12. St 15:00–17:55 Učebna S9 (55), J. Fikejs, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB102/T02: St 18. 9. až Pá 20. 12. St 10:00–12:55 Učebna S1 (36a), K. Malá, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB102/01: St 8:00–9:50 G330, F. Blahoudek
IB102/02: St 10:00–11:50 G126, F. Blahoudek
IB102/03: Čt 8:00–9:50 G330, T. Brázdil
IB102/04: Po 16:00–17:50 G123, T. Brázdil
IB102/05: Čt 14:00–15:50 G331, P. Budíková
IB102/06: Pá 8:00–9:50 G330, V. Řehák
IB102/07: Út 18:00–19:50 G330, P. Čadek
IB102/08: Čt 16:00–17:50 G331, M. Klimoš
IB102/09: St 14:00–15:50 G123, M. Klimoš
IB102/10: St 18:00–19:50 G330, P. Čadek
IB102/11: Út 8:00–9:50 G331, Z. Petruchová
IB102/12: St 16:00–17:50 G330, K. Malá
IB102/13: Pá 10:00–11:50 G123, V. Řehák
IB102/14: Út 16:00–17:50 G123, V. Štill
IB102/15: St 16:00–17:50 G331, V. Štill

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

předmět má 22 mateřských oborů, zobrazit

Cíle předmětu

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

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, Myhill-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.
Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky.
Výpočetní složitost algoritmů a problémů.
Složitostní třídy: polynomiální redukce, úplnost a težkost problémů, NP-úplné problémy.

Literatura

doporučená literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2012

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. František Blahoudek, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
Mgr. Pavel Čadek, DiS. (cvičící)
Mgr. Ľuboš Korenčiak, Ph.D. (cvičící)
Mgr. Petr Kunc (cvičící)
Mgr. Zuzana Petruchová (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Marek Trtík, Ph.D. (cvičící)
RNDr. Jana Tůmová, Ph.D. (cvičící)
Mgr. Jiří Uhlíř (cvičící)
RNDr. Nikola Beneš, Ph.D. (pomocník)
doc. RNDr. Milan Češka, Ph.D. (pomocník)
Mgr. Lukáš Ďurovský (pomocník)
Mgr. Jan Fikejs (pomocník)
Mgr. Lukáš Másilko (pomocník)
RNDr. Ondrej Moriš (pomocník)
doc. RNDr. Petr Novotný, Ph.D. (pomocník)
Mgr. et Mgr. Tomáš Sklenák (pomocník)
RNDr. Mária Svoreňová, Ph.D. (pomocník)
RNDr. Vladimír Štill, Ph.D. (pomocník)

Garance

Rozvrh

Po 10:00–11:50 D3, Po 10:00–11:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/A: Po 14:00–15:50 B411, J. Strejček
IB102/T01A: Čt 20. 9. až Pá 21. 12. Čt 8:00–9:55 Učebna S11 (58), L. Másilko
IB102/T01AA: Po 8:00–10:55 Učebna S11 (58), L. Másilko
IB102/01: Út 12:00–13:50 B410, F. Blahoudek
IB102/02: Čt 8:00–9:50 C511, F. Blahoudek
IB102/03: St 14:00–15:50 C511, P. Budíková
IB102/04: St 16:00–17:50 C511, P. Budíková
IB102/05: Út 14:00–15:50 G123, P. Čadek
IB102/06: Po 16:00–17:50 G125, Ľ. Korenčiak
IB102/07: Po 18:00–19:50 G125, Ľ. Korenčiak
IB102/08: Čt 18:00–19:50 C511, P. Kunc
IB102/09: Po 12:00–13:50 G126, Z. Petruchová
IB102/10: Út 10:00–11:50 G126, V. Řehák
IB102/11: St 12:00–13:50 B410, J. Strejček
IB102/12: Po 12:00–13:50 B410, J. Tůmová
IB102/13: Pá 12:00–13:50 C511, J. Uhlíř
IB102/14: Pá 14:00–15:50 C511, J. Uhlíř
IB102/15: Út 18:00–19:50 G124, M. Trtík

Předpoklady

( MB101 Lineární modely || IB112 Matematické základy || PřF:M1125 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á 22 mateřských oborů, zobrazit

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;

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, Myhill-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.

Literatura

doporučená literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2011

Rozsah

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

Vyučující

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 D1, Po 10:00–11:50 D3

Rozvrh seminárních/paralelních skupin:

IB102/A: Čt 10:00–11:50 B204, J. Strejček
IB102/01: St 10:00–11:50 B410, F. Blahoudek
IB102/02: St 12:00–13:50 B204, F. Blahoudek
IB102/03: Čt 8:00–9:50 C511, J. Bouda
IB102/04: Čt 10:00–11:50 C511, J. Bouda
IB102/05: Čt 8:00–9:50 B204, P. Budíková
IB102/06: Po 12:00–13:50 B410, M. Češka
IB102/07: Čt 12:00–13:50 G101, J. Krčál
IB102/08: Čt 14:00–15:50 G101, J. Krčál
IB102/09: Út 18:00–19:50 B410, P. Kunc
IB102/10: Út 8:00–9:50 G101, P. Novotný
IB102/11: Út 10:00–11:50 G101, P. Novotný
IB102/12: Po 18:00–19:50 G125, M. Svoreňová
IB102/13: Čt 16:00–17:50 B204, J. Tůmová
IB102/14: Pá 12:00–13:50 C511, J. Tůmová
IB102/15: Po 14:00–15:50 B410, 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á 28 mateřských oborů, zobrazit

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;

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, Nerodova věta, minimalizace, nedeterministické konečné automaty.
Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost.
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.

Literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2010

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í)
Mgr. Jiří Appl (cvičící)
RNDr. Tomáš Babiak, Ph.D. (cvičící)
RNDr. František Blahoudek, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
doc. RNDr. Milan Češka, Ph.D. (cvičící)
doc. RNDr. Petr Novotný, Ph.D. (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
RNDr. Mária Svoreňová, Ph.D. (cvičící)
RNDr. Jana Tůmová, Ph.D. (cvičící)
RNDr. Nikola Beneš, Ph.D. (pomocník)
RNDr. Jakub Chaloupka, Ph.D. (pomocník)
Bc. Tomáš Janoušek (pomocník)
Mgr. Petr Kunc (pomocník)
Mgr. Lukáš Másilko (pomocník)
Mgr. Filip Štefaňák (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/A: Po 14:00–15:50 B410, J. Strejček
IB102/01: Út 8:00–9:50 B011, J. Appl
IB102/02: Út 18:00–19:50 B410, T. Babiak
IB102/03: St 8:00–9:50 B410, T. Babiak
IB102/04: Út 14:00–15:50 B204, F. Blahoudek
IB102/05: Pá 14:00–15:50 C511, F. Blahoudek
IB102/06: Pá 10:00–11:50 B011, P. Budíková
IB102/07: Pá 12:00–13:50 B011, P. Budíková
IB102/08: Út 12:00–13:50 B011, M. Češka
IB102/09: Po 16:00–17:50 B410, M. Češka
IB102/10: Po 12:00–13:50 B011, P. Novotný
IB102/11: Út 8:00–9:50 B204, P. Novotný
IB102/12: St 12:00–13:50 C511, V. Řehák
IB102/13: Út 14:00–15:50 B011, M. Svoreňová
IB102/14: Čt 18:00–19:50 C525, J. Tůmová
IB102/15: Čt 14:00–15:50 B011, 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á 26 mateřských oborů, zobrazit

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;

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, Nerodova věta, minimalizace, nedeterministické konečné automaty.
Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost.
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.

Literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2009

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. František Blahoudek, Ph.D. (cvičící)
doc. Ing. RNDr. Barbora Bühnová, Ph.D. (cvičící)
doc. RNDr. Milan Češka, Ph.D. (cvičící)
RNDr. Petra Budíková, Ph.D. (cvičící)
doc. RNDr. Petr Novotný, Ph.D. (cvičící)
Mgr. Filip Štefaňák (cvičící)
Mgr. et Mgr. Miroslav Cupák (pomocník)
Mgr. Martin Milata (pomocník)
RNDr. Jakub Chaloupka, Ph.D. (pomocník)
Mgr. Helena Hlaváčová (pomocník)
RNDr. Mária Svoreňová, Ph.D. (pomocník)
Mgr. Lukáš Másilko (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 D1, Po 10:00–11:50 D3

Rozvrh seminárních/paralelních skupin:

IB102/A: Po 16:00–17:50 B007, J. Strejček
IB102/01: Po 12:00–13:50 B204, T. Babiak
IB102/02: Po 18:00–19:50 B011, T. Babiak
IB102/03: Čt 16:00–17:50 B011, N. Beneš
IB102/04: Čt 18:00–19:50 B011, N. Beneš
IB102/05: Út 8:00–9:50 B204, F. Blahoudek
IB102/06: Út 10:00–11:50 B204, F. Blahoudek
IB102/07: St 12:00–13:50 B011, M. Češka
IB102/08: St 14:00–15:50 B011, M. Češka
IB102/09: St 10:00–11:50 B003, P. Budíková
IB102/10: St 12:00–13:50 B003, P. Budíková
IB102/11: Pá 12:00–13:50 C511, P. Novotný
IB102/12: Čt 8:00–9:50 B011, F. Štefaňák
IB102/13: Po 14:00–15:50 B410, B. Bühnová
IB102/14: Po 16:00–17:50 B410, B. Bühnová
IB102/15: Po 14:00–15:50 B007, 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á 26 mateřských oborů, zobrazit

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;

Osnova

Motivace: problém specifikace (nekonečných, regulárních) jazyků.
Konečné automaty a regulární gramatiky: Pumping lemma, Nerodova věta, minimalizace, nedeterministické konečné automaty.
Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost.
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.

Literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

Výukové metody

přednášky a cvičení

Metody hodnocení

Navazující předměty

IA006 Vybrané kapitoly z teorie automatů

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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2008

Rozsah

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

Vyučující

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 D1, Po 10:00–11:50 D3

Rozvrh seminárních/paralelních skupin:

IB102/01: Út 16:00–17:50 B011, T. Babiak
IB102/02: Út 18:00–19:50 A107, T. Babiak
IB102/03: Po 12:00–13:50 B003, F. Blahoudek
IB102/04: Čt 8:00–9:50 B204, V. Brožek
IB102/05: Po 16:00–17:50 B204, M. Češka
IB102/06: Po 18:00–19:50 B204, M. Češka
IB102/07: Po 14:00–15:50 B011, T. Janoušek
IB102/08: Út 8:00–9:50 C511, P. Budíková
IB102/09: Pá 8:00–9:50 B410, P. Novotný
IB102/10: Čt 8:00–9:50 B011, P. Ročkai
IB102/11: St 14:00–15:50 B011, J. Strejček
IB102/12: Čt 12:00–13:50 B204, J. Strejček
IB102/13: Út 16:00–17:50 B003, M. Svoreňová
IB102/14: Pá 12:00–13:50 B011, M. Šmérek
IB102/15: St 12:00–13:50 B003, J. Tůmová
IB102/16: St 18:00–19:50 B410, J. Tůmová

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á 24 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ů.
Konečné automaty a regulární gramatiky: Pumping lemma, Nerodova věta, minimalizace, nedeterministické konečné automaty.
Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost.
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.

Literatura

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

Metody hodnocení

Přednášky a cvičení. 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 bez pomocných materiálů.

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ě.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 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/01: Po 14:00–15:50 B410, T. Babiak
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

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] 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ě.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2006

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í)
doc. RNDr. Jan Bouda, 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í)
RNDr. Jakub Chaloupka, Ph.D. (cvičící)
Mgr. Jitka Kudrnáčová (cvičící)
Mgr. Pavel Moravec (cvičící)
RNDr. Pavel Šimeček, Ph.D. (cvičící)
Mgr. Jiří Šimša (cvičící)
RNDr. Jana Tůmová, Ph.D. (cvičící)
prof. RNDr. Jiří Barnat, Ph.D. (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/sp: St 14:00–15:50 C416, Čt 8:00–9:50 C511
IB102/01: Pá 10:00–11:50 B410, T. Babiak
IB102/02: Út 16:00–17:50 B007, N. Beneš
IB102/03: Út 18:00–19:50 B007, N. Beneš
IB102/04: St 10:00–11:50 B410, V. Brožek
IB102/05: Čt 18:00–19:50 B011, M. Češka
IB102/06: Út 12:00–13:50 B011, V. Forejt
IB102/07: Čt 10:00–11:50 B410, J. Chaloupka
IB102/08: Čt 18:00–19:50 B410, J. Kudrnáčová
IB102/09: Po 18:00–19:50 B007, P. Moravec
IB102/10: Út 16:00–17:50 B011, J. Strejček
IB102/11: Pá 8:00–9:50 B007, P. Šimeček
IB102/12: Čt 12:00–13:50 C511, J. Bouda
IB102/13: St 12:00–13:50 B003, J. Šimša
IB102/14: Čt 16:00–17:50 B011, J. Tůmová
IB102/15: Po 16:00–17:50 B204, B. Bühnová
IB102/16: Po 12:00–13:50 B410, P. Moravec

Předpoklady

! I005 FJA I &&! I505 FJA I &&( MB101 Matematika I || MB005 Základy matematiky || M005 Základy matematiky )&& ! IB005 FJA I

Omezení zápisu do předmětu

Předmět je určen pouze studentům mateřských oborů.

Mateřské obory/plány

předmět má 14 mateřských oborů, zobrazit

Cíle předmětu

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: shora -- LL(1) gramatiky, zdola -- nástroj yacc či ekvivalent; (případové studie gramatik Java, C, ...).

Literatura

I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
SIPSER, Michael. Introduction to the theory of computation. Online. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. [citováno 2024-04-23] info

Metody hodnocení

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ě.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2005

Rozsah

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

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
doc. RNDr. Vojtěch Řehák, Ph.D. (přednášející)
prof. RNDr. Jiří Barnat, Ph.D. (cvičící)
RNDr. Nikola Beneš, Ph.D. (cvičící)
RNDr. Peter Bezděk, Ph.D. (cvičící)
doc. Ing. RNDr. Barbora Bühnová, Ph.D. (cvičící), prof. RNDr. Jan Strejček, Ph.D. (zástupce)
RNDr. Jakub Chaloupka, Ph.D. (cvičící)
Mgr. et Mgr. Pavlína Moravcová Vařeková (cvičící)
Mgr. Pavel Moravec (cvičící)
Mgr. Jiří Šimša (cvičící)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.

Rozvrh

Po 8:00–9:50 D3, Po 8:00–9:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/01: Čt 8:00–9:50 B011, J. Chaloupka
IB102/02: Čt 10:00–11:50 B011, J. Barnat
IB102/03: Čt 14:00–15:50 B011, J. Barnat
IB102/04: Út 12:00–13:50 B011, V. Řehák
IB102/05: St 14:00–15:50 B011, B. Bühnová
IB102/06: St 16:00–17:50 B011, B. Bühnová
IB102/07: St 10:00–11:50 B011, J. Chaloupka
IB102/08: St 12:00–13:50 B011, P. Moravcová Vařeková
IB102/09: Čt 16:00–17:50 B011, N. Beneš
IB102/10: Čt 18:00–19:50 B011, N. Beneš
IB102/11: Po 12:00–13:50 B011, P. Bezděk

Předpoklady

! I005 FJA I &&! I505 FJA I &&( MB101 Matematika I || MB005 Základy matematiky || M005 Základy matematiky )&& ! IB005 FJA I

Omezení zápisu do předmětu

Předmět je určen pouze studentům mateřských oborů.

Mateřské obory/plány

předmět má 13 mateřských oborů, zobrazit

Cíle předmětu

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: shora -- LL(1) gramatiky, zdola -- nástroj yacc či ekvivalent; (případové studie gramatik Java, C, ...).

Literatura

I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
GRUSKA, Jozef. Foundations of computing. Online. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info

Metody hodnocení

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

Informace učitele

http://www.fi.muni.cz/usr/cerna/AaG/ib102.html

Další komentáře

Předmět je vyučován každoročně.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2004

Rozsah

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

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
prof. RNDr. Jiří Barnat, Ph.D. (cvičící)
RNDr. Nikola Beneš, Ph.D. (cvičící)
doc. Ing. RNDr. Barbora Bühnová, Ph.D. (cvičící)
Mgr. Jan Holeček (cvičící)
RNDr. Jakub Chaloupka, Ph.D. (cvičící)
Mgr. Pavel Moravec (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Oldřich Stražovský (cvičící)
RNDr. Pavel Šimeček, Ph.D. (cvičící)
Mgr. Jiří Šimša (cvičící)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.

Rozvrh

Út 12:00–13:50 D3, Út 12:00–13:50 D1

Rozvrh seminárních/paralelních skupin:

IB102/01: Čt 10:00–11:50 B410, J. Barnat
IB102/02: Čt 8:00–9:50 B011, V. Řehák
IB102/03: Čt 10:00–11:50 B011, V. Řehák
IB102/04: St 12:00–13:50 B011, P. Moravec
IB102/05: Čt 8:00–9:50 C525, P. Moravec
IB102/06: Čt 14:00–15:50 B204, B. Bühnová
IB102/07: Čt 16:00–17:50 B204, B. Bühnová
IB102/08: Pá 8:00–9:50 B204, J. Chaloupka
IB102/09: Čt 12:00–13:50 B011, O. Stražovský
IB102/10: St 16:00–17:50 B011, J. Holeček
IB102/11: Pá 12:00–13:50 B204, N. Beneš

Předpoklady

! I005 FJA I &&! I505 FJA I &&( MB101 Matematika I || MB005 Základy matematiky || M005 Základy matematiky )&& ! IB005 FJA I

Omezení zápisu do předmětu

Předmět je určen pouze studentům mateřských oborů.

Mateřské obory/plány

předmět má 13 mateřských oborů, zobrazit

Cíle předmětu

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: shora -- LL(1) gramatiky, zdola -- nástroj yacc či ekvivalent; (případové studie gramatik Java, C, ...).

Literatura

I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
GRUSKA, Jozef. Foundations of computing. Online. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info

Metody hodnocení

Informace učitele

http://www.fi.muni.cz/usr/cerna/AaG/ib102.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ů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2003, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2003

Rozsah

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

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
prof. RNDr. Jiří Barnat, Ph.D. (cvičící)
doc. RNDr. Tomáš Brázdil, Ph.D. (cvičící)
Mgr. Jan Holeček (cvičící)
Mgr. Pavel Moravec (cvičící)
Roman Rožník (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Oldřich Stražovský (cvičící)
RNDr. Pavel Šimeček, Ph.D. (cvičící)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.

Rozvrh

Po 12:00–13:50 TA (Aula Technická)

Rozvrh seminárních/paralelních skupin:

IB102/01: Út 16:00–17:50 B204, J. Barnat
IB102/02: St 14:00–15:50 B011, P. Moravec
IB102/03: St 16:00–17:50 B011, J. Holeček
IB102/04: Po 14:00–15:50 B204, V. Řehák
IB102/05: Po 16:00–17:50 B204, V. Řehák
IB102/06: Čt 8:00–9:50 B003, P. Moravec
IB102/07: Čt 14:00–15:50 B003, T. Brázdil
IB102/08: St 8:00–9:50 B011, R. Rožník
IB102/09: St 10:00–11:50 B011, R. Rožník
IB102/10: Čt 14:00–15:50 B204, O. Stražovský
IB102/11: Pá 8:00–9:50 B204, P. Šimeček

Předpoklady

! I005 FJA I &&! I505 FJA I &&( MB101 Matematika I || MB005 Základy matematiky || M005 Základy matematiky )&& ! IB005 FJA I

Omezení zápisu do předmětu

Předmět je určen pouze studentům mateřských oborů.

Mateřské obory/plány

Aplikovaná informatika (program FI, B-AP)
Informatika a druhý obor (program FI, B-IO)
Učitelství výpočetní techniky pro střední školy (program FI, M-SS)

Cíle předmětu

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: shora -- LL(1) gramatiky, zdola -- nástroj yacc či ekvivalent; (případové studie gramatik Java, C, ...).

Literatura

I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
GRUSKA, Jozef. Foundations of computing. Online. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info

Metody hodnocení

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

Informace učitele

http://www.fi.muni.cz/usr/cerna/AaG/ib102.html

Další komentáře

Předmět je vyučován každoročně.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Předmět je zařazen také v obdobích podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019.

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2023

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

Rozsah

2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno prezenčně.

Vyučující

Garance

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

předmět má 62 mateřských oborů, zobrazit

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

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.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2022

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

Rozsah

2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno prezenčně.

Vyučující

Garance

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

předmět má 62 mateřských oborů, zobrazit

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

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.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2021

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

Rozsah

2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno prezenčně.

Vyučující

Garance

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

předmět má 62 mateřských oborů, zobrazit

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

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.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2020

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

Rozsah

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

Vyučující

Garance

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

předmět má 62 mateřských oborů, zobrazit

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. Online. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. [citováno 2024-04-23] URL info

neurčeno

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

Výukové metody

přednášky a cvičení

Metody hodnocení

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.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

IB102 Automaty a gramatiky

Fakulta informatiky
podzim 2002

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

Rozsah

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

Vyučující

prof. RNDr. Mojmír Křetínský, CSc. (přednášející)

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.

Předpoklady

! I005 FJA I &&! I505 FJA I &&( MB101 Matematika I || MB005 Základy matematiky )

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

Aplikovaná informatika (program FI, B-AP)
Informatika (program FI, B-IN)

Cíle předmětu

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: shora -- LL(1) gramatiky, zdola -- nástroj yacc či ekvivalent; (případové studie gramatik Java, C, ...).

Literatura

I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
GRUSKA, Jozef. Foundations of computing. Online. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. [citováno 2024-04-23] info
HOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Online. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. [citováno 2024-04-23] info
KOZEN, Dexter C. Automata and computability. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
MOLNÁR, Ľudovít a Bořivoj MELICHAR. Gramatiky a jazyky. Online. Edited by Milan Češka. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1987. 188 s. [citováno 2024-04-23] info

Metody hodnocení

2 písemné zkoušky během semestru a závěrečná písemná zkouška.

Další komentáře

Předmět je vyučován každoročně.
Výuka probíhá každý týden.

Nachází se v prerekvizitách jiných předmětů

IB107 Vyčíslitelnost a složitost
IB005 || IB102

Statistika zápisu (nejnovější)

Informace o předmětu

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty, gramatiky a složitost

IB102 Automaty, gramatiky a složitost

IB102 Automaty, gramatiky a složitost

IB102 Automaty, gramatiky a složitost

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

IB102 Automaty a gramatiky

Další aplikace