Előadás:
|
|
|
Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) |
|
|
Gyakorlatok, gyakorlatvezetők:
|
|
|
|
|
Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) |
Kedd14.15 - 15.00 |
|
A gyakorlatok után 45 perces "konzultáció" van a T
604-es
teremben.
Segédanyagok:
Készült néhány digitális jegyzet villamosmérnököknek és informatikusoknak, ami az anyag bizonyos részeit tartalmazza. Ez később még talán bővülni fog.
Digitális tananyag található még Simonyi Gábor honlapján is.
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, 2009
Kombinatorika és Gráfelmélet I, 2010
Kombinatorika és Gráfelmélet I, 2011
Kombinatorika és Gráfelmélet I, 2012
Kombinatorika és Gráfelmélet I, 2013
Kombinatorika és Gráfelmélet II, 2010
Kombinatorika és Gráfelmélet II, 2011
Kombinatorika és Gráfelmélet II, 2012
Kombinatorika és Gráfelmélet II, 2013
További segédanyagok:
A Tutte tétel bizonyítása
A Fáry-Wagner tétel bizonyítása
Listaszínezés, Galvin tétel
A Perfekt gráf tétel bizonyítása
Kuratowski-tétel, Fáry-Wagner tétel
Részben rendezett halmazok, Dilworth tétele
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
Eseménynaptár
1. hét |
2014. február
10. |
Perfekt gráfok, intervallumgráfok, perfekt gráf tétel, Dilworth tétele |
2014. február 11. | 1. gyakorlat |
|
2. hét |
2014. február
17. |
Síkbarajzolhatóság, Euler-formula, Kuratowski-tétel, Fáry-Wagner tétel |
2014. február 18. | 2. gyakorlat |
|
3. hét |
2014. február
24. |
Geometriai és absztrakt dualitás, gyenge izomorfia, Whitney tételei, ötszíntétel |
2014. február 25. | 3. gyakorlat |
|
4. hét |
2014. március 3. |
Ramsey-tétel, Erdős-Szekeres tétel, Erdős-féle alsó becslés, a valószínűségi módszer |
2014. március 4. |
4. gyakorlat | |
5. hét |
2014. március 10. |
Turán-tétel, Erdős-Stone tétel, Erdős-Simonovits tétel |
2014. március 11. |
5. gyakorlat | |
6. hét | 2014. március 17. | Hipergráfok, Erdős-Ko-Rado tétel |
2014. március 18. | 6. gyakorlat (konzultáció) |
|
7. hét | 2014. március
24. |
I. Zárthelyi (Helyszín: K134, időpont: 10.00) megoldások eredmények |
2014. március 25. | 7. gyakorlat | |
8.hét |
2014. március 31. |
Sperner-tétel, LYM egyenlőtlenség, De Bruijn - Erdős tétel |
2014. április 1. |
8. gyakorlat | |
9. hét |
2014. április 7. |
Rekurziók, generátorfüggvények, Fibonacci számok, homogén lineáris rekurziók |
2014. április 8. |
9. gyakorlat | |
10. hét |
2014. április
14. |
halmazelméleti és számelméleti particiók, Catalan-számok |
2014. április 15. | 10. gyakorlat | |
11. hét |
2014. április
21. |
Húsvét hétfő |
2014. április 22. | Stabil párosítások (előadás!) | |
12. hét | 2014. április 28. | 11. gyakorlat (!!!) |
2014. április 29. | 12. gyakorlat (konzultáció) |
|
13. hét | 2014. május 5. | II. Zárthelyi (Helyszín: K134, időpont: 10.00) megoldások eredmények |
2014. május 6. |
13. gyakorlat | |
14. hét |
2014. május 12. |
A Dinitz-probléma, listaszinezés, Galvin tétele, síkgráfok listaszínezése |
2014. május 13. | Pótzárthelyi (Helyszín: T604, időpont: 14.00) eredmények | |
pótlási hét | 2014. május ?? |
Aláíráspótló zárthelyi (Helyszín: , időpont: ...) |
Értékelés, tárgykövetelmények, vizsga:
Házi feladat:
Minden
gyakorlaton adunk egy vagy
két házi feladatot, amelye(ke)t a
következő gyakorlat elején kell beadni. Feladatonként legfeljebb
5 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 beadott házi feladatok eredménye
10% súllyal számít a végső érdemjegybe. A pontverseny állása online
megtekinthető.
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 az alábbiak szerint.
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 pótzárthelyi ugyanazt az anyagrészt fedi le, amelyet
a megfelelő zárthelyi, és szándékunk
szerint a nehézsége is
azonos a pótolt zárthelyi dolgozatéval.
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ó zárthelyi helyszínét és
időpontját később tűzzük ki. Természetesen
a kijavított aláíráspótló dolgozatokba való betekintésre is
biztosítunk
lehetőséget.
Figyelem! 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.)
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 sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe az így kapott eredmény számít bele (akkor is, ha ez rosszabb) és az aláírás érvényessége az újbóli megszerzéstől számított 3 év lesz.
Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be és az aláírás érvényessége sem változik az eddigihez képest.
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.
Konzultáció:
Minden vizsgaalkalom előtti munkanapon konzultációt tartunk, ahol a vizsgára készülés közben felvetődött kérdéseket tisztázzuk. A konzultációra vonatkozó igényét az érintett hallgató e-mailben jelezze az előadónak.
Vizsga:
Vizsgára csak az jelentkezhet,
aki érvényes aláírással rendelkezik, aláírást
ebben a félévben a "Zárthelyik, pótzárthelyik"
pontban leírtak szerint lehet
szerezni.
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 vizsga ebből a tárgyból szóbeli. A vizsga
megkezdésekor a vizsgázónak kisorsolunk egy tételt a tárgyhoz
tartozó, a félév végére kialakuló vizsgatételsorból. Ennek 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 a vizsgázó egyrészt
a jegyzeteire támaszkodva részletesen beszámol a húzott
tételben található tananyagról, másrészt a vizsgáztató néhány
szúrópróbaszerű, a tananyag tová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 meg kell felelni.) 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. Számítani kell arra, hogy a vizsgázó bizonyosan kap kérdést
a zárthelyik által le nem fedett anyagrészből.
Figyelem:
az eredetileg hibásan meghirdetett tételsor
javításra került. Az anyagban
nem szereplő Bruck-Chowla-Ryser
tétel helyett bekerült a tanult Ray-Chauduri-Wilson
tétel, valamint szerepel egy stabil
párosításokkal kapcsolatos tétel is, ami sajnálatos
módon kimaradt az első változatból.
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.
Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen
(függetlenül a házi feladatok és
a zárthelyik eredményeitől).
Ez a gyakorlatban azt jelenti, hogy a zárthelyik eredményei
alapján egy 16 és 40 közötti "hozott pontszámot"
számítunk ki, amihez hozzáadódik a házi
feladatokra kapott legfeljebb 100 pont
tizedrésze, valamint
a vizsgán szerezhető legfeljebb 50
pont. Ha a vizsgán szerzett pontszám 20-nál kevesebb, akkor a vizsgajegy elégtelen,
egyébként pedig a hozott pontszám és a vizsgán szerzett pontok
összegéből az alábbiak szerint számítjuk a vizsgajegyet: 40 és
54 pont között elégséges, 55 és 69 pont között közepes, 70 és
84 pont között jó, végül 85 és 100 pont között jeles.
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ákat megelőző
munkanapokon tartott konzultáción a vizsgára való
készülés közben felmerült kérdéseket lehet feltenni. A
konzultációk időpontja és helyszíne a neptunban szintén megtalálható, de a konzultációra nem kell (és nem is lehet)
jelentkezni. Az elővizsga követelményei és
következményei azonosak a vizsgáéval: aki érvényes
aláírással rendelkezik, az jelentkezhet, pontosan
ugyanolyan szigorúan osztályozunk, mint a többi vizsgán
és a meg nem jelenés ill. elégtelen érdemjegy
következményei is ugyanazok.
A vizsgán (ebből a tárgyból) nem szükséges alkalmi
viseletben megjelenni. A hallgató (egyébként
civilizált) öltözködése a vizsga eredményét
semmilyen tekintetben sem befolyásolja.