Detail předmětu

Seminář teoretické informatiky

FIT-STIAk. rok: 2014/2015

Výuka probíhá formou demonstračních cvičení s aktivním podílem studentů na řešení konkrétních problémů a příkladů z oblastí teoretické informatiky včetně teorie vyčíslitelnosti a složitosti. Řešené problémy a příklady spadají do témat pokročilé teorie a aplikací regulárních jazyků, bezkontextových jazyky a kontextových jazyků, Turingových strojů, rozhodnutelnosti, redukce rozhodovacích problémů, vyčíslitelných funkcí a základů složitosti. Aplikačními oblastmi jsou modelování systémů, formální analýza a verifikace systémů, překladače, umělá inteligence, lingvistika ap.

Jazyk výuky

čeština

Počet kreditů

Garant předmětu

prof. Ing. Tomáš Vojnar, Ph.D.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Výsledky učení předmětu

Hlubší pochopení principů a schopnost aplikace poznatků z teorie formálních jazyků a teorie vyčíslitelnosti a složitosti. Student je schopen aplikovat získané znalosti při řešení teoretických i praktických problémů modelování, programování, formální specifikace, automatizace návrhu, verifikace a umělé inteligence.

Rozšíření a zkvalitnění schopností samostatně formalizovat a řešit informatické i aplikační problémy, vytvářet algoritmy i konstruovat důkazy. Student mj. získává hlubší kompetence k výzkumné práci v různých oblastech informatiky.

Prerekvizity

Základní znalosti z teorie algeber, teorie grafů a regulárních a bezkontextových jazyků.

Způsob a kritéria hodnocení

Maximálně dvě neomluvené absence.

Osnovy výuky

    Osnova přednášek:
    1. Množiny a relace. Řetězce, jazyky, operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik.
    2. Regulární jazyky a konečné automaty, determinizace a minimalizace automatů, převod regulárních výrazů na konečné automaty.
    3. Kleeneho algebra. Pumping lemma, důkaz neregularity jazyků.
    4. Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik.
    5. Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků.
    6. Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky.
    7. Turingovy stroje.
    8. Jazyky rekurzívní a rekurzívně vyčíslitelné a jejich vlastnosti.
    9. Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů.
    10. Vyčíslitelné funkce. Další Turingovsky úplné výpočetní mechanismy (automaty s více zásobníky, automaty s čítači).
    11. Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti.
    12. NP problémy. Polynomiální redukce.
    13. Aplikace poznatků z teoretické informatiky v překladačích, automatizované verifikaci, lingvistice, ... Přehled různých oblastí rozšiřujících probranou látku (automatizované učení jazyků ze vzorků, stromové jazyky s využitím ve verifikaci nebo např. při manipulaci XML, automaty s omezeními, hierarchie nerozhodnutelných problémů, ...).

Učební cíle

Rozšíření schopností aplikovat poznatky pokročilé teorie formálních jazyků a teorie vyčíslitelnosti a výpočetní složitosti a schopnosti řešit konkrétní teoretické a praktické problémy. Předmět pokrývá, rozšiřuje a procvičuje všechny oblasti diskutované v předmetu Teoretická informatika, tj. regulární jazyky a konečné automaty, bezkontextové jazyky a zásobníkové automaty, Turingovy stroje, vyčíslitelnost, rekurzivní funkce i složitost.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Kontrola účasti, maximálně dvě neomluvené absence.

Základní literatura

Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0 Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1 Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3. vydání, 2002. ISBN 0-072-32200-4 Brookshear, J.G.: Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7 Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8

Doporučená literatura

Češka, M. a kol.: Vyčíslitelnost a složitost, Nakl. VUT Brno, 1993. ISBN 80-214-0441-8 Češka, M., Rábová, Z.: Gramatiky a jazyky, Nakl. VUT Brno, 1992. ISBN 80-214-0449-3 Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0 Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1 Černá, I., Křetínský, M., Kučera, A.: Automaty a formální jazyky I, učební text FI MU, Brno, 1999. Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997. ISBN 1-85032-243-0

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-2 magisterský navazující

    obor MBI , 1 ročník, zimní semestr, volitelný
    obor MBS , 1 ročník, zimní semestr, volitelný
    obor MIN , 1 ročník, zimní semestr, volitelný
    obor MIS , 1 ročník, zimní semestr, volitelný
    obor MMI , 1 ročník, zimní semestr, volitelný
    obor MMM , 1 ročník, zimní semestr, volitelný
    obor MPV , 1 ročník, zimní semestr, volitelný
    obor MSK , 1 ročník, zimní semestr, volitelný
    obor MGM , 1 ročník, zimní semestr, volitelný