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
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 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
    neurčeno
  • 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
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
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
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.