Kombinatorika ea. + gyak. (tanárszakosoknak), 2023/2024 tavasz

Szerda 14:00-16:00, Grünwald Géza terem

KÖVETELMÉNYEK

A gyakorlaton és az előadáson is 50-50 pont szerezhető.

A gyakorlaton 30 pontot lehet szerezni a két zárthelyi dolgozaton (15+15 pont), melyek időpontjai: március 27. és május 15. A vizsgaidőszak első hetében az egyik zh javítható/pótolható. Ezenfelül 12 gyakorlaton adok házi feladatokat, 2-2 pont értékben, a következő órán kell írásban benyújtani a megoldásokat. Az így szerzett 12 házifeladat-pontból a 10 legjobb lesz figyelembe véve, vagyis maximum 20 pont gyűjthető összesen házi feladatokkal.

Az előadásvizsga egy rövid írásbeli beugróval kezdődik, mely átfogó módon teszteli a tananyag fogalmainak és tételeinek ismeretét (bizonyítások nélkül), akár példákon keresztül. Amennyiben a beugróban komoly hiányosságokra derül fény, az érdemjegy szóbeli vizsga nélkül elégtelen. A beugró után egy tételhúzásos szóbeli vizsga következik, írásbeli felkészülés után. A vizsgát egy 0 és 50 közötti pontszámmal értékelem. (A hiányosságok 0 pontos vizsgát eredményeznek.) A vizsgán megszerzett pontszámhoz hozzáadódik a gyakorlatról hozott pontszám, és kialakul az érdemjegy:
  0 – 49:   elégtelen
50 – 62:   elégséges
63 – 75:   közepes
76 – 87:   jó
88 – 100: jeles

A félév folyamán mind az előadáson, mind a gyakorlaton pluszpontokat is lehet gyűjteni órai munkával, szorgalmi feladatok megoldásával, illetve érdemi hozzászólással/hibajelzéssel. A pluszpontok hozzáadódnak a fent kialakult összpontszámhoz. Továbbá a tételsorban szerepelnek olyan elemek is, amelyek ismerete pluszpontokat jelent a szóbeli vizsgán.

TEMATIKA / TÉTELSOR

A lila szín a nehezebb anyagrészeket jelöli, ezeket csak a jeles érdemjegyet megcélzó hallgatóktól kérdezhetem (a beugróban biztosan nem fognak szerepelni).
A zöld színű részek nem tartoznak a vizsgaanyaghoz: ha a törzsanyag jól ment (!), akkor ezen kiegészítő részek ismerete pluszpontot ér.

1. Alapelvek (prezentáció): Bijekció. A kombinatorika három alapelve (bijekciós, összeadási, szorzási). Egy (véges) halmaz elemszámának precíz definíciója. Zárójelfelbontás és a direkt szorzat kapcsolata. Skatulyaelv, általánosított skatulyaelv.
2. Részhalmazok (prezentáció): Hatványhalmaz. Részhalmaz karakterisztikus vektora. Egy n elemű halmaz részhalmazainak száma. Páros/páratlan elemszámú részhalmazok száma. Kettős leszámlálás (példával, akár későbbi előadásról / gyakorlatról is).
3. Binomiális együtthatók (prezentáció): A binomiális együtthatók definíciója. A Pascal-háromszög és alaptulajdonságai (rekurzió a binomiális együtthatókra; szimmetria; egy sor elemeinek összege). Képlet az (nk) binomiális együtthatóra. Binomiális együtthatók összehasonlítása. Binomiális tétel. SZORGALMI: Binomiális együtthatók paritása. (Bizonyítás ITT [9.tétel], a Pascal-háromszög Sierpiński-háromszögszerű ,,paritástérképének'' magyarazáta pedig ITT.)
4. Multihalmazok (prezentáció): Multihalmazok szemléletes jelentése. Multihalmazok precízebben + alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai). Részmultihalmazok száma. Egy n elemű alaphalmaz feletti k elemű multihalmazok száma. ((nk)) mint bizonyos vektorok száma.
5. Sorbaállítások (prezentáció): Sorbaállítás definíciója. Egy n elemű halmaz sorbaállításainak száma. Stirling-formula (biz. nélkül). Multihalmaz sorbaállításai, és ezek száma. Trinomiális és multinomiális tétel.
6. Átrendezések (prezentáció): Átrendezés (permutáció) definíciója. Egy n elemű halmaz átrendezéseinek száma. Bijekciók száma két n elemű halmaz között. Ciklusok. Minden permutáció ciklusokra bomlik (a bizonyítás önállóan olvasandó el a jegyzet alapján).
7. Logikai szita (prezentáció): A szita formula. Alkalmazás: Fixpont nélküli permutációk száma (elcserélt levelek problémája).
8. Rekurziók (prezentáció): Rekurzióval definiált sorozatok (elég, ha példákat tudunk felírni). A Fibonacci-számok és Catalan-számok rekurzív definíciója. A Fibonacci-számok (egy) kombinatorikus jelentése. Catalan-számok zárt alakja (biz. nélkül). Lineáris rekurziók. Lineáris rekurziók középiskolás tárgyalása (konkrét másodrendű rekurziót meg kell tudni oldani). Lineáris rekurziók alaptétele (biz. nélkül), és alkalmazása lineáris rekurziók megoldására. Fibonacci-számok zárt alakja. SZORGALMI: Catalan-számok zárt alakjának elemi bizonyítása.

A GYAKORLAT FELADATSORAI

1. Kombinatorikus alapelvek
2. Binomiális együtthatók, polinomok
3. Multihalmazok
4. Sorbaállítások, átrendezések
5. Logikai szita
6. Rekurziók

MINTA ZH

Minta 1. zh (új)

SEGÉDANYAGOK

AJÁNLOTT IRODALOM

HASZNOS LINKEK

Főoldal