BSc Matematika Alapszak
Tantárgyleírás
2013.

Véges matematika2 — haladó változat
Óraszám
ea/gy
Kredit
ea/gy
Számonkérés Szakirány Tárgykód
ea/gy
Ajánlott
félév
Státusz
2 + 2 2 + 3 kollokvium +
gyak. jegy
közös mm1c1vm2
mm1c2vm2
2 kötelező
tanári minor mm1c1vm2
mm1c2vm2
4 kötelező
Erős Gyenge előfeltételek
Gyakorlat
Erős:
Véges matematika1E (mm1c1vm1)
Előadás
Gyenge:
a gyakorlat
Megjegyzések
  • 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 feladatmegoldással.
Irodalom
  • Katona Gyula, Recski András, Szabó Csaba: A számítástudomány alapjai. Typotex, 2004.
  • 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). Az alternáló utak módszere.
  • Többszörös összefüggőség, kétszeresen összefüggő gráf jellemzése körökkel. 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: a karakterisztikus egyenlet szerepe.
  • Séták a rácspontokon, tükrözési elv, Catalan-számok (sor a pénztárnál), bolyongás a számegyenes rácspontjain.
  • A Ramsey-tételkör immár részletesebben: Az R(k,l) és R(3,3,...,3) Ramsey számok becslése. Euklideszi Ramsey-tételek, a sík színezése 3 illetve 9 színnel.
  • Halmazrendszerek kombinatorikája: a Sperner tétel (kapcsolat párosításokkal: első bizonyítás) és a LYM egyenlőtlenség (ebből második biz.). Az Erdős-Ko-Rado tétel. A De Bruijn-Erdős tétel. Extremális gráfok újra: négyszöget nem tartalmazó gráfok, felső becslés az élszámra.
  • Szabályos kombinatorikai struktúrák: véges síkok. Konstrukció a modulo p maradékosztály-test felett. Véges síkok és négyszögmentes gráfok kapcsolata, alsó becslés az élszámra. Véges síkok és a De Bruijn-Erdős tétel.