Előadó Fleiner Tamás (fleiner@cs.bme.hu)
Előadás kedd 12:15-14:00: QBF13
Gyakorlatok
Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
T1 |
péntek 12:15-13:45 | Varga Kitti |
H406 |
1. hét |
február
28. |
1.
előadás Néhány tipikus algoritmikus bizonyítás: mohó technika, javító utak. |
március 3. | 1. gyakorlat | |
2. hét | március 7. |
2.
előadás Stabil párosítások, éltörlési lemma, Gale és Shapley lánykérő algoritmusa. |
március 10. | 2. gyakorlat | |
3. hét | március 14. | 3.
előadás Stabil párosítások hálóstruktúrája, stabil párosítások alkalmazásai: Pym linking tétele, Galvin tételének általánosítása. |
március 17. | 3. gyakorlat | |
4. hét | március 21. | Simonyi konferencia, az
előadás elmarad |
március 24. | 4. gyakorlat | |
5. hét | március 28. | 4.
előadás Stabil párosítások nem páros gráfokon, Irving algoritmusa, stabil félpárosítások. |
március 31. | 5.
gyakorlat |
|
6. hét | április 4. | 5.
előadás Minimális vágások keresése, a Nagamochi-Ibaraki-algoritmus (maxvissza sorrend), Karger algoritmusa. |
április 7. | Tavaszi szünet, a
gyakorlat elmarad. |
|
7. hét | április 11. | Tavaszi szünet, az előadás elmarad. |
április 14. | 6. gyakorlat | |
8. hét | április 18. |
6.
előadás Ritka tanúk, merevkörű gráfok, szimpliciális sorrend, merevkörű gráfok listaszínezése. |
április 20. |
7. gyakorlat | |
9. hét | április 25. |
7.
előadás Lamináris halmazrendszerek reprezentációja és a Gomory-Hu fa. |
április 28. |
8. gyakorlat | |
10. hét | május 2. |
8.
előadás Edmonds algoritmusa, Tutte tétele, Tutte--Berge-formula, Edmonds--Gallai-struktúratétel, faktorkritikus gráfok. Tudnivalók |
május 5. |
Hétfői munkarend: a gyakorlat elmarad | |
11. hét | május 9. |
9.
előadás |
május 13. | 9. gyakorlat | |
12. hét | május
16. |
10.
előadás Baranyai tétele |
május 19. |
10. gyakorlat | |
13. hét | május
23. |
11.
előadás ZH előtti konzultáció |
május
26. |
12-14 ZH (gyakorlat helyett) Megoldások | |
14. hét | május 30. |
A ZH megbeszélése |
június 2. |
12-14 pZH (gyakorlat helyett) Megoldások | |
póthét |
június 9. |
10, IB134, vizsga |
június 9. |
13-15, IB134, konzultáció (e-mailes egyeztetés után) | |
1.
vizsgahét |
június 12. |
8, IE007, vizsga |
június 16. |
13-15, IB134, konzultáció (e-mailes egyeztetés után) | |
2.
vizsgahét |
június 19. |
8, IE007, vizsga |
június 23. |
10-12, IB134, konzultáció (e-mailes egyeztetés után) | |
3. vizsgahét |
június 26. |
8, IE007, vizsga |
Frank András: Diszkrét optimalizálás
Frank András: Gráfelmélet
Értékelés,
tárgykövetelmények,
vizsga
Zárthelyik, pótzárthelyik, aláírás:
A félév során egy öt feladatból álló, 90 perces
zárthelyi lesz. Az aláírás feltétele, hogy ez a zárthelyi
sikeres legyen (azaz az elérhető 50 pont 40%-át, konkrétan
legalább 20 pontot érjen). A zárthelyi esetében biztosítjuk
pótlás lehetőségét, amikoris a meg nem írt zárthelyi pótolható
vagy a már megírt zárthelyi javítható. A pZH-t a ZH-val azonos
anyagrészből íratjuk, és szándékunk szerint a ZH-val azonos
nehézségű. A pZH-n elért eredmény felülírja az adott
számonkérés korábbi eredményét, kivéve egy sikeresen megírt ZH
sikertelen javításának esetét: ilyenkor az adott ZH pontszáma a
sikeres számonkérés minimális pontszáma, azaz 20 lesz.
Aláíráspótlást nem tartunk, tehát aki a pZH-n sem tudta
megszerezni az aláírást, az nem jelentkezhet a szóbeli vizsgára.
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 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.
Negyvenöt perc felkészülési idő letelte után a vizsgáztató
abban az esetben is elkezdheti a vizsgáztatást, ha a hallgató
még nem jelezte, hogy elkészült. 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
fent 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 lényeges (a tételsorban félkövéren
szedett) definíciót és tételt pontosan ki tudjon mondani,
illetve tudjon értelmezni. Ugyancsak szükséges, hogy a
nem vastagon szedett részek esetében is legfeljebb egy-két
hiányossága legyen a vizsgázónak. Ennél több viszont nem is
kell a ketteshez, azaz a tételsorban szereplő tételek
bizonyításainak ismerete csak a közepes vagy jobb jegy
megszerzéséhez szükséges. Ha valaki az egyszerűbb
bizonyításokat is tudja, akkor jók az esélyei a hármas szóbeli
feleletre. A négyes vagy ötös felelethez (esetleg
kisebb-nagyobb segítséggel) már a nehéz bizonyításokat is el
kell tudni mondani (és persze érteni is kell azokat). A
vizsgán számítani kell arra is, hogy a zárthelyik által le nem
fedett anyagrészből bizonyosan kap kérdést a vizsgázó.
A vizsgajegy a zárthelyi eredményének ill. a vizsgán nyújtott
szóbeli teljesítménynek a súlyozott átlaga, amiben a
zárthelyiedmény súlya 2, a szóbeli vizsgáé pedig 3. Ha a
szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen
(függetlenül a zárthelyi eredményétől). Ez a gyakorlatban azt
jelenti, hogy a zárthelyi eredményei alapján egy 16 és 40
közötti "hozott pontszámot" számítunk ki, ami a két ZH
pontszámának 40%-a, és ehhez adódik a szóbeli vizsgán
szerezhető, legfeljebb 60 pont. Ha a szóbeli részen szerzett
pontszám 24-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. Sikeres
vizsga esetén is tehető javító vizsga. Ismétlő ill. javító
vizsga esetén a zárthelyikből származó eredmények változatlan
módon érvényesek. A férőhelyek függvényében további
ismétlő/javító vizsgára is van lehetőség, azonban ugyanabban
félévben csupán két vizsga díjmentes: a harmadik alkalomtól ez
díjköteles, amit a neptun kiszámláz.
A
vizsgákat megelőzően konzultációt tartunk. Itt a vizsgára
való készülés közben felmerült kérdéseket lehet feltenni.
A konzultáción bárki részt vehet, nem csak az, aki az
éppen soron következő vizsgára jelentkezett. 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 szóbeli vizsga eredményét semmilyen
tekintetben sem befolyásolja.