Az informatika elméleti alapjai

1. félév (2+1+1, 4 kredit, X)

Ábécék, szavak és nyelvek, nyelvcsaládok, a matematikai logika nyelve. Algoritmikus problémák és nyelvekkel való reprezentációjuk. Formális nyelvtanok, mint a nyelvek leírásának eszközei, a Chomsky-féle nyelvtani osztályok, nyelvosztályok és néhány zártsági tulajdonságuk, a Chomsky-féle hierarchia. A szóprobléma és algoritmikus eldöntése absztrakt programnyelvi algoritmusokkal.

Véges automaták és változataik, felismerő erejük. A harmadik típusú nyelvek tulajdonságai. Verem-automaták és változataik, felismerő erejük. A második típusú nyelvek tulajdonságai.

A Turing-gép és változatai, Turing gépek programozása, eldönthető és eldönthetetlen nyelvek.

2. félév (2+0+0, 2 kredit, K)

Szavak, nyelvek, nyelvek megadásának módszerei, formális nyelvtanok, matematikai gépek.

Véges automaták analízisének és szintézisének módszerei, véges automaták minimalizálása.

Környezet-független nyelvtanok elemzése. A levezetés fogalom kiterjesztésének lehetőségei, indexelt-nyelvtanok, attribútum nyelvtanok, kétszintű nyelvtanok, gyakorlati alkalmazásaik.

A Turing-gép és változatai, Turing gépek programozása, eldönthető és eldönthetetlen nyelvek. Eldönthetetlen problémák az informatikában. Problémák megoldásának idő- és tárigénye, idő- és tárbonyolultsági osztályok. P és NP, NP-teljes problémák az informatikai gyakorlatban.

Kompetenciák:

Rendelkezik azokkal az ismeretekkel, amelyek lehetővé teszik, hogy szaktárgyának új eredményeit megismerhesse, értelmezhesse. Ismeri a szaktárgy alapvető kutatási módszertanát. – Képes a szaktárgy témakörében szakszerűen kifejezni magát mind szóban, mind írásban. Képes a szaktárgyának megfelelő tudományterületen a fogalmak, elméletek és tények közötti összefüggések megteremtésére, közvetítésére. Képes a szaktárgyában elsajátított elméleti ismeretek gyakorlati alkalmazására, ennek közvetítésére a tanulók felé.

Irodalomjegyzék:

• J. Demetrovics, J. Denev, R. Pavlov, A számítástudomány matematikai alapjai, Tankönyvkiadó, 1995.
• Bach Iván, Formális nyelvek, Typotex, 2001.
• Dr. Fülöp Zoltán, Formális nyelvek és szintaktikus elemzésük, 2. kiadás: Polygon, Szeged, 2004.
• Hunyadvári László, Manhertz Tamás, Formális nyelvek I., Elektronikus jegyzet, 2005. (http://aszt.inf.elte.hu/~hunlaci/book.pdf)
• Hunyadvári László, Formális nyelvek II., Elektronikus jegyzet, 2009. (http://aszt.inf.elte.hu/~hunlaci/fnyau2.pdf)
• Dr. Ésik Zoltán: A számítástudomány alapjai, Typotex Kiadó, 2011.

• G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Springer-Verlag, 1997.
• J.E. Hopcroft, R. Montovani, J.D. Ullman,Introduntion to Automata Theory, Languages, Computation, Addison Wesley, 2001.
• J. Hromkovic, Theoretical Computer Science, Springer-Verlag, 2004.
• G. Paun, G. Rozenberg, A. Salomaa (Eds.), The Oxford Handbook of Membrane Computing, Oxford University Press, 2012.