Tantárgyleírás
2020.
Véges matematika1 — normál 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): vegmat1n0_m17ea, vegmat1n0_m17ga
- Ajánlott félév: 1
- 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 | vegmat1n0_m17ea vegmat1n0_m17ga |
1 | kötelező |
Tantárgyfelelős
| Erős | Gyenge | előfeltételek |
|---|---|---|
| Előadás | ||
|
Gyenge:
a gyakorlat
| ||
Megjegyzések
- A Véges matematika1 normál, haladó és intenzív változata egymás között átjárható.
- 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:
Szükséges előismeretek
A középiskolai matematika anyag.
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
- Elekes György: Kombinatorika feladatgyűjtemény. ELTE jegyzet.
- Hajnal Péter: Elemi kombinatorikai feladatok. JATE Polygon Kiadó.
- Lovász László, Pelikán József, Vesztergombi Katalin: Diszkrét matematika. TypoTeX, 2006.
Tematika
- Stratégiás játékok.
- Leszámlálási alapfeladatok: permutációk, variációk, kombinációk ismétlés nélkül és ismétléssel. Alapötletek leszámlálási feladatok megoldására: egymás utáni döntések, ``Dobjuk ki a rosszat'' elv alkalmazásai. A többszöri megszámlálás korrekciója (``tehén-szabály''). Logikai szitaformula és változatai, mint a ``Dobjuk ki a rosszat'' elv általánosítása. Rekurziós okoskodások, Fibonacci-számok, ezekre vezető kombinatorikai feladatok. A skatulyaelv és alkalmazásai kombinatorikai és geometriai feladatokban. Átlagolás.
- Binomiális együtthatók, azonosságok binomiális együtthatókra. Kitalálós játékok: a Barkochba és változatai, hamis pénz kitalálása. Módszerek lehetetlenség igazolására: színezések, számozások.
- Gráfok fogalma, hurokél, többszörös él, egyszerű gráfok. Pontok fokszáma és élek száma közti összefüggés, és alkalmazásai. Egy speciális eset:páros gráfok, a fokszám-összefüggés páros gráfokra. Részgráfok, feszített részgráfok. Séták, vonalak, utak, körök és kapcsolatuk. Összefüggő és nem összefüggő gráfok: komponensek (a ``komponenstétel''). Fák és erdők, élszámuk meghatározása. A ``königsbergi hidak problémája'': Euler-vonal ill. körvonal létezésének szükséges és elégséges feltétele. Irányított gráfok, turnamentek. Az Euler-tétel megfelelője irányított gráfokra (biz. nélkül). Hamilton-körök és Hamilton-utak, szükséges feltétel létezésükre. Elégséges feltétel(ek) Hamilton-körök és Hamilton-utak létezésére (biz. nélk.) összefüggőségi és útkereső algoritmusok: részletesen csak a szélességi bejárás. Síkgráfok, Euler-formula (biz. nélk.), Kuratowski tétele (biz. nélk.). Síkgráfok élszáma. Gráfszínezések, kromatikus szám: kapcsolat a maximális fokszámmal és a legnagyobb teljes részgráf méretével. Síkgráfok színezése: a hatszíntétel.
- A Ramsey tétel néhány speciális esete, két és több szín esetére (csak gyakorlaton). Extremális gráfok: maximális élszám háromszögmentes gráfokra.