Borromeo gyűrűk
BSc Matematika Alapszak
Tantárgyleírás
2020.

Véges matematika2 — intenzív változat

  • Óraszám (ea+gy): 2 + 2
  • Specializáció: közös
  • Kredit (ea+gy): 3 + 3
  • Számonkérés: kollokvium + gyak. jegy
  • Tárgykód (ea, gy): vegmat2i0_m17ea, vegmat2i0_m17ga
  • Ajánlott félév: 2
  • Státusz: kötelező
Óraszám
ea(+k) + gy(+k)
Kredit
ea + gy
Számonkérés Specializáció Tárgykód
ea/gy
Ajánlott
félév
Státusz
2 + 2 3 + 3 kollokvium +
gyak. jegy
közös vegmat2i0_m17ea
vegmat2i0_m17ga
2 kötelező
Erős Gyenge előfeltételek
Gyakorlat
Erős:
Véges matematika1E (vegmat1*0_m17ea)
Előadás
Gyenge:
a gyakorlat

Megjegyzések

  • Ennél a tárgynál a gyakorlaton is legalább 50%-ban az elméleti anyag elmélyítése történik.
  • Pótlási lehetőség: Egy sikertelen zárthelyi pótolható.

A tematikát kidolgozta:

A tantárgy célkitűzése

A ma már középiskolában, sőt általános iskolában is egyre többször előforduló kombinatorikus gondolkodásmód kialakítása sok feladat-megoldással.

Irodalom

  • Brunczel András, Elekes György: Véges matematika. ELTE jegyzet.
  • Elekes György: Kombinatorika feladatgyűjtemény. ELTE jegyzet.
  • Hajnal Péter: Elemi kombinatorikai feladatok. JATE Polygon Kiadó.

Tematika

  • Az első félévi anyag fontos részeinek ismétlése: szitaformula és változatai, különféle rekurziók.
  • Minimax tételek: intervallum-rendszerekre vonatkozó feladatok. Páros gráfok és párosítások, Kőnig-Hall tétel és változatai. Kapcsolat páros gráf különféle paraméterei között (Gallai tételei). Tutte tétele párosítások létezéséről nem páros gráfban.
  • Többszörös összefüggőség, (algoritmusok is). Hálózati folyamok. A Ford-Fulkerson tétel.
  • A folyamprobléma általánosításai és alkalmazásai.
  • A mélységi keresés és alkalmazásai.
  • Lineáris rekurzióra vezető feladatok, állandó együtthatós lineáris rekurziók megoldása.
  • Séták a rácspontokon, tükrözési elv, Catalan-számok (sor a pénztárnál), bolyongás.
  • A Ramsey-tételkör: Becslések Ramsey számokra: harmadfokú konstrukció klasszikus halmazrendszer-tételekkel; tetszőleges polinomiális konstrukció az általános (moduláris) tételekből.
  • Euklideszi Ramsey tételek; a d dimenziós euklideszi egység-távolság gráfjának kromatikus száma exponenciális.
  • Halmazrendszerek kombinatorikája: Klasszikus és lineáris algebrai módszerek. A Sperner tétel és a LYM egyenlőtlenség. Erdős-Ko-Rado tétel. A De Bruijn-Erdős tétel és a Fisher-egyenlőtlenség. Páratlanfalva tétele.
  • A polinom-módszer: kettő-távolságú ponthalmazok, halmazrendszerek lefogása, l-metsző halmazrendszerek.
  • Szabályos kombinatorikai struktúrák: véges projektív és affin síkok, Latin négyzetek.