Számítástudomány alapjai
- 2 óra előadás (kollokvium), 1 óra gyakorlat (Gyakorlati jegy)
- 3+1 kredit, őszi félév
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.
Ajánlott irodalom
- É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
Hall. 1998.
- 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/
Tantárgy oktatója
Gombás Éva Dr.
A tantárgy honlapja
Számítástudomány alapjai