456-0500/01 – Teorie jazyků a automatů - Bc. (TJAb)

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í1998/1999Rok zrušení2003/2004
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
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:

Pracovní text ke kursu zpracovaný P. Jančarem (na http://www.cs.vsb.cz/jancar/TJAA/tjaa.htm odkazy na soubor clk_tja01_2p.ps a alternativne na clk_tja01_2p.pdf)

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: 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
2003/2004 (B2612) Elektrotechnika a informatika (1801R001) 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
2002/2003 (B2612) Elektrotechnika a informatika (1801R001) Informatika P čeština Ostrava 3 povinný stu. plán
2001/2002 (B2612) Elektrotechnika a informatika (1801R001) Informatika P čeština Ostrava 3 povinný stu. plán
2000/2001 (B2612) Elektrotechnika a informatika (1801R001) 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