Elméleti
informatikai alapismeretek, 2+0, kollokvium
1. félév:
Á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:
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: