Gyakorlat
A gyakorlaton maximum 60 pont szerezhető; ebből legalább 25 pontot kell elérni a gyakorlat aláírásához, ami az előadás teljesítésének előfeltétele is.
A gyakorlati pontszám két zárthelyi dolgozat pontszámából (20+20 pont) és a házi feladatok eredményéből (10×2 pont) tevődik össze. A zárthelyi dolgozatok időpontjait a gyakorlatvezető jelöli ki, a vizsgaidőszak első hetében az egyik zh javítható/pótolható. A két zh-írós órát leszámítva minden gyakorlaton házi feladatok lesznek feladva, 2-2 pont értékben, és a következő órán kell írásban benyújtani a megoldásokat. Az így szerzett 12 házifeladat-pontból a 10 legjobb kerül beszámításra félév végén. (A házi feladatok nem javíthatók/pótolhatók.)
Ezenfelül a gyakorlaton legfeljebb 10 pluszpont gyűjthető órai munkával, illetve a szorgalmi feladatok otthoni megoldásával.
Előadás
Az előadásvizsgán maximum 40 pont szerezhető (tehát a vizsga 40%-os súllyal számít bele a végső érdemjegybe).
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: A hallgató egy kombinatorika és egy gráfelmélet tételt ismertet szóban,
írásbeli felkészülés után. (A tételhúzás után kijelölöm, hogy mely részeket kell majd jobban részletezni, és melyeket elegendő kevésbé.)
A 40 pontból legalább 15 pontot el kell érni a kurzus teljesítéséhez (alapvető hiányosságok 0 pontot eredményeznek).
E feltétel teljesülése esetén a vizsgán megszerzett pontszám hozzáadódik a gyakorlatról hozott pontszámhoz, és kialakul az érdemjegy:
0 – 50: elégtelen
51 – 62: elégséges
63 – 75: közepes
76 – 87: jó
88 – 100: jeles
A félév folyamán pluszpontokat is lehet gyűjteni az előadás alatt tett é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 zöld 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 barna 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 (a SZORGALMI címkéjűek többet, a "pluszpontért"
részek kevesebbet; az egyebek inkább csak olvasmányok).
1. Alapok: A három kombinatorikus alapelv. Bijekció. Hatványhalmaz. Részhalmaz karakterisztikus függvénye és karakterisztikus vektora. Egy n elemű halmaz részhalmazainak száma. Skatulyaelv (példával, pl. gyakorlatról). Kettős leszámlálás (példával).
2. Binomiális együtthatók: A binomiális együtthatók definíciója. A binomiális együtthatók rekurzív kiszámítási módja.
A Pascal-háromszög és alaptulajdonságai (szimmetria, egy sor elemeinek összege). Képlet az (nk) binomiális együtthatóra. Binomiális tétel.
Páros/páratlan elemszámú részhalmazok száma (II. pont itt, vagy 1. gyakorlat).
SZORGALMI: Páros/páratlan elemösszegű k elemű részhalmazok (9. oldal, 4. feladat).
3. Polinomok, formális hatványsorok: Formális hatványsorok és polinomok definíciója, generátorfüggvények. Alapműveletek (összeadás és szorzás). Formális hatványsorok műveleti tulajdonságai (nem kell betanulni; számolni kell tudni formális hatványsorokkal), többtényezős szorzat.
Formális hatványsor fokszáma, osztás, egész kitevős hatványozás.
Az 1/(1-x) formális hatványsor. Deriválás. Kompozíció.
Az 1/(1-x)2 formális hatványsor.
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása
(az általános elméletet nem fogom kérdezni, konkrét polinom/polinom alakú hatványsor együtthatóit tudjuk kiszámolni lineáris rekurzió megoldásakor).
SZORGALMI: n-edik gyök, tört kitevőjű hatványok, Newton-formula (ld. Formális hatványsorok II. prezentáció vége).
4. Multihalmazok: Multihalmazok precíz definíciója + alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai). Multiplicitásvektor.
Részmultihalmazok száma. Az ((nk)) számok definíciója. Rekurzió az ((nk)) számokra (lásd gyakorlat).
Az ((nk)) számok pontos értéke. Az ((nk)) számok generátorfüggvénye.
5. Sorbaállítások: Sorbaállítás definíciója. Egy n elemű halmaz sorbaállításainak száma. Stirling-formula (biz. nélkül). Inverzióban álló elempár. Inverziószám definíciója és gyors kiszámítási módja.
Az i(n,k) számok definíciója és egyszerű tulajdonságai. Az i(n,k) számok rekurzív kiszámítási módja és generátorfüggvénye.
Multihalmaz sorbaállítása, és a sorbaállítások száma. Trinomiális és multinomiális tétel (bizonyítás: ld. gyakorlat). SZORGALMI: Páros és páratlan permutációk.
6. Átrendezések: Bijekciók száma két n elemű halmaz között. Átrendezések (permutációk) definíciója. Egy n elemű halmaz átrendezéseinek száma. Ciklusok. Minden permutáció ciklusokra bomlik.
Az [nk] számok definíciója, rekurzív kiszámítási módja és generátorfüggvénye (utóbbi biz. nélkül).
SZORGALMI: Az [nk] számok generátorfüggvényének szép levezetése.
7. Logikai szita: A szita formula. Alkalmazások: Fixpont nélküli permutációk száma (elcserélt levelek problémája); szürjektív leképezések száma (ld. gyakorlat).
8. Rekurziók: Rekurzióval definiált sorozatok (elég, ha példákat tudunk felírni).
Fibonacci-számok rekurzív definíciója. Lineáris rekurziók, és megoldásuk generátorfüggvény-módszerrel
(általam adott lineáris rekurziót kell tudni megoldani).
Fibonacci-számok zárt alakja. Lineáris rekurziók alaptétele (biz. nélkül), és alkalmazása
lineáris rekurziók megoldására. Fibonacci-számok kombinatorikus definíciója.
Elméleti segédlet a generátorfüggvény együtthatóinak kiszámolásához:
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása.
Kiegészítő olvasmány: Lineáris rekurziók középiskolás tárgyalása (avagy "honnan jön" a karakterisztikus polinom).
SZORGALMI: Catalan-számok (ld. Rekurziók prezentáció vége). SZORGALMI: Catalan-számok zárt alakjának elemi bizonyítása.
9. Gráfelméleti alapok: Egyszerű gráf, (általános) gráf definíciója; hurokél, párhuzamos él. Csúcs fokszáma. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata). Részgráf; feszítő és feszített részgráfok.
Séta, vonal, út. Összefüggőség. Gráfok izomorfiája. Egyszerű gráf komplementere. Reguláris gráfok. Néhány speciális gráf: teljes gráf, út gráf, kör gráf.
Hasznos ismerni: Irányított gráfok (2. oldal vége).
10. Euler-vonal: Euler-vonal definíciója (nyílt és zárt). Euler-tétel.
A történelmi példa: Königsberg (ma Kalinyingrád) térképe Euler idejében, és a gráf.
11. Hamilton-út, Hamilton-kör: Kör. Hamilton-út, Hamilton-kör definíciója.
Dirac-tétel. Ore-tétel.
Egy (nem mindig alkalmazható) módszer annak igazolására, hogy a gráfban nincs Hamilton-kör/út.
Érdekesség: Hamilton játéka.
12. Összefüggőség, fák: Összefüggőség. Komponensek.
Fák ekvivalens definíciói (hasznos minél többet ismerni, de elég annyi, amennyi előadáson volt).
Feszítőfák. Levelek. Ághajtás operáció, fák "struktúratétele" (fák jellemzése ághajtás operációkkal). A fa éleinek száma, és egyszerű következményei (összefüggő gráfok, körmentes gráfok élszámáról). Erdők.
Gyökeres fák és lerajzolásaik.
13. Csúcsszínezések I.: Páros gráfok definíciója és jellemzésük páratlan körökkel. Jó színezés és kromatikus szám definíciója.
Klikkek, ω(G) paraméter. Független ponthalmazok, α(G) paraméter.
A kromatikus szám alsó becslése az α(G) paraméter (és a csúcsszám) segítségével.
A χ(G) és ω(G) paraméterek kapcsolata.
Nagy kromatikus számú háromszögmentes gráfok (lásd 3. konstrukció itt).
14. Csúcsszínezések II., síkgráfok: Kromatikus szám felső becslése a maximális fokszám segítségével, mohó színezési algoritmus (ebben az illusztrációban
számok helyett igazi színekkel színezünk; a színpreferencia szerint 1 = világoszöld, 2 = világoskék, stb.).
Síkgráfok definíciója. Térképszínezési probléma, négyszín-tétel (biz. nélkül).
A két alappélda nem síkgráfokra (bizonyítás nélkül). Gráfok felosztása. Kuratowski-tétel.
SZORGALMI: Euler-formula.
15. Párosítások: Lefogó ponthalmazok, τ(G) paraméter. Párosítások, teljes párosítások, ν(G) paraméter. A ν(G) és τ(G) paraméterek kapcsolata.
Párosítások páros gráfokban: Kőnig-tétel (biz. nélkül). Kőnig-akadály (mit akadályoz meg, és miért; egy Kőnig-akadály hány párosítatlan pontot garantál A-ban).
Kőnig—Hall-tétel (a nehéz irány bizonyítása nélkül), Kőnig—Frobenius-tétel. Egy alkalmazás: teljes párosítás létezése reguláris páros gráfokban. Kőnig-formula (biz. nélkül).
SZORGALMI: Párosítások általános gráfokban: Tutte-akadály (mit akadályoz meg, és miért), Tutte-tétel kimondása.
Kiegészítő segédanyag: Az órai anyagnál bővebb jegyzet párosításokról (a kihagyott bizonyításokkal együtt).
16. Extremális gráfelmélet: Turán-gráfok. Turán-tétel (biz. nélkül). Mantel-tétel.
SZORGALMI: A Turán-tétel bizonyítása.
17. Ramsey-elmélet: Ramsey-tétel. Az R(k) Ramsey-számok. R(3) pontos értéke (a kapcsolódó feladat megoldásával együtt). R(k) felső becslése (ami a Ramsey-tétel bizonyításából kijön).
R(k) alsó becslése (Erdős Pál tétele, SZORGALMI: a bizonyítás vázlata).
Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR (sok elhangzott definíció benne van)
A fő segédanyag a korábbi előadó, Hajnal Péter internetes jegyzete a kurzushoz: 2016/2017-es tanév
A tanárszakos kurzushoz készült jegyzet kevesebb anyagot tartalmaz, viszont olvasmányosabb: 2014/2015-ös tanév
Kivetített prezentációk: Formális hatványsorok II. (3. és 6. előadás),
Logikai szita (5. előadás),
Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása (6. előadás),
Rekurziók, Fibonacci-számok, Catalan-számok (6-7. előadás),
Euler-tétel (8. előadás), Dirac-tétel (9. előadás),
Síkgráfok (11-12. előadás).
Euler-vonal: #1 (zárt),
#2 (zárt),
#3 (nyílt),
#4 (nyílt).
Hamilton-út: #1, #2.
Hamilton-kör: #1, #2, #3.
Komponensek: #1 (gráf 4 komponenssel),
#2 (gráf 3 komponenssel),
#3 (gráf 3 komponenssel).
Fa: #1, #2, #3.
Feszítőfa: #1, #2.
Gyökeres fa lerajzolása: #1 (gyökér: 'a'), #2.
Síkgráf duálisa: #1, #2, #3, #4.
A duális gráf az eredeti gráf lerajzolásától is függ: #1.
Jó (csúcs)színezés: #1, #2, #3.
Térképszínezési probléma / négyszíntétel szemléltetése: #1, #2.
Párosítás: #1 (nem teljes), #2 (teljes),
#3 (páros gráf egy párosítása), #4 (páros gráf egy A-t lefedő párosítása),
#5 (páros gráf egy teljes párosítása).
Kőnig-akadály: #1, #2. Lefogó ponthalmaz: #1.
Turán-gráf: #1 (T13,4, T14,4, T13,2 és T14,3), #2 (T7,3).
Ramsey-elmélet: #1 (K6 egy piros-kék élszínezése, és a kialakuló monokromatikus háromszögek).
A képek többségét más oldalakról linkeltem (az URL-ből kiolvasható/megkereshető a forrás).
Hajnal Péter: Összeszámlálási problémák (Polygon Jegyzettár)
Hajnal Péter: Gráfelmélet, II. kiadás (Polygon Jegyzettár)
Lovász László: Kombinatorikai problémák és feladatok (Typotex, ingyenesen olvasható az interneten)
Bóna Miklós: Introduction to Enumerative Combinatorics (McGraw-Hill)
Reinhard Diestel: Graph Theory (Springer-Verlag, ingyenesen olvasható az interneten)
Richard P. Stanley: Enumerative Combinatorics, Vol. 1-2 (Cambridge University Press)
Benny Sudakov: Graph Theory (internetes jegyzet)
The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"
⇦ | Főoldal |