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: