Tantárgyleírás
2020.
Véges matematika2 — haladó 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): vegmat2h0_m17ea, vegmat2h0_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 | vegmat2h0_m17ea vegmat2h0_m17ga |
2 | kötelező |
Tantárgyfelelős
| 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 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.