Borromeo gyűrűk
BSc Matematika Alapszak
Tantárgyleírás
2017.

Véges matematika1 — 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): vegmat1h0_m17ea, vegmat1h0_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 vegmat1h0_m17ea
vegmat1h0_m17ga
1 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ó.
  • 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ó.

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.