Diszkrét matematika előadás-anyag

[G.Á]

A Diszkrét matematika kurzus előadásfóliái az alább elérhetőek.

Mivel az előadás anyagait folyamatosan készítem, könnyen előfordulhat, hogy maradtak benne elírások.
A kurzus nem minden témaköréhez készítek fóliákat.
Az anyag az órai magyarázattal és a gyakorlatok anyagával együtt használandó.
Jegykialakítás 50%-ban a ZH-k, 50%-ban a szóbeli vizsga alapján történik.

Témakörök:

Kombinatorika

1. A diszkrét matematika tárgya, bevezetés a kombinatorikába, a kombinatorika alapelvei 1.fólia
2. Permutációk, kombinációk, variációk (órai jegyzet)
3. Binomiális és polinomiális tételek (órai jegyzet)
4. Partíciók alapjai 4.fólia
5. A klasszikus kombinatorikai feladatok csoportosítása 5.fólia
6. Logikai szita-formula és alkalmazásai (órai jegyzet)
7. Generátorfüggvény-módszer 7.fólia
8. Rekurziók megoldása (órai jegyzet)

Gráfelmélet
9. Bevezetés a gráfelméletbe 9.fólia
10. Euler-körök, nyírt és zárt utak Szalkai-jegyzet Segéd-jegyzet
11. Fák és alkalmazásaik Szalkai-jegyzet/1 Szalkai-jegyzet/2
12. Hamilton körök és utak Szalkai-jegyzet Segéd-jegyzet Feladatok megoldással
13. Gráfok mátrixai, algoritmusok Szalkai-jegyzet/1 Szalkai-jegyzet/2
14. Páros gráfok Szalkai-jegyzet Segéd-jegyzet Segéd-jegyzet 2
15. Síkgráfok Szalkai-jegyzet Segéd-jegyzet
16. Gráfok színezése Szalkai-jegyzet

Számelmélet
17. Adatkezelési eljárások, bevezetés a számelméletbe (órai jegyzet)
18. Oszthatóság és tulajdonságai, maradékos osztás tétele. Legnagyobb közös osztó és tulajdonságai, előállítása lineáris kombinációként. (órai jegyzet)
19. Euklideszi algoritmus, lineáris diofantoszi egyenletek. (órai jegyzet)
20. Legkisebb közös többszörös, prímszámok, törzstényezős felbontás, számelmélet alaptétele. (órai jegyzet)
21. Kongruenciák és tulajdonságai, lineáris kongruenciák és kongruencia-rendszerek megoldása. (órai jegyzet)
22. Kínai maradéktétel. Maradékrendszerek. (órai jegyzet)
23. Euler-függvény, Euler tétele, Fermat tétele, gyengén multiplikatív számelméleti függvények.
24. RSA titkosírás.

[G.Á]

A félév úgy alakult, hogy az utolsó két témakörre (számelméleti függvények, RSA titkosírás) már nem jutott idő. Ezeket vizsgán nem fogom számonkérni.

A vizsga két részből áll: A beugró írásbeli dolgozat, mely három feladatból áll. A három feladat közül legalább kettőt hiba nélkül meg kell tudni oldani. Ennek teljesítése esetén a vizsgázó két tételt húzhat, melyeket írásban kidolgozhat, majd szóbeli magyarázattal kiegészítve prezentál.

A jegy kialakítása 50%-ban a vizsga értékelésével, 50%-ban pedig a félév közben megírt ZH-k pontszáma alapján történik.
A beugró dolgozatban elért pontszám nem kerül beszámításba.

A vizsgatételek:
1. Összeszámlálási alapelvek, teljes indukció és alkalmazásai. Permutációk, kombinációk, variációk fogalma és elemi példák.
2. Binomiális- és polinomiális együtthatók és tételek, és alkalmazásuk
3. Partíciók fogalma, logikai szitaformula és alkalmazások (szürjektív leképezések száma vagy elcserélt levelek problémája)
4. Rekurzív sorozatok, lineáris rekurziók általános megoldása
5. Generátorfüggvények fogalma és elemi alkalmazásai
6. Gráfok alapfogalmai (irányítottság, hurokél, séta, kör, fokszám, gráfok mátrixa, részgráf)
7. Gráfok összefüggősége, komponensek, tintacsöppentős algoritmus
8. Euler séták és Hamilton körök
9. Fák és jellemzésük, fák alkalmazásai
10. Páros gráfok (párosítások, lefogó ponthalmazok, teljes párosítás)
11. Síkgráfok (síktérképek, Euler és Kuratowski tétele)
12. Gráf színezése, kromatikus szám, ötszíntétel, négyszíntétel
13. Oszthatóság, maradékos osztás tétele. Legnagyobb közös osztó és tulajdonságai, Euklideszi algoritmus, lineáris diofantoszi egyenletek.
14. Legkisebb közös többszörös, prímszámok, törzstényezős felbontás, számelmélet alaptétele. Kongruenciák és tulajdonságai, lineáris kongruenciák és kongruencia-rendszerek megoldása.