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