Számítástudomány alapjai

Tematika

Nyelvek és műveletek nyelveken. Reguláris nyelvek és véges automaták. Determinisztikus és nemdeterminisztikus automaták. A reguláris nyelvek pumpáló lemmája.
Nyelvtanok. A Chomsky hierarchia. Környezetfüggetlen nyelvek és veremautomaták. A környezetfüggetlen nyelvek zártsági tulajdonságai. Egyértelmű nyelvtanok és nyelvek. A környezetfüggetlen nyelvek pumpáló lemmája és nem környezetfüggetlen nyelvek.
Turing-gépek és változataik. Turing-gépek mint a számítás formális modelljei. A Turing-gépek ekvivalenciája az egyéb számítási modellekkel. Church tézise. Rekurzív és rekurzívan felsorolható nyelvek. Eldönthetetlen problémák.
Problémák példányainak szavakkal való reprezentálása. Az idő- és tárigény becslése. Megfelelően tömör kódolások.
Algoritmusok idő- és tárigénye. Idő és tárkorlátos Turing-gépek. Bonyolultsági osztályok.
A P és NP osztályok. P-teljes és NP-teljes problémák. A PSPACE osztály, a PSPACE-teljes problémák. Az L és NL osztályok. Bizonyíthatóan nehéz problémák.

Ésik Zoltán: Számítástudomány alapjai, Typotex Kiadó, 2011. Jegyzet letöltése PDF formátumban
Ésik Zoltán, Gombás Éva, Iván Szabolcs: Automaták és formális nyelvek példatár, Typotex Kiadó, 2011.Jegyzet letöltése PDF formátumban
Peter Linz: An Introduction to Formal Languages and Automata, 5th edition, Jones & Bartlett Publishers, Sudbury, MA, USA, 2012.
Susan H. Rodger and Thomas W. Finley: JFLAP An Interactive Formal Languages and Automata Package, Jones & Bartlett Publishers, Sudbury, MA, USA, 2006.v
J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Reading, 1979.
Lovász László: Algoritmusok bonyolultsága, Tankönyvkiadó, 1989.v
H. R. Lewis, C. H. Papadimitriou: Elements of the Theory of Computation, 2nd ed., Prentice
C. H. Papadimitriou: Számítási bonyolultság, Novadat Kiadó, 1999.
M. Sipser: Introduction to the Theory of Computation, PWS Publishing Co., 1997.
JFLAP program, letölthető: http://www.jflap.org/