PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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 [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
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. (07.02.2024)

Naučit základy teorie automatů a gramatik, zejména o regulárních a bezkontextových jazycích a základních třídách složitosti.

Podmínky zakončení předmětu -
Poslední úprava: Mgr. Marta Vomlelová, Ph.D. (07.02.2024)

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 především na základě bodového hodnocení závěrečného testu, část bodů je možné udělit za aktivitu v podobě případných domácích úloh, aktivity na cvičeních apod. Opakovat lze pouze závěrečný test, nikoli aktivitu v průběhu semestru.

V případě epidemie 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. Marta Vomlelová, Ph.D. (07.02.2024)
  • J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
  • M. Sipser: Introduction to the Theory of Computation, Cengage Learning, 2013
  • 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
  • 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. (07.02.2024)

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

Zkouška sestává z písemné přípravy 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 ze tří otázek, které korespondují obsahem 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.

V případě epidemie možné, ž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. (07.02.2024)

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 regulární jazyky.

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

Bezkontextové gramatiky, derivace, normální tvary, pumping (iterační) lemma pro bezkontextové jazyky, zásobníkové automaty.

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

Polynomiální složitost, NP-úplnost, Cook-Levinova věta.

 
Univerzita Karlova | Informační systém UK