PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Automaty a gramatiky - NTIN071
Anglický název: Automata and Grammars
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
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
Neslučitelnost : NTIX071
Záměnnost : NTIX071
Je neslučitelnost pro: NTIX071, NTIN013
Je prerekvizitou pro: NTIN046
Je záměnnost pro: NTIX071, NTIN013, NUIN002
Ve slož. záměnnosti pro: NUIN021
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 pravděpodobné, že se značná část zkoušek či zápočtů může 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