Előadó Fleiner Tamás (fleiner@cs.bme.hu)
Előadás csütörtök 12:15-14:00: IE217.1
Gyakorlatok
Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
T1 |
kedd 12:15-13:45 | Varga Kitti |
március 26-ig IB025 március 19-én IE217.1 április 9-től IB146 |
1. hét |
február
13. |
1. gyakorlat |
február 15. | 1.
előadás Néhány tipikus algoritmikus bizonyítás: mohó technika, javító utak. |
|
2. hét | február 20. | 2. gyakorlat |
február 22. | 2.
előadás Stabil párosítások, éltörlési lemma, Gale és Shapley lánykérő algoritmusa. |
|
3. hét | február 27. | 3. gyakorlat |
február 29. | 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. |
|
4. hét | március 5. | 4. gyakorlat |
március 7. | 4.
előadás Stabil párosítások nem páros gráfokon, Irving algoritmusa, stabil félpárosítások. |
|
5. hét | március 12. | 5. gyakorlat |
március 14. | 5.
előadás Minimális vágások keresése, a Nagamochi-Ibaraki-algoritmus (maxvissza sorrend), Karger algoritmusa. |
|
6. hét | március 19. | 6. gyakorlat |
március 21. | 6.
előadás Ritka tanúk, merevkörű gráfok, szimpliciális sorrend, merevkörű gráfok listaszínezése. |
|
7. hét | március 26. | 7. gyakorlat |
márciuis 28. | Tavaszi szünet, az előadás elmarad. | |
8. hét | április 2. |
Tavaszi szünet, a gyakorlat elmarad. |
április 4. |
Tavaszi szünet, az előadás elmarad. | |
9. hét | április 9. |
8. gyakorlat |
április 11. |
7.
előadás Lamináris halmazrendszerek reprezentációja és a Gomory-Hu fa. |
|
10. hét | április
16. |
9. gyakorlat |
április 18. |
8.
előadás Edmonds algoritmusa, Tutte tétele, Tutte--Berge-formula, Edmonds--Gallai-struktúratétel, faktorkritikus gráfok. Tudnivalók |
|
11. hét | április
23. |
10. gyakorlat |
április 25. | 9.
előadás Lovász leemelési tétele, 2k-élösszefüggő gráfok előállítása, Nash-Williams irányítási tétele |
|
12. hét | április
30. |
11.
gyakorlat |
május 2. |
10.
előadás Algoritmus minimális költségű folyam keresésére. Folyamok kerekítése, és alkalmazásai: páros gráfok (egyenletes) élszínezése. |
|
13. hét | május 7. |
12.
gyakorlat |
május
9. |
11.
előadás Baranyai tétele, ZH előtti konzultáció |
|
14. hét | május 14. |
13.
gyakorlat ZH előtti konzultáció |
május 16. |
12-14 ZH (előadás helyett) Megoldások | |
15. hét |
május 21. |
A ZH megbeszélése |
május 23. |
12-14 pZH (előadás helyett) Megoldások | |
póthét |
május 31. |
10-12 IB217.1 konzultáció |
1.
vizsgahét |
június 3. | 9-11 vizsga IE007 |
június 7. | 10-12 IB217.1 konzultáció | |
2.
vizsgahét |
június 10. | 9-11 vizsga IE007 |
június 14. | 10-12 IB217.1 konzultáció | |
3. vizsgahét |
június 17. | 9-11 vizsga IE007 |
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 ZH
pontszámának 80%-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.
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.