PředmětyPředměty(verze: 809)
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 2016
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: http://ktiml.mff.cuni.cz/~bartak/automaty/
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

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