Az ELTE IK Programtervező Informatikus BSc képzésén belüli Diszkrét Matematika tantárgy jegyzetei a teljes félévből.
Frissítés
A jelenlegi legújabb, azaz 2011/2012 I. féléves Dimat jegyzeteket (kidolgozott definíciók, tételek + bizonyítások) megtalálod a Diszkrét Matematika kategóriában!
Diszkmat vizsga kérdéssorok
2010. január 09.
Az eddigi vizsgák kérdéssorai, tehát ezeket ebben a félévben írtuk (írták), ez nem csak gyakorlás. Állítolag a tanár úr programmal generálja a kérdéssorokat, de valahogy ezt személy szerint kétlem, mert a papírok tetején volt oldalszám, mintha egy előre elkészített vizsgadolgozat-gyűjteményből származnának… Ez csak összeesküvés-elmélet, de ki tudja, érdemes majd a következő félévekben ezeket azért megtanulni, biztos, ami biztos alapon, hátha pont az egyik listát kapja valaki. A mázlista…
Utólag beszrúrtam még ide egy 0. kérdéssort is, de abból csak a bizonyítás részt ismerem. Egyébként a valódi vizsgaalkalmak szerinti számozás alapján (-1)-ről kellene kezdenem a számozást, mert dec. 17-én volt az első vizsgaalkalom, de most már mindegy, marad úgy, ahogy kezdetben írtam. 🙂
0. (dec. 21.)
Bizonyítások
1. Mit állíthatunk monoton növekvő függvény inverzéről? Bizonyítsa be az állítását!
2. Fogalmazza meg az Archimédészi tulajdonságot! Mi a kapcsolata a felső határ tulajdonsággal? Bizonyítsa be az állítását!
3. Bizonyítsa be a Zm gyűrű tulajdonságait leíró tételt!
I. (jan. 4.)
Kérdések
1. Mondjon legalább három példát predikátumra!
2. Definiálja halmazok különbségét, szimmetrikus differenciáját és komplementerét!
3. Mi az, hogy kisebb, nagyobb, megelőzi, követi?
4. Igaz-e, hogy az identikus leképezés mindig szürjektiv?
5. Hogyan definiálunk műveleteket függvények között?
6. Igaz-e, hogy ha X tetszőleges halmaz, akkor X hatványhalmaza, az unióval egy csoport?
7. Definiálja az egész számokat az összeadással és fogalmazza meg az egész számok összeadásának tulajdonságait leíró tételt!
8. Fogalmazza meg a valós számok egyértelműségét leiró tételt!
9. Milyen algebrai struktúrát alkotnak a kvaterniók?
10. Definiálja az ismétléses variációk fogalmát! Mit mondhatunk egy véges halmaz összes ismétléses variációinak számáról?
11. Ismertesse a bővitett euklideszi algoritmust!
12. Ismertesse az RSA eljárás felhasználását bizonyitványok kiállitására!
Bizonyitások
13. Fogalmazza meg a halmazok metszetének kommutativitását, asszociativitását és idempotenciáját és bizonyítsa be!
14. Fogalmazza meg gyűrűben a nullával való szorzás tulajdonságait és az előjelszabájt és bizonyítsa be!
15. Fogalmazza meg a polinomiális tételt és bizonyítsa be!
II. (jan. 7.)
Kérdések
1. Mikor van egy változó egy kvantor hatáskörében?
2. Definiálja két halmaz Descartes-szorzatát!
3. Definiálja legkisebb és a legnagyobb elem fogalmát!
4. Mi a kapcsolat függvények és ekvivalenciarelációk között?
5. Fogalmazza meg a Peano-axiómákat!
6. Definiálja a szimmetrikus csoport fogalmát!
7. Ismertesse egész számok többletes ábrázolását!
8. Definiálja a bővített valós számokat!
9. Igaz-e, hogy bármely kvaternió bármely komplex számmal felcserélhető?
10. Fogalmazza meg a polinomiális tételt!
11. Hogyan határozhatók meg természetes számok esetén az osztók, a legnagyobb közös osztó és a legkisebb közös többszörös a prímtényezős felbontás segítségével?
12. Adjon egyszerű példát additív, multiplikatív, teljesen additív és teljesen multiplikatív számelméleti függvényekre!
Bizonyítások
13. Bizonyítsa be, hogy binér relációk kompozíciója asszociatív!
14. Fogalmazzon meg szükséges és elégséges feltételt arra vonatkozóan, hogy egy integritási tartomány rendezett integritási tartomány legyen, és bizonyítsa be az állítást!
15. Mi a kapcsolat az egységek és az asszociáltak között? Bizonyítsa be állítását!
III. (jan. 11.)
Kérdések
1. Sorolja fel a logikai jeleket!
2. Fogalmazza meg a halmazok komplementerének alaptulajdonságait!
3. Definiálja az intervallumokat és adja meg a kapcsolódó jelöléseket!
4. Definiálja a permutáció fogalmát!
5. Adjon példát műveletekre függvények között!
6. Igaz-e, hogy ha X tetszőleges halmaz, akkor (ró(x),) egy félcsoport?
7. Definiálja az egész számok szorzását, és fogalmazza meg az egész számok szorzásának tulajdonságait leíró tételt!
8. Definiálja a bővített valós számokat!
9. Adja meg a komplex számok beágyazását kvaterniókba!
10. Fogalmazza meg a binomiális tételt!
11. Mely tétel alapján számolhatjuk ki véges sok egész szám legnagyobb közös osztóját prímfelbontás nélkül?
12. Definiálja a számelméleti függvény, az additív számelméleti függvény és a teljesen additív számelméleti függvény fogalmát!
Bizonyítások
13. Fogalmazza meg az unió és a metszet disztributivitását és bizonyítsa be!
14. Fogalmazza meg gyűrűben az egész együtthatóval való szorzás tulajdonságait és bizonyítsa be!
15. Fogalmazza meg a logikai szita formulát és bizonyítsa be!
IV. (jan. 14.)
Kérdések
1. Mondjon két példát nyitott formulára!
2. Mondjon binér relációra 3 példát! (ilyen nincs a tételsorban)
3. Adjon meg olyan részbenrendezett halmazt, amelyben több minimális elem van!
4. Mikor nevezünk egy függvényt szigorúan monoton növekedőnek illetve szigorúan monoton csökkenőnek?
5. Definiálja a számjegyeket!
6. Fogalmazza meg a természetes számokra a kisebb egyenlő reláció és a műveletek kapcsolatát leiró tételt!
7. Definiálja egy csoportban az egész kitevős hatványozást és fogalmazza meg egy olyan tulajdonságát, amely csak felcserélhető elemekre érvényes!
8. Ismertesse valós számok kerekitési módjait!
9. Definiálja kvaternió valós és képzetes részét (és konjugáltját, ez nem volt ott)!
10. Definiálja a természetes számok körében az oszthatóságot és adja meg a jelölését!
11. Hogyan számolhatjuk ki véges sok egész szám legkisebb közös többszörösét primfelbontás nélkül?
12. Fogalmazza meg az Euler-féle fi függvény kiszámitására vontkozó tételt!
Bizonyítások
13. Fogalmazza meg az ekvivalenciareláció és az osztályozás kapcsolatát és bizonyitsa be!
14. Definiálja a racionális számok halmazát az összeadással, bizonyitsa be, hogy az összeadás kompatibilis az osztályozással, és az összeadással a racionális számok halmaza Abel-csoport!
15. Mi a kapcsolat Z-ben a primelemek és az irreducibilis elemek között? Bizonyitsa állitását!
V. (jan. 18.)
Kérdések – nem szószerinti idézés és nem pont ilyen sorrendben, de tartalmilag ugyanezek
1. Definiálja halmazok egyenlőségét, és írja le milyen tulajdonságokkal rendelkezik!
2. Definiálja az egység fogalmát (oszthatóság)!
3. Definiálja a rendezett integritás tartományt!
4. Ágyazza be a valós számok testét a komplex számok testébe!
5. Fogalmazza meg a Schröder-Bernstein tételt!
6. Definiálja binér relációk kompozicióját, lehet-e a kompozició üres?
7. Definiálja az összeadást természetes számokon!
8. Milyen összefüggéseket ismer egy függvény és a halmazműveletek között?
9. Írja le a komplemens ábrázolást!
10. Igaz-e hogyha egy parciálisan rendezett halmaz részhalmazának az alsó határ eleme, akkor ez minimális elem is?
11. Mit értünk véges és végtelen halmazon?
12. Adja meg a hatványozás egy olyan tualjdonságát, ami csak felcserélhető elemekre érvényes!
Bizonyítások
13. Bizonyítsa a (Kis-)Fermat tételt!
14. Definiálja valós számokon az alsó egészrészt, és a felső egészrészt, és bizonyítsa hogy egyértelmű!
15. Bizonyítsa be hogyha n eleme N akkor n+ nem egyenlő n és hogy ha n nem egyenlő 0 akkor létezik m eleme N hogy m+=n!
VI. (jan. 25.)
Kérdések
1. Írja le a rendezetlen pár fogalmát! Milyen jelölés kapcsolódik hozzá?
2. Mit jelent az, hogy egy reláció szigorúan antiszimmetrikus, reflexív illetve irreflexív? Ezek közül mi az, ami csak a reláción múlik?
3. Adjon példát jólrendezett halmazra!
4. Definiálja tetszőleges indexelt halmaz család Descartes-szorzatát és ismertesse a kapcsolódó jelöléseket!
5. Definiálja a baloldali semleges elem, a jobboldali semleges elem és a semleges elem fogalmát!
6. Definiálja logikai függvény diszjunktív illetve konjuktív normál alakját!
7. Adja meg Z-nek Q-ba való beágyazását és fogalmazza meg a beágyazás tulajdonságait!
8. Fogalmazza meg komplex számok abszolút értékének tulajdonságait!
9. Mit mondhatunk véges halmazban minimális és maximális elem létezéséről?
10. Definiálja egységelemes integritási tartományban a prímelem és az irreducibilis elem fogalmát! Mi a kapcsolat a két fogalom között?
11. Definiálja az Euler-féle fi függvényt!
12. Definiálja a megszámlálható végtelen és a megszámlálható fogalmát!
Bizonyítások
13. Fogalmazza meg és bizonyítsa be a természetes számok szorzásának alaptulajdonságait kimondó tételt, a kommutativitást kivéve!
14. Bizonyítsa be, hogy bármely n eleme N-re {1, 2, . . . , n} bármely valódi részhalmaza ekvivalens egy m < n természetes számra {1, 2, . . . ,m}-mel!
15. Ismertesse az RSA eljárást részletes indoklással!
VII. (jan. 28.)
Bizonyítások
1. Mit állíthatunk a monoton növekedő függvények inverz függvényéről? A megfogalmazott állítást bizonyítsa be!
2. Van-e olyan racionális szám, amelynek a négyzete 2? Bizonyítsa be állítását!
3. Fogalmazza meg az egész számok kongruenciájának egyszerű tulajdonságait és bizonyítsa be azokat!
Beugrók és bizonyítások kidolgozva
2010. január 09.
Borsos Tominak hála az alábbi szuper segédanyaghoz!
A kidolgozás a szintén csatolt vizsgatematikát követi, első része a beugrók (azaz a kis tételek) kifejtése, második része pedig a bizonyítások kidolgozása. A dokumentum Tomi szabadidejétől függően frissül, tehát akár naponta is bővülhet újabb részekkel. A fájlnévben szereplő dátum alapján láthatjátok mindig, hogy melyik verzió az aktuális.
Tulajdonképpen az ebben a menüpontban szereplő definíció gyűjtemény aktualizált, bővített változata kiegészítve a bizonyítás résszel. Letöltése erősen ajánlott, de ne feledjétek, hogy még nem végleges, frissülni fog többször is!
Halmazelmélet
2009. október 24.
Halmazelmélet témakörhöz találtam egy szemléletes ábrákkal ellátott jegyzetet a Szegedi Tudományegyetem egyik weblapján. A Bevezetés a matematikába c. könyv 2006-os kiadása elég szegényes ábrákban, remélem segít valamennyit ez a jegyzet a témakör megértésében.
A gyakorlatok anyaga
2009. szeptember 22.
A diszkmat gyakorlati órákon az alábbi feladatlapot oldjuk meg, óráról-órára az előző előadásnak megfelelő sebességgel. A tárgyi honlapon fent van, de mostantól itt is, ha esetleg valakinek elveszne, megrongálódna, esetleg véletlenül felgyulladna.
Definíció gyűjtemény
2009. szeptember 21.
A metros oldalán fent lévő diszkrét matematika kidolgozott kérdéssor nekem nem tetszik, mert a kérdések nincsenek megszámozva és a speciális jelek valamiért el vannak csúszva a szöveghez képest. Inkább az alábbi jegyzetet ajánlom (dyn-féle), ami nekem jobban tetszik és tartalmilag (szerintem) megegyezik a nem olyan széppel.
4