Kapitoly z teoretické informatiky

Garant předmětu:  Doc. RNDr. Alice Kelemenová, CSc.

Anotace:
Cílem předmětu je seznámit doktorandy s klasickými oblasti teoretické informatiky jako jsou teorie formálních jazyků a automatů, teorie vyčíslitelnosti a složitosti a se současnými trendy v teoretické informatiky. Absolvování předmětu umožní základní orientaci v oblasti a poskytne absolventům možnost sledovat rozvoj discipliny.

Sylabus
Formální jazyk. Motivace, operace.
Formální stroje.
Turingův stroj. Jeho varianty (počet pásek, počet a směr pohybu hlav). Nedeterminismus. Zásobníkový automat. Konečný automat.
Formální gramatiky. Sekvenční gramatiky, paralelní gramatiky, řízené odvození v gramatikách.
Výpočetní síla automatů a gramatik.
Složitost jazyků. Výpočetní složitost a popisná složitost.
Kooperativní a distribuované systémy.
Biologicky motivované stroje a gramatiky. Celulární automat, L systémy, P systémy, ekogramatické systémy.

Literatura:
1. D.P. Bovet, P. Crescenzi: Introduction to the theory of complexity. Prentice Hall, 1994
2. E. Csuhaj-Varjú, J. Dassow, J. Kelemen, G. Păun: Grammar systems: A grammatical approach to distribution and cooperation. Gordon and Breach, Yverdon, 1994
3. J. Dassow, G. Paun: Regulated rewriting in formal language theory. Springer Verlag, 1989
4. J. Gruska: Foundation of computing. Thomson 1997
5. G. Rozenberg, A. Salomaa: The mathematical theory of L systems. Academic Press, 1980
6. G. Rozenberg, A. Salomaa (eds.): Handbook of formal languages, Springer Verlag, Berlin, 1997
7. D.A. Simovici, R.L. Tenney: Theory of formal languages with applications. World Scientific, 1999