Babeş–Bolyai Tudományegyetem Kolozsvár
Matematikai és Informatikai Kar  
2006-2007-es  tanév,  I.  félév 

I.	A tantárgy adatai

A tantárgy neve: A számítógépek matematikai alapjai
Kód: MIF0001
Kreditszám: 6
Hol tartják?  (előadás, szeminárium): 16-os terem
Mikor tartják? (előadás, szeminárium): hétfő 8-10; hétfő 10-12

II.	Az oktatók adatai 
 
Előadás
Név, tudományos cím: Egri Edith, tanársegéd
Elérhetőség (e-mail, telefon): egriedit@yahoo.com
Fogadóóra : az órarend függvényében
Szeminárium
Név, tudományos cím: Egri Edith, tanársegéd
Elérhetőség (e-mail, telefon): egriedit@yahoo.com
Fogadóóra : az órarend függvényében

III.	A tantárgy leírása: 

Célok
	Az előadás célja olyan logikai ismeretek elsajátítása a hallgatók által, amelyekre a következő években szükségük lesz, és amelyek a számítógépek működésének, illetve programázásának alapját képezik: kijelentés- és predikátumkalkulus, Boole-algebra és függvények, tételbizonyítás. Ott, ahol lehetséges, rámutatunk  a logika alkalmazására a számítástechnikában: logikai kapukkal megvalósítható áramkörök, logikai programozás, stb. Ezenkívül az információnak a számítógép belsejében való kódolásával kapcsolatos fogalmak is szóba jönnek.

Tartalom
1. Számrendszerek. Számok átváltása a különböző számrendszerek között. 
2. Az információ ábrázolása a számítógép belsejében: alfanumerikus és numerikus adatok kódolása.  Fixpontos ábrázolás (komplementer kód), lebegőpontos ábrázolás.
3. Hibaészlelő és hibajavító kódok.
4. Boole algebra. Boole függvények megadási módjai. Igazságfüggvények leegyszerűsítése. 
5. Logikai áramkörök.
6. A matematikai logika alapjai. Predikátumkalkulus. A döntéshozás problémája a predikátumok logikájában: Skolem tétele. Tételbizonyítás a rezolúció módszerével.

Kompetenciák
1. A különböző  (főként bináris) számrendszerekben való  műveletvégzéshez, átváltási módszerekhez szükséges jártasság kialakulása
2. A számítógép belsejében történő adatábrázolás különböző formáinak alkalmazása
3. A hibaészlelő és hibajavító kódok alapjaival való megismerkedés
4. A számítógép elemi alkotóelemeit képező logikai áramkörök megismerése
4. Megbarátkozás az automatikus gondolatmenettel
5. Előkészítés a logikai nyelvek könnyebb elsajátításához
6. A hétköznapi okfejtés matematikai modellezésének begyakorlása kijelentés- és predikátumkalkulus segítségével

Módszerek
Előadás, hallgatókkal való párbeszéd, feladatmegoldás

IV.	Kötelező könyvészet:
1. F. M. BOIAN: Bazele matematice ale calculatoarelor, Editura Presa Universitară Clujeană, 2002
2. DRAGÁLIN ALBERT, BUZÁSI SZVETLANA: Bevezetés a matematikai logikába, Kossuth Egyetem, Debrecen, 1997
3. KISS EMIL: Bevezetés az absztrakt algebrába (kézirat) 
www.cs.elte.hu/~ewkiss/bboard/algebrabook/Abstract_Algebra_582.pdf

V.	Az oktatásban használt eszközök: számítógép, kivetítő

VI.	A tevékenységek és ellenőrzések/részleges vizsgák órarendje:

1.-2. előadás+szeminárium: Számrendszerek
•	A számrenszerek kialakulása
•	Valós számok ábrázolása adott b alapon
•	Átváltási módszerek
•	Műveletek tetszőleges alapú számrendszerekben
•	Példák a 2-es, 8-as és 16-os számrendszerben

3.-4. előadás+szeminárium: Adatábrázolás a számítógépben/I
•	A kódolás és dekódolás kérdése
•	Alfanumerikus kódok: ASCII kód, UNICODE
•	Előjel nélküli egészek ábrázolása, műveletek
•	Egész számok ábrázolása, komplementer kód
•	A túlcsordulás fogalma és annak kezelése
•	Műveletek komplementer kódban

5. előadás+szeminárium: Adatábrázolás a számítógépben/II
•	Valós szám 1 és 2 közötti mantisszás alakja
•	Valós számok kódolása: fixpontos és lebegőpontos ábrázolás
•	Standardok lebegőpontos ábrázolásmódban
•	Túlcsordulás kezelése

6. előadás+szeminárium: Hibaészlelő és hibajavító kódok/I
•	Alapfogalmak értelmezése: véges test, kód hossza, t-hibajelző kód, t-hibajavító kód, Hamming távolság, minimális távolság,  
•	Lineáris kódok (Hamming kód)

7. előadás+szeminárium: Hibaészlelő és hibajavító kódok/II
•	Polinomkódok
•	Ciklikus kódok
•	A dekódolás kérdése

8. előadás+szeminárium: Boole-algebra
•	Logikai műveletek, kifejezések szintaxisa 
•	Szemantika: kifejezések értelmezése (logiki értékek), tautologia, ellentmondás (kontradikció)
•	A Boole algebra értelmezése, axiómái

9. előadás+szeminárium: Boole-függvények
•	Igazságfüggvények megadási módjai és azok közötti kapcsolatok
•	Boole-függvények leegyszerűsítése: analítikus és táblázatos módszerekkel (Karnaugh-féle táblázat, Quine-féle prím implikációs módszer)
•	Konjunktív, illetve diszjunktív normálformák (KNF, DNF). Tetszőleges formula KNF/DNF-ba való felírása.  

10. előadás+szeminárium: Logikai áramkörök
•	Elemi logikai kapuk („and”, „or”,  „not”) értelmezése, fizikai megvalósításuk
•	Származtatott logikai kapuk (”xor”, “nand”, “nor”) és kapcsolataik az elemi logikai kapukkal
•	Boole-függvények megvalósítása logikai kapuk segítségével
•	Példák logikai áramkörökre (összehasonlító áramkör,  dekódoló, félösszeadó, összeadó)

11. előadás+szeminárium: Matematikai logika alapjai/I
•	Elsőrendű matematikai-logikai nyelvek, termek, formulák értelmezése. Példák elsőrendű nyelvekre
•	Szabad és kötött változók, változók helyettesítése termekkel
•	Normálformák
•	Ítéletek formalizálása

12. előadás+szeminárium: Matematikai logika alapjai/II
•	Logikai nyelv klasszikus szemantikája, igazságértékelés a modellben, interpretáció
•	Logikai törvények, ellentmondásos formulák, kielégíthető formulák
•	Logikai kalkulus, levezethetőség

13. előadás+szeminárium: Matematikai logika alapjai/III
•	klóz, prenex forma, Skolem-normálforma
•	Herbrandt univerzum, Herbrandt tétel
•	Illesztő helyettesítés (unifikáció)

14. előadás+szeminárium: Matematikai logika alapjai/IV
•	A rezolúciós stratégia,
•	Cáfolati gráf, válaszadási gráf
•	Rezolúciós stratégiák

VII.	Az értékelés módja:
Az ellenőrzés során (szemináriumi aktív tevékenységek, zárthelyi dolgozat íratása esetében) követjük, hogy a hallgatók hogyan  sajátították el a logikai alapfogalmakat és azok alkalmazásanak módjait. A vizsga formája: írásbeli dolgozat (70%). A jegybe még beszámítanak: a szemináriumi tevékenységek (10%), a  zárthelyi dolgozat eredménye (20%).

VIII.	Szervezési kérdések, a különleges esetek kezelése:
A vizsgára való jelentkezés feltétele: szemináriumokon legtöbb 3 hiányzás.

IX.	Ajánlott, de nem kötelező könyvészet:
1. http://users.telenet.be/educypedia/electronics/digitallogic.htm
2. D. KNUTH: A számítógép-programozás művészete, V. 1: Alapvető algoritmusok, Műszaki Könyvkiadó, Budapest, 1987
3. D. KNUTH: A számítógép-programozás művészete, V. 2: Szeminumerikus algoritmusok, Műszaki Könyvkiadó, Budapest, 1987
4. M. CLARKE: Logic for Computer Science, ed. Addison-Wesley, 1990.
5. M. FITTING: First-order logic and Automated Theorem Proving, Ed. Springer Verlag, 1990.