Elméleti informatikai alapismeretek, 2+0, kollokvium
Á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 és elemzésének legfontosabb módszerei.
A Turing-gép és változatai. Kiszámíthatóság és eldönthetőség, 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.
Kialakítandó kompetenciák:
Hunyadvári László, Manhertz Tamás, Formális nyelvek I., Elektronikus jegyzet, 2006. (http://aszt.inf.elte.hu/~hunlaci/book.pdf)
G. Rozenberg, A. Salomaa, Handbook of Formal Languages, Springer-Verlag, 1997.