PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   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í
Další informace: https://dl1.cuni.cz/course/view.php?id=5119
Garant: Mgr. Marta Vomlelová, Ph.D.
Vyučující: RNDr. Jakub Bulín, Ph.D.
Mgr. Tomáš Čelko
doc. Mgr. Petr Gregor, Ph.D.
doc. RNDr. Vladislav Kuboň, Ph.D.
Mgr. Vladan Majerech, Dr.
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: NTIN013, NTIX071
Je prerekvizitou pro: NTIN046, NSWI098
Je záměnnost pro: NTIN013, NTIX071, NUIN002
Ve slož. záměnnosti pro: NUIN021
Anotace -
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).
Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)
Cíl předmětu -

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.

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

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.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)
Literatura -
  • 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
Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)
Metody výuky -

přednáška a cvičení

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)
Požadavky ke zkoušce -

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.

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

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.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)
 
Univerzita Karlova | Informační systém UK