Előadó Fleiner Tamás (fleiner@cs.bme.hu)
Előadás kedd 12:15-14:00: IE217.1
Gyakorlatok
Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
T1 |
csütörtök 12:15-13:45 | Varga Kitti |
IB134 |
1. hét |
február
11. |
1. előadás Ismétlés (párosítások), Edmonds algoritmusa. Alternáló utas algoritmus példa Edmonds-algoritmus példa |
február 13. | 1.
gyakorlat |
|
2. hét | február 18. | 2.
előadás Edmonds algoritmusa, Tutte tétele, Tutte--Berge-formula. Edmonds--Gallai-struktúratétel, faktorkritikus gráfok. Tudnivalók |
február 20. | 2. gyakorlat | |
3. hét | február 25. | 3.
előadás Stabil párosítások, éltörlési lemma, Gale és Shapley lánykérő algoritmusa, stabil párosítások hálóstruktúrája. (A diasorban szereplő stabil b-párosításokról nem volt szó az órán.) |
február 27. | 3. gyakorlat | |
4. hét | március 4. | 4.
előadás Stabil párosítások alkalmazásai: Pym linking tétele, Galvin tételének általánosítása. Stabil párosítások nempáros gráfokon. |
március 6. | 4. gyakorlat | |
5. hét | március 11. | 5. előadás Irving algoritmusa, stabil félpárosítások. |
március 13. | 5. gyakorlat | |
6. hét | március 18. | Simonyi konferencia,
dékáni szünet, az előadás elmarad. |
március 20. | 6.
gyakorlat |
|
7. hét | március 25. | 6. előadás Ismétlés (folyamok, folyamok és párosítások kapcsolata). Folyamok kerekítése, és alkalmazásai: páros gráfok (egyenletes) élszínezése. |
márciuis 27. | 7. gyakorlat | |
8. hét | április 1. | 7. előadás Algoritmus minimális költségű folyam keresésére. |
április 3. |
8.
gyakorlat |
|
9. hét | április 8. |
8. előadás Minimális vágások keresése, a Nagamochi-Ibaraki-algoritmus (maxvissza sorrend), Karger algoritmusa. |
április 10. |
9. gyakorlat | |
10. hét | április
15. |
9. előadás Ritka tanúk, merevkörű gráfok, szimpliciális sorrend, merevkörű gráfok listaszínezése. |
április 17. |
Tavaszi szünet, a gyakorlat elmarad. | |
11. hét | április
22. |
Tavaszi szünet, az előadás elmarad. |
április 24. | Tavaszi szünet, a
gyakorlat elmarad. |
|
12. hét | április
29. |
10.
gyakorlat (előadás helyett) |
május 1. |
A munka ünnepe, a
gyakorlat elmarad. |
|
13. hét | május 6. |
10. előadás A Gomory-Hu fa. |
május
8. |
11. gyakorlat | |
14. hét | május 13. |
ZH előtti konzultáció |
május 15. |
12-14 ZH (gyakorlat helyett) Megoldások | |
15. hét |
május 20. |
11. előadás Baranyai tétele |
május 22. |
12.
gyakorlat |
|
póthét |
május ??. |
12-14 pZH Megoldások |
1.
vizsgahét |
június ??. | |
június ??. | ||
2.
vizsgahét |
június ??. | |
június ??. | ||
3. vizsgahét |
június ??. |
Korábbi előadásvideók és diasorok
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 30 percet biztosítunk.
A 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 esetenként 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.