Předmět Seminář teoretické informatiky (FIT-STI)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu FIT-STI - Seminář teoretické informatiky, Fakulta informačních technologií, Vysoké učení technické v Brně (VUT).

Materiál	Typ	Datum	Počet stažení

Cíl

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.

Osnova

Osnova přednášek:Množiny a relace. Řetězce, jazyky, operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik. Regulární jazyky a konečné automaty, determinizace a minimalizace automatů, převod regulárních výrazů na konečné automaty. Kleeneho algebra. Pumping lemma, důkaz neregularity jazyků. Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik. Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků. Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky. Turingovy stroje. Jazyky rekurzívní a rekurzívně vyčíslitelné a jejich vlastnosti. Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů. Vyčíslitelné funkce. Další Turingovsky úplné výpočetní mechanismy (automaty s více zásobníky, automaty s čítači). Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti. NP problémy. Polynomiální redukce. 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ů, ...).

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-0Kozen, 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

Požadavky

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

Garant

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

Vyučující

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