Szerda 14:00-16:00, Grünwald Géza terem
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: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.
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.
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 1. zh (új)