I005 Formální jazyky a automaty I

Fakulta informatiky
jaro 2002
Rozsah
3/2. 5 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Mojmír Křetínský, CSc. (přednášející), prof. RNDr. Ivana Černá, CSc. (zástupce)
prof. RNDr. Ivana Černá, CSc. (cvičící)
prof. RNDr. Jiří Barnat, Ph.D. (cvičící)
doc. RNDr. Tomáš Brázdil, Ph.D. (cvičící)
Mgr. BcA. Robert Král, Ph.D. (cvičící)
Mgr. Pavel Krčál (cvičící)
Mgr. Jaroslav Műller (cvičící)
doc. Mgr. Radek Pelánek, Ph.D. (cvičící)
RNDr. Jaroslav Ráček, Ph.D. (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Radek Sedláček, Ph.D. (cvičící)
Mgr. Oldřich Stražovský (cvičí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.
Rozvrh seminárních/paralelních skupin
I005/01: Čt 13:00–14:50 B011, J. Barnat
I005/01plus: Rozvrh nebyl do ISu vložen. J. Barnat
I005/02: Čt 15:00–16:50 B011, J. Barnat
I005/02plus: Rozvrh nebyl do ISu vložen. J. Barnat
I005/A: Čt 9:00–10:50 B410, I. Černá
I005/pondel: Po 12:00–14:50 D1, M. Křetínský
I005/streda: St 14:00–16:50 D1, M. Křetínský
I005/03: Čt 17:00–18:50 B011, R. Pelánek
I005/04: Pá 8:00–9:50 B003, V. Řehák
I005/05: Čt 13:00–14:50 C416, J. Ráček
I005/06: Čt 15:00–16:50 C416, J. Ráček
I005/07: Čt 15:00–16:50 B003, J. Műller
I005/08: Čt 17:00–18:50 B003, R. Sedláček
I005/09: Čt 11:00–12:50 B007, P. Krčál
I005/10: Pá 8:00–9:50 B204, T. Brázdil
I005/11: Čt 9:00–10:50 B011, R. Sedláček
I005/12: Čt 9:00–10:50 B007, V. Řehák
I005/13: Čt 11:00–12:50 B011, R. Král
I005/14: Pá 10:00–11:50 B204, R. Král
I005/15: Čt 9:00–10:50 B003, J. Ráček
I005/17: Pá 10:00–11:50 B410, O. Stražovský
I005/18: Čt 13:00–14:50 B410, P. Krčál
Předpoklady
I000 Úvod do informatiky && ( M005 Základy matematiky || M036 Okruhy a moduly || PřF:M3510 Algebra III ) && (! I505 FJA I )&& (!NOW( I505 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
Osnova
  • Pojem jazyka a gramatiky. Chomského hierarchie.
  • Konečné automaty a regulární gramatiky.
  • Vlastnosti regulárních jazyků.
  • Bezkontextové gramatiky a zásobníkové automaty.
  • Vlastnosti bezkontextových jazyků.
  • Deterministické zásobníkové automaty.
  • Turingovy stroje. Vyčíslitelné jazyky a funkce.
  • Nerozhodnutelnost, (parciální) rozhodnutelnost. Problém zastavení TS.
  • Postův korespondenční problém. Algoritmicky nerozhodnutelné problémy z teorie jazyků.
Literatura
  • I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
  • 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
Metody hodnocení
2 písemné zkoušky během semestru a závěrečná písemná zkouška.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/usr/kretinsky/fja1.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích léto 1995, zima 1995, léto 1996, léto 1997, léto 1998, jaro 1999, jaro 2000, jaro 2001.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2002/I005