456-0061/01 – Teorie jazyků a automatů (TJA)

Garantující katedraKatedra informatikyKredity8
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětuprof. RNDr. Petr Jančar, CSc.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
RočníkSemestrzimní
Jazyk výukyčeština
Rok zavedení1992/1993Rok zrušení2005/2006
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
JAN59 prof. RNDr. Petr Jančar, CSc.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2

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

Cílem předmětu je zvládnutí základních pojmů a metod teorie jazyků a automatů, speciálně konečných automatů a bezkontextových jazyků.

Vyučovací metody

Anotace

Kurs je venovan zakladnim partiim (matematicke) teorie automatu a jazyku, se soustredenim se na konecne automaty a bezkontextove jazyky. Cilem kursu je jednak objasneni pojmu, vysledku a metod, ktere jsou vyuzivany v ruznych oblastech aplikovane informatiky (napr. pri vyhledavani vzorku v textu ci pri navrhu a realizaci prekladacu), a take demonstrovani uzitecnosti formalizovaneho (abstraktniho) pristupu pri reseni (praktickych) problemu.

Povinná literatura:

M. Chytil: Automaty a gramatiky, SNTL, Praha 1984 J. Hopcroft, J. Ullman: Formal languages and their relation to automata - slov. preklad Formalne jazyky a automaty, Alfa, Bratislava 1978 Molnar, Ceska, Melichar: Gramatiky a jazyky, Alfa-SNTL 1987 Krome vyse uvedenych existuji i dalsi moznosti studia uvedene problematiky v cestine ci slovenstine. Neuvadime cizojazycnou literaturu kvuli jeji tezke dostupnosti -- na druhe strane surfovanim na Webu je samozrejme mozne ziskat mnohe uzitecne texty v anglictine.

Doporučená literatura:

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

Podmínky udělení zápočtu: Za kazde cviceni, na ktere si posluchac donese (dostatecnou) pisemnou pripravu a bude na nem pripraven reseni a problemy aktivne diskutovat, ziska 1 bod - maximalne vsak 10 bodu za semestr. Podminkou zapoctu je odevzdani prehledne zpracovaneho pisemneho reseni vsech prikladu zadanych pro vsechna cviceni v semestru. Reseni musi byt psano vlastni rukou resitele (nikoli vystup z elektronicke podoby ci podobne) a musi byt odevzdano nejpozdeji na poslednim cviceni v semestru ! Poznamka. I ten, kdo se nekterych cviceni nezucastni, ci kdo na ne nebude dostatecne pripraven, musi tedy pro ziskani zapoctu odevzdat i reseni uloh prislusnych k temto cvicenim. Body za takova cviceni ovsem nedostane. Muze se tedy i stat, ze nekdo splni podminky zapoctu, ale neziska zadny bod.

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: Uvod ke kursu. Konecny automat. Navrh konecnych automatu. Regularni operace. Nedeterminismus. Vztah deterministickych a nedeterministickych konecnych automatu. Uzaverove tridy regularnich jazyku. Regularni vyrazy a jejich ekvivalence s konecnymi automaty. Minimalni konecne automaty a algoritmus minimalizace. Neregularni jazyky. Pumping lemma pro regularni jazyky. Bezkontextove gramatiky a jazyky, stromy odvozeni, jednoznacnost, uloha syntakticke analyzy. Redukovane gramatiky, Chomskeho normalni forma. Zasobnikove automaty a jejich ekvivalence s bezkontextovymi gramatikami. Uzaverove vlastnosti tridy bezkontextovych jazyku. Deterministicke zasobnikove automaty. Nebezkontextove jazyky. Pumping lemma pro bezkontextove jazyky. Obecne gramatiky, Chomskeho hiearchie. Konecne automaty a regularni gramatiky. Turingovy stroje. Rekurzivni a rekurzivne spocetne jazyky. Linearne omezene automaty a kontextove jazyky. Zaver kursu.

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

Prezenční forma (platnost od: 1960/1961 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.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2006/2007 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 5 volitelný odborný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 volitelný odborný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (B2612) Elektrotechnika a informatika (1801R001) Informatika P čeština Ostrava 3 povinný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán
2000/2001 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán

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

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