Kombinatorika és Gráfelmélet II.
Kombinatorika és Gráfelmélet II.
VISZA 071

2012/2013. második félév
Előadó:
Időpont:
Helyszín:
Tóth Géza (email: geza_KUKAC_cs.bme.hu)
Hétfő 10.15 - 12.00
H 607


Gyakorlatok, gyakorlatvezetők:


Kurzuskód:
Gyakorlatvezető:
Időpont:
Helyszín:
T1
 Tóth Géza (email: geza_KUKAC_cs.bme.hu) Kedd 14.15 - 15.00
H 406
T2
 Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) Kedd 14.15 - 15.00
H 405A

A gyakorlatok után, 15.15-től 16.00-ig konzultációt tartunk a H 406 teremben.

Segédanyagok:

Készült néhány digitális jegyzet villamosmérnököknek és informatikusoknak, ami az anyag jelentős részét tartalmazza. Ez később még talán bővülni fog.
Katona Y. Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai, TypoTEX Kiadó, 2002, 2003.
Friedl Katalin - Recski András - Simonyi Gábor: Gráfelméleti feladatok, TypoTEX Kiadó, 2006.
Elekes György: Kombinatorika feladatgyüjtemény
Kombinatorika és Gráfelmélet I, 2011
Kombinatorika és Gráfelmélet I, 2010
Kombinatorika és Gráfelmélet I, 2009
Kombinatorika és Gráfelmélet II, 2011
Kombinatorika és Gráfelmélet II, 2012
Kombinatorika és Gráfelmélet II, 2010
Tutte tétel bizonyítása
Listaszínezés, Galvin tétel
Perfekt gráf tétel
Kuratowski-tétel, Fáry-Wagner tétel
Részben rendezett halmazok, Dilworth tétel
Síkgráfok listaszínezési száma
A súlyátrendező módszer
Az Erdős-Szekeres tétel
Erdős - De Bruijn tétel, véges síkok, C4-mentes gráfok
Catalan számok magyarul
Catalan számok angolul


Házi feladat és ZH eredmények

Tételsor


Eseménynaptár (TERV)

1. hét 2013. február 11.
Perfekt gráfok, intervallumgráfok, Perfekt gráf tétel
2013. február 12. 1. gyakorlat
2. hét 2013. február 18. Síkbarajzolhatóság, Euler-formula
2013. február 19. 2. gyakorlat
3. hét 2013. február 25. Kuratowski-tétel, Fáry-Wagner tétel
2013. február 26. 3. gyakorlat
4. hét 2013. március 4. Geometriai és absztrakt dualitás, gyenge izomorfia, Whitney tételei, ötszíntétel
2013. március 5. 4. gyakorlat
5. hét 2013. március 11. Részben rendezett halmazok, Dilworth tétel, súlyátrendező módszer
2013. március 12. 5. gyakorlat
6. hét 2013. március 18 I. Zárthelyi Kf 81, 10.15-11.45 Feladatok és javítási útmutató Eredmények

2013. március 19. 6. gyakorlat
7. hét 2013. március 25. Ramsey-tétel, Erdős-Szekeres tétel, Erdős-féle alsó becslés, a valószínűségi módszer
2013. március 26. 7. gyakorlat
8. hét 2013. április 1. Előadás elmarad (Húsvét)
2013. április 2. 8. gyakorlat
9. hét 2013. április 8. Turán-tétel, Erdős-Stone tétel, Erdős-Simonovits tétel
2013. április 9. 9. gyakorlat
10. hét 2013. április 15. Hipergráfok, Erdős-Ko-Rado tétel
2013. április 16. 10. gyakorlat
11. hét 2013. április 22. Sperner-tétel. LYM egyenlőtlenség, De Bruijn - Erdős tétel
2013. április 23. 11. gyakorlat
12. hét 2013. április 29. II. Zárthelyi Kf 81, 10.15-11.45 Feladatok és javítási útmutató Eredmények

2013. április 30. 12. gyakorlat
13. hét 2013. május 6. Generátor függvények, Fibonacci számok, homogén lineáris rekurziók
2013. május 7. 13. gyakorlat
14. hét 2013. május 13. Catalan számok (utolsó előadás)
2013. május 14. Pótzárthelyi, Feladatok és javítási útmutató 1 2 Eredmények közben 14. gyakorlat
pótlási hét 2013. május 21 kedd Konzultáció (8.00-10.00) IB 134
2013. május 22 szerda Aláíráspótló zárthelyi, (8.00-10.00), Eredmények Elővizsga, (8.00-14.00) H 607
2013. május 24 péntek Konzultáció (8.00-10.00) IB 134
1. hét 2013. május 27 hétfő Vizsga (9.00-14.00) IB 025
2013. május 29 szerda Konzultáció (8.00-10.00) IB 217.1
2013. május 30 csütörtök Vizsga (8.00-14.00) IB 025
2013. május 31 péntek Konzultáció (8.00-10.00) IB 134
2. hét 2013. június 3 hétfő Vizsga (8.00-14.00) IB 025
2013. június 7 péntek Konzultáció (8.00-10.00) IB 134
3. hét 2013. június 10 hétfő Vizsga (8.00-14.00) QBF 09
2013. június 14 péntek Konzultáció (8.00-10.00) IB 134
4. hét 2013. június 17 hétfő Vizsga (8.00-14.00) IB 025


Értékelés, tárgykövetelmények, vizsga:

Házi feladat:

Minden gyakorlaton adunk 1 vagy 2 házi feladatot, amelye(ke)t a következő gyakorlat elején kell beadni. Feladatonként legfeljebb 10 pontot adunk, de a végső pontszám nem haladhatja meg a 100 pontot. Tehát a maximális pontszám eléréséhez nem szükséges az összes feladatot beadni. A házi feladat 10% súllyal számít a végső érdemjegybe.

Zárthelyik, pótzárthelyik:

A félév során két zárthelyi lesz. Mindkét zárthelyi 6, egyenként 10 pontot érő feladatból áll, időtartama 90 perc. Elégséges osztályzat 40%-os teljesítménytől, azaz 24 ponttól jár. A félévvégi aláírás megszerzésének, azaz a vizsgára bocsátásnak az a feltétele, hogy külön-külön mindkét zárthelyi legalább elégséges legyen.

A két zárthelyi közül legalább az egyiket már az első alkalommal (pótlás nélkül) sikeresen kell megírni, és pótolni legfeljebb csak egyet lehet. Ezért a szorgalmi időszak alatt összesen egy pótzárthelyi alkalom lesz, ahol vagy az első, vagy a második (de nem mindkét) zárthelyin elért eredmény javítható vagy pótolható.

A pótzárthelyin a korábban megírt, eredményes zárthelyi javításakor az újonnan kapott pontszám lesz érvényes, kivéve, ha az eredményes zárthelyi javítása elégtelen. Ekkor a megfelelő zárthelyit az elégségeshez szükséges minimális pontszámmal (konkrétan 24 ponttal) vesszük figyelembe.

A kijavított zárthelyi és pótzárthelyi dolgozatokba betekintést biztosítunk. A zárthelyik összesen 40% súllyal számítanak a végső érdemjegybe.

Aláíráspótló vizsga:

Amennyiben valamelyik zárthelyi elsőre eredményes, ám a másik még a pótzárthelyin sem sikerül, úgy (különeljárási díj megfizetése mellett) marad még egy utolsó lehetőség a vizsgaidőszak előtti pótlási héten a mindaddig eredménytelen zárthelyi újbóli pótlására. Ez a második pótzárthelyi alkalom a TVSz-ben "aláíráspótló vizsga" néven szerepel annak ellenére, hogy ez természetesen nem valódi vizsga.

Mindez tehát azt jelenti, hogy ha valaki a két zárthelyi közül mindkettőn elégtelent ír (vagy nem jelenik meg), akkor ebben a félévben már semmilyen módon nem szerezheti meg az aláírást. Ha viszont valaki a két zárthelyi közül legalább az egyiket már elsőre eredményesen írja meg, akkor a másik zárthelyit összesen akár három alkalommal (a zárthelyin, a pótzárthelyin, illetve az aláíráspótló vizsgán) is megpróbálhatja teljesíteni. Az aláíráspótló vizsgán történő zárthelyi pótlásra kizárólag a Neptunban lehet jelentkezni. (Aki ezt elmulasztja, annak az ekkor megszerzett aláírását nem tudjuk a Neptunba könyvelni. Ezért nem tudjuk olyan hallgatónak engedélyezni a pótlást, aki a Neptun-jelentkezést elmulasztotta.)

Korábbi félévben szerzett aláírás:

A hatályos TVSz szerint a tárgyból szerzett aláírás 3 évig érvényes. (Ez pontosabban azt jelenti, hogy a megszerzését követő hatodik félév vizsgaidőszakának végéig érvényes az aláírás. Azok, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyiket, a célból hogy a korábbi zárthelyik eredményein javítsanak illetve hogy az aláírás érvényességét meghosszabbítsák. Erre az esetre az alábbi feltételek vonatkoznak:

Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését.

Vizsga:

Vizsgára csak az jelentkezhet, aki érvényes aláírással rendelkezik.

A vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a vizsgázó a tárgyhoz tartozó tételsorból egyetlen tételt kap, aminek a kidolgozására (vagyis a szóbeli felelethez egy vázlat vagy bő jegyzet elkészítésére) legalább 45 percet biztosítunk. A felelet abból áll, hogy egyrészt a vizsgázó a jegyzeteire támaszkodva részletesen beszámol a húzott tételről, másrészt a vizsgáztató néhány szúrópróbaszerű, az anyag többi részével kapcsolatos kérdésére válaszol. (A vizsga sikerességéhez tehát nem elég a kihúzott tétel ismertetése, az imént említett további kérdésekre is kell tudni válaszolni.) Az elégséges megszerzésének feltétele, hogy a vizsgázó az anyagban szereplő minden definíciót és tételt ki tudjon mondani, illetve tudjon értelmezni. Természetesen a zárthelyik által le nem fedett anyagrészből is kaphat kérdést a vizsgázó.

A vizsgajegy a házi feladatokra kapott pontok, a két zárthelyi eredménye ill. a vizsgán nyújtott szóbeli teljesítmény súlyozott átlaga, amiben a házi feladatok 10%, a zárthelyik összeredménye 40%, a szóbeli vizsga pedig 50% súllyal szerepel.

Aki elégtelenre vizsgázik, az egy ízben ismétlő vizsgát tehet amennyiben a vizsgaidőszak hátralévő részében még van meghirdetett vizsgaalkalom és arra tud jelentkezni. Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

A vizsgákra a Neptunban kell jelentkezni. (Felhívjuk a figyelmet arra, hogy a Neptun csak a vizsgára jelentkezett hallgatók eredményeinek a felvitelét engedélyezi, így nincs lehetőségünk olyan hallgatót vizsgáztatni, aki a jelentkezést elmulasztotta.)
A vizsgán (ebből a tárgyból) nem szükséges alkalmi viseletben megjelenni. A hallgató öltözködése a vizsga eredményét nem befolyásolja.