MA1243d vizsgatematika
2008/09 II. félév


  1. kombinatorikai alapfeladatok:  ismétléses variációk, ismétlés nélküli variációk, ismétlés nélküli kombinációk, binomiális együtthatók és tulajdonságai, Pascal-háromszög, ismétléses kombinációk
  2. rendezett osztályozás, ismétléses permutációk, multinomiális együtthatók, polinomiális tétel, binomiális tétel 
  3. szita-formula és speciális alakja, alkalmazások: szürjektív leképezések számára vonatkozó állítás, olyan ismétléses kombinációk száma, amelyben az egyes elemek előfordulásának száma maximalizálva van, elcserélt levelek problémája (derangement-ek)
  4. néhány ismert rekurzív sorozat (Fibonacci-sorozat, Hanoi-torony, sík felosztása általános helyzetű egyenesekkel), konstans együtthatós homogén és inhomogén lineáris egyenletrendszerek, tulajdonságok, karakterisztikus egyenlet, próbafüggvény módszere, generátorfüggvény módszer
  5. irányítás nélküli gráfok, alapfogalmak (hurokél, séta, út, kör, pont fokszáma, részgráf, komponens, összefüggő gráfok), fokszámok összegére vonatkozó állítás, fák és jellemzésük, egyszerű gráfok, tintacsöppentős algoritmus komponensek meghatározására
  6. nyílt és zárt Euler-vonal, Euler-gráf, nyílt és zárt Euler-vonal létezésére vonatkozó állítások, vágóél, Fleury-algoritmus, Hamilton-kör, szükséges feltétel Hamilton-kör létezésére, Dirac tétele
  7. páros gráf, páros gráf jellemzésére vonatkozó tétel, párosítás, teljes párosítás, lefogó ponthalmaz, ν(G) és τ(G), Kőnig tétele, Magyar módszer és bizonyítása, Kőnig-Hall-kritérium, teljes párosítás létezésére vonatkozó állítás
  8. síkgráf, síktérkép, ország, határélek számának összegére vonatkozó állítás, Euler tétele, élek és csúcsok száma közötti összefüggés, K5 és K3,3 síkbarajzolhatására vonatkozó állítások, Kuratowski tétele
  9. gráf színezése, elemi állítások, kromatikus szám, 2-színezhetőségére vonatkozó állítás, elegendő állítások k-színezhetőségre, ötszíntétel, országok színezhetőségére vonatkozó állítás
  10. oszthatóság és kapcsolódó állítások, maradékos osztás tétele, legnagyobb közös osztó és tulajdonságai,  előállítása lineáris kombinációként, relatív prímek, euklideszi algoritmus, lineáris diofantoszi egyenletek
  11. legkisebb közös többszörös, prímszámok, törzstényezős felbontás, a számelmélet alaptétele, legnagyobb közös osztó és legkisebb közös többszörös előállítása törzstényezős alak segítségével, Euklidész tétele, prímszámok eloszlása
  12. kongruenciák és tulajdonságai, lineáris kongruenciák és kongruencia-rendszerek megoldhatóságára vonatkozó állítások, kínai maradéktétel
  13. teljes maradékrendszer, redukált maradékrendszer, Euler-függvény, Euler tétele, Fermat tétele, gyengén multiplikatív számelméleti függvények, Euler-függvény kiszámítása