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

Véges matematika1 — 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 mm1c1vm1
mm1c2vm1
1 kötelező
tanári minor mm1c1vm1
mm1c2vm1
3 kötelező
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ó.
  • 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ó.
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. 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: 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. Fokszámsorozatok realizációja. 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. Fák és erdők, élszámuk meghatározása. A leghosszabb utak módszere. 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: szélességi bejárás, labirintus-bejárás. Súlyozott élű gráfok: Kruskal és Dijkstra algoritmusai. 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. Élszínezések, Vizing tétele (biz. nélk.).
  • 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.