PředmětyPředměty(verze: 821)
Předmět, akademický rok 2017/2018
   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 2017 do 2019
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
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: prof. RNDr. Roman Barták, Ph.D.
doc. RNDr. Pavel Surynek, Ph.D.
Mgr. Marta Vomlelová, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Je prerekvizitou pro: NTIN046
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: T_KTI (23.05.2008)

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: Mgr. Marta Vomlelová, Ph.D. (16.01.2018)

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í.

Literatura -
Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (16.02.2017)

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

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. (09.10.2017)

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.

Sylabus -
Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

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.

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

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

Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy

 
Univerzita Karlova | Informační systém UK