PředmětyPředměty(verze: 941)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
Automaty a gramatiky - NTIX071
Anglický název: Automata and Grammars
Zajišťuje: Studijní oddělení (32-STUD)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Je zajišťováno předmětem: NTIN071
Další informace: https://dl1.cuni.cz/course/view.php?id=5119
Garant: Mgr. Marta Vomlelová, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Prerekvizity : {NXXX015, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX030, NXXX031, NXXX033, NXXX065}
Neslučitelnost : NTIN071
Záměnnost : NTIN071
Je neslučitelnost pro: NTIN071
Je záměnnost pro: NTIN071
Anotace -
Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)
Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
Cíl předmětu -
Poslední úprava: Mgr. Marta Vomlelová, Ph.D. (13.05.2019)

Naučit základy teorie automatů a gramatik, zejména o regulárních a bezkontextových jazycích.

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Jan Hric (12.05.2022)

Formou kontroly studia předmětu je zápočet a zkouška. Získání zápočtu je nutnou podmínkou pro absolvování zkoušky.

Zápočet udělují vyučující na jednotlivých cvičeních na základě bodového hodnocení průběžných testů, případných domácích úloh, aktivity apod. Povaha kontroly na zápočet vylučuje možnost jejího opakování.

Je možné, že se část zkoušek či zápočtů bude konat distanční formou. Závisí to na vývoji aktuální situace a o jakékoli změně budete včas informováni.

Literatura -
Poslední úprava: Mgr. Petr Jedelský (21.02.2019)
  • M. Chytil: Automaty a gramatiky, SNTL Praha, 1984
  • V. Koubek: Automaty a gramatiky, elektronický text (http://ktiml.mff.cuni.cz/ktiml/teaching/files/materials/Automstr_ps.zip), 1996
  • M. Chytil: Teorie automatů a formálních jazyků, skripta MFF UK, 1978
  • M. Chytil: Sbírka řešených příkladů z teorie automatů a formálních jazyků, skripta MFF UK, 1987
  • M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL Praha, 1990
  • J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
  • Videozáznamy přednášek
Metody výuky -
Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

přednáška a cvičení

Požadavky ke zkoušce -
Poslední úprava: Mgr. Marta Vomlelová, Ph.D. (27.04.2020)

Zápočet je nutnou podmínkou účasti na zkoušce.

Zkouška sestává z písemné a ústní části. Písemná část předchází části ústní, její nesplnění znamená, že celá zkouška je hodnocena známkou nevyhověl(a) a ústní částí se již nepokračuje.

Nesložení ústní části znamená, že při příštím termínu je nutno opakovat obě části zkoušky, písemnou i ústní. Známka ze zkoušky se stanoví na základě bodového hodnocení písemné i ústní části.

Písemná část bude sestávat z dvanácti otázek, které korespondují sylabu přednášky, ověřují schopnosti získané na cvičení a znalost definic, vět a algoritmů z přednášky.

Požadavky ústní části odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce. Zpravidla se jedná o detailnější rozbor zadaného problému, např. zdůvodnění zařazení daného jazyka do Chomského hierarchie či důkaz klíčových vět.

Je pravděpodobné, že se značná část zkoušek či zápočtů může konat distanční formou. Za ekvivalent písemného testu se považuje zkouškový test moodle, ústní zkoušení může probíhat distanční formou.

Závisí to na vývoji aktuální situace a o jakékoli změně budete včas informováni.

Sylabus -
Poslední úprava: Mgr. Marta Vomlelová, Ph.D. (13.05.2019)

Konečné automaty a regulární jazyky, Nerodova věta, ekvivalence a redukce automatů, nedeterminismus.

Uzávěrové vlastnosti, regulární výrazy, Kleeneova věta, pumping (iterační) lemma pro regurální jazyky.

Gramatiky, Chomského hierarchie, regulární, bezkontextové a kontextové gramatiky

Bezkontextové gramatiky, derivace, redukce, normální tvary, pumping (iterační) lemma pro bezkontextové jazyky, uzávěrové vlastnosti, deterministické a nedeterministické zásobníkové automaty.

Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy, univerzální jazyk, diagonální jazyk.

 
Univerzita Karlova | Informační systém UK