BSc Matematika Alapszak
Tantárgyleírás
2017.
Tantárgyleírás
2017.
Véges matematika1 — 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): vegmat1i0_m17ea, vegmat1i0_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 | vegmat1i0_m17ea vegmat1i0_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 a 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
- Stratégiás játékok, játékok a sakktáblán.
- Leszámlálási alapfeladatok: permutációk, variációk, kombinációk ismétlés nélkül és ismétléssel. 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 differencia-sorozatok módszere. A skatulyaelv és alkalmazásai kombinatorikai és geometriai feladatokban. Átlagolás, kettős leszámlálá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.
- 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. Séták, vonalak, utak, körök és kapcsolatuk. Végtelen gráfok, Kőnig-lemma végtelen utakról. Összefüggő és nem összefüggő gráfok: komponensek.
- Fák és erdők, élszámuk meghatározása. Euler-vonal ill. körvonal létezésének szükséges és elégséges feltétele. Irányított gráfok, turnamentek, pszeudogyőztesek. Az Euler-tétel megfelelője irányított gráfokra. 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. Hamilton-út
- létezése turnamentekben. Körmérkőzések, a teljes gráf 1-faktorokra bontásai.
- Összefüggőségi és útkereső algoritmusok: szélességi bejárás, labirintus-bejárás. Súlyozott élű gráfok: Kruskal és Dijkstra algoritmusai.
- Síkgráfok, Euler-formula, Kuratowski tétele. Gráfszínezések, kromatikus szám. Háromszög nélküli nagy-kromatikus gráf. Kapcsolat végtelen gráf és véges részgráfjai kromatikus száma között. Síkgráfok színezése: hat-, öt- és négyszín tétel.
- A Ramsey tétel gráfokra (két- és több színre.) Erdős alsó becslése. Ramsey tétele halmaz-rendszerekre. A ``Happy end'' probléma. Extremális gráfok: Maximális és maximálishoz közeli távolságok száma a síkban. Erdős-Stone-Simonovits (biz. nélkül). Becslés tiltott négyszög esetén. Véges geometriák. A Reimann-konstrukció. Felső becslés az egységtávolságok számára a síkban.