BSc Matematika Alapszak
Tantárgyleírás
2013.
Tantárgyleírás
2013.
Véges matematika2
— intenzív 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ő |
Tantárgyfelelős
Erős | Gyenge | előfeltételek | |
---|---|---|---|
Gyakorlat | |||
Erős:
Véges matematika1E
(mm1c1vm1)
| |||
Előadás | |||
Gyenge:
a gyakorlat
|
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.