456-0906/01 – Teorie jazyků a automatů - Ph.D. (TJA)

Garantující katedraKatedra informatikyKredity10
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětuprof. RNDr. Petr Jančar, CSc.
Úroveň studiapostgraduálníPovinnostpovinně volitelný
RočníkSemestrzimní + letní
Jazyk výukyčeština
Rok zavedení1997/1998Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studiadoktorské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 3+0
kombinovaná Zápočet a zkouška 3+0

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Student po úspěšném absolvování předmětu: - rozumí základním pojmům v oblasti teorie jazyků a automatů - umí volit vhodný formální jazyk k popisu praktických problémů a chápe možnosti i omezení různých tříd automatů v souvislosti s jejich řešením - prokáže schopnost samostatně zvládnout a odprezentovat pokročilou partii v dané oblasti (např. u verifikace programů)

Vyučovací metody

Přednášky
Individuální konzultace
Projekt

Anotace

Předmět nejdříve rekapituluje základní znalosti týkajici se konečných automatů, bezkontextových jazyků a Turingových strojů, se kterými se studenti seznámili v magisterském studiu. Klade se ovšem důraz na exaktní přístup a hlubší pochopení. Dále je kurs věnován pokročilejším partiím v těchto a dalších oblastech (např. vztahu jazyků, automatů a logiky, stromovým jazykům apod.).

Povinná literatura:

J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1978 M.Demlová, V.Koubek: Algebraická teorie automatů. Matematický seminář SNTL, Praha, 1990 M.Chytil: Automaty a gramatiky. Matematický seminář SNTL, Praha, 1984

Doporučená literatura:

Handbook of formal languages, Vol 1,2,3 (ed. G.Rozenberg) (Springer 1997)

Forma způsobu ověření studijních výsledků a další požadavky na studenta

E-learning

Další požadavky na studenta

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Přednášky: Pojem formálního jazyka. Operace s jazyky. Regulární jazyky. Specifikace jazyků. Přepisovací systémy a gramatiky. Chomského klasifikace gramatik. Konečné automaty: deterministické, nedeterministické, zobecněné nedeterministické. Jazyky rozpoznávané konečnými automaty. Kleeneho věta. Automatové morfismy a minimalizace konečných automatů. Konečné automaty a regulární gramatiky. Bezkontextové gramatiky. Zásobníkové automaty. Jazyky generované bezkontextovými gramatikami a rozhodované zásobníkovými automaty. Kontextové jazyky generované kontextovými gramatikami a rozpoznávané lineárně omezenými automaty. Turingovy stroje. Jazyky rozpoznávané a rozhodované Turingovými stroji /rekurzivně spočetné a rekurzivní jazyky/. Postova věta. Algoritmická řešitelnost. Turingova /Churchova/ téze. Další partie teorie konečných automatů (dvoucestné automaty, automaty s váhami, ...) Další partie teorie bezkontextových jazyků (deterministické bezkontextové jazyky, ...) Stromové jazyky Vztah jazyků, automatů a logických teorií Další vybrané partie

Podmínky absolvování předmětu

Prezenční forma (platnost od: 1960/1961 letní semestr, platnost do: 2008/2009 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2007/2008 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku