Az informatika logika alapjai

Oktatók: Kovásznai Gergely, Kusper Gábor, Bíró Csaba

Eszterházy Károly Egyetem

 

A tantárgy céljai:

 „Az informatika logikai alapjai” kurzus oktatása az Eszterházy Károly Főiskola által indított több képzés részét képzi: a tanegységhez kapcsolódó elméleti és gyakorlati kurzus teljesítése kötelező a Programtervező informatikus alapképzési (BSc) és a Gazdaságinformatikus alapképzési (BSc) szakok esetén, valamint mindkét kurzus része az intézmény Informatikatanár MA részismereti képzésének is. A tanegység oktatása magas hallgatói létszámmal történik, az elmúlt félévben a tanegységre bejelentkezett hallgatók száma nappali és levelező tagozaton összesen 107 fő volt. A Programtervező, illetve a Gazdaságinformatikus szakok a főiskola legkedveltebb és legnagyobb légyszámú szakjai közé tartoznak. „Az informatika logikai alapjai” kurzuson (mindjárt az első szemeszterben) elsajátított logikai alapok egyértelműen hasznosak – és bizonyos mértékben szükségesek – az összes programozással kapcsolatos kurzus esetében. Fontos, hogy a hallgatók megismerjék a logikus gondolkodással kapcsolatos fogalmakat, a gyakorlatban és a programozási feladatokban tudják alkalmazni azokat. Mindez fontos alapot nyújt ahhoz, hogy az oklevelet szerző hallgatók a gyakorlati életben – akár szoftverfejlesztőként – a logikai problémákat sikeresen legyenek képesek interpretálni és megoldani. Ezért is tartjuk kiemelten fontosnak, hogy a tanegység tanításában részt vevő oktatók közösen, a közös tudást, valamint az évek során felhalmozott konkrét oktatási megfigyeléseket és tapasztalatok felhasználva építsenek fel egy olyan elektronikus tananyagot, amely biztosítja az objektum-orientált programozás sikeres és precíz elsajátítását minden hallgató számára, valamint alkalmas a szükséges motiváció kialakítására és fenntartására is egyaránt.  

 A tananyag céljai:

 A tananyagot sikeresen elvégző hallgató képes lesz a mindennapi életből merített problémákat, természetes nyelven kimondott állításokat megfelelő módon, logikai úton modellezni. A kapott logikai állításokat kiértékelni, logikai következtetésekkel kapcsolatos kérdéseket megválaszolni. Programozást tanuló hallgatókról lévén szó, fontosnak tartjuk azt is, hogy a hallgatók olyan algoritmusokat és szoftvereket ismerjenek meg, melyek segítik őket a logikai analízis elvégzésében. Továbbá hogy megismerjék a fent említett algoritmusok és szoftverek által megkívánt normálformákat és formátumokat, és képesek legyenek logikai állításokat ilyen formára hozni. Olyan modern szoftveres és programozási eszközöket kívánunk a hallgatóknak bemutatni, melyek az „unalmas” matematikai háttér megismerésén túl a hallgatóknak egy egyfajta „Hát ez az egész erre jó!” élményt adnak. Meg kívánjuk mutatni, hogy hogyan tudják a való életben a mindennapi hardver-, illetve szoftvertervezési és -fejlesztési feladataikban a logikai ismereteket felhasználni. Érzékeltetjük, hogy mindezeket az ismereteket és technológiákat a „nagyok”, pl. a chipgyártó cégek és a szoftverfejlesztő vállalatok a saját folyamataikban alkalmazzák és teszik ezáltal a saját informatikai termékeiket sokkal megbízhatóbbá és biztonságosabbá, minden embertársunk örömére.  

A tananyag rövid leírása :

A tervezett online kurzus megismerteti a hallgatóval az 0. és 1. rendű matematikai logika alapjait. A logikai modellezést és formalizálást életszerű példákon keresztül mutatja be. Az állítások kiértékelését, következtetések elvégzését, normálformára alakítást szintén sok-sok feladaton keresztül sajátíthatják el a hallgatók. A tananyagban érintett szoftverekkel is kell a hallgatóknak megadott feladatokat megoldaniuk.

1. modul. Szövegértés és logika. A matematikai logika szerepe. Formalizálás 0. rendű logikában. Szintaktikai fogalmak: ítéletváltozó, formula definíciója. A logikai összekötő jelek szemantikája.

2. modul. 0. rendű logika szemantikai fogalmai: interpretáció (kiértékelés), logikai törvény, logikai ellentmondás, kielégíthetőség, logikai következmény. Igazságtábla. Bevezetés egy ingyenes komputeralgebrai rendszer használatába (Maxima, Wolfram Alpha live).

3. modul. Normálformák. Kapcsolódó definíciók: literál, elemi diszjunkció/konjunkció, KNF, DNF. Normálformára hozó algoritmus, átírási szabályok: logikai jelek eltüntetése, de Morgan azonosságok, disztributivitás, egyszerűsítési szabályok, elimináció. Programozás technikai vonatkozások (pl. ciklusba lépés, ciklusban maradás feltétele, feltételek elemzése, egyszerűsítése).

4. modul. KNF/DNF-re hozás (folytatás). Logikai törvény, logikai ellentmondás bizonyítása átírási szabályok alkalmazásával. Tseitin transzformáció. Egyszerűbb áramkörök tervezése, vizsgálata.

5. modul. Rezolúciós algoritmus 0. rendű logika esetén. DPLL algoritmus. Unit propagáció szabálya. Konfliktusok elemzése, klózok tanulása.

6. modul. DIMACS formátum. Létező szolverekkel való demózás. Hardver- és szoftververifikáció, constraint solving, Spec# (elő és utófeltételek).

7. modul. SMT alapok, SAT-SMT összehasonlítása, egyszerűbb problémák (egész aritmetika) megfogalmazása. Demózás SMT szolverekkel.

8. modul. 1. rendű logika bevezetése. Szövegértés és formalizálás 1. rendű logikában. Kvantorok szemantikája, értelmezésük ciklusként.

9. modul. 1. rendű logikai nyelv. 1. rendű logika szintaktikai fogalmai: term, atom, formula definíciója.

10. modul. Kvantorok hatásköre. Kötött és szabad változó-előfordulások. Formula paraméterei. 1. rendű logika szemantikai fogalmai: logikai törvény, logikai ellentmondás, kielégíthetőség, logikai következmény.

11. modul. KNF/DNF-re hozás (ismétlés). Prenex normálforma. Skolemizálás.

12. modul. Rezolúciós algoritmus 1. rendű logika esetén. Unifikáció.

13. modul. Bizonyítás rezolúció segítségével, teljes és nem teljes rezolúciós stratégiák, a lineáris és az input rezolúció.

14. modul. A Prolog szintaxisa, tények, szabályok, cél, Prolog program átírása Hornklózok halmazává, az SLD-rezolució. Programozás a Prologban.

A kurzus követelményei és értékelési szempontjai:

 A kurzus teljesítéséhez a hallgatók a tananyagtól függően egy- vagy kéthetente házi feladatot kapnak, melynek megoldására a feladat terjedelmétől függően egy- vagy két hét áll rendelkezésükre. A megoldott feladatot az Eszterházy Károly Egyetemen aktívan használt elearning felületre kell feltölteniük. A kurzus sikeres teljesítéséhez a kapott házi feladatok 80%-át szükséges beadniuk. Az otthoni feladatok mellett minden hallgató két zárthelyi dolgozatot kell megírjon, melyek mindegyike szükségképpen elégséges kell legyen a tantárgy teljesítéséhez. Amennyiben a hallgató mindkét zárthelyi dolgozatot elégtelenre írta, úgy a kurzus teljesítése sikertelen, míg egy elégtelen és egy elégséges dolgozat esetén lehetősége van egy javító dolgozat megírására, mely a teljes félévi anyagból vár komplex ismereteket tartalmazza.

 

EKIK Honlap
Óbudai Egyetem Honlap

2014 szeptember 1-je óta az oldal látogatóinak száma: