Előadó Fleiner Tamás (fleiner@cs.bme.hu)
Előadás kedd 12:15-14:00: H406
Gyakorlatok
Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
T1 |
péntek 12:15-13:45 | Varga Kitti |
H406 |
1. hét |
február
15. |
1.
előadás Néhány tipikus algoritmikus bizonyítás: mohó technika, javító utak. |
február 18. | 1. gyakorlat | |
2. hét | február 22. |
2.
előadás Stabil párosítások, Gale és Shapley lánykérő algoritmusa. |
február 25. | 2. gyakorlat | |
3. hét | március 1. | 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 4. | 3. gyakorlat | |
4. hét | március 8. | 4.
előadás Stabil párosítások nem páros gráfokon, Irving algoritmusa, stabil félpárosítások. |
március 11. | 4. gyakorlat | |
5. hét | március 15. | Nemzeti ünnep: az előadás
elmarad |
március 18. | 5.
gyakorlat |
|
6. hét | március 22. | 5.
előadás Minimális vágások keresése, a Nagamochi--Ibaraki-algoritmus (maxvissza sorrend), Karger algoritmusa. |
március 25. | 6. gyakorlat | |
7. hét | március 29. |
6.
előadás Ritka tanúk, merevkörű gráfok, szimpliciális sorrend, merevkörű gráfok listaszínezése. |
április 1. | 7. gyakorlat | |
8. hét | április 5. |
7.
előadás Lamináris halmazrendszerek reprezentációja és a Gomory-Hu fa. |
április 8. |
8. gyakorlat | |
9. hét | április 12. |
8.
előadás Edmonds algoritmusa, Tutte tétele, Tutte--Berge-formula, Edmonds--Gallai-struktúratétel, faktorkritikus gráfok. Tudnivalók |
április 15. |
Nagypéntek: a gyakorlat
elmarad |
|
10. hét | április
19. |
Tavaszi szünet: az előadás elmarad |
április 22. |
9. gyakorlat | |
11. hét | április
26. |
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. |
10.
gyakorlat |
||
12. hét | május 3. |
10.
előadás |
május 6. |
11. gyakorlat | |
13. hét | május
10. |
11.
előadás Baranyai tétele |
május
13. |
12. gyakorlat | |
14. hét | május 17. |
12-14 ZH (előadás helyett) Megoldások |
május 20. |
12-14 pZH (gyakorlat helyett) Megoldások | |
pótlási hét |
május ??. |
aláíráspótlás (előzetes neptun-jelentkezés szükséges) |
Vizsgák: május 30, június 7, 13, 20.
Konzultáció a vizsgát megelőző munkanapon 9 órától, e-mailes
egyeztetést követően.X
Frank András: Diszkrét optimalizálás
Frank
András: Gráfelmélet
Frank
András: Kombinatorikus algoritmusok II.
É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.
Akinek a fenti, alanyi jogon jár pótlás után sincs aláírása, az a ppZH (alias aláíráspótlás) alkalmával megírhatja ugyanezt a számonkérést, és annak az eredménye végleges lesz. Erre a neptunban kell jelentkezni, aholis aláíráspótló vizsga néven fut ez a számonkérés. Figyelem! Aki a neptunbeli jelentkezést elmulasztja vagy lekési, az nem vehet rész ezen a számonkérésen, így jegyet sem szerezhet, hiszen az ekkor megszerzett eredményt nem tudjuk a neptunban adminisztrálni. Az ppZH-n való részvételért a neptun utólag különeljárási díjat számláz ki. (A szorgalmi időszakban tartott pótzárthelyire nem szükséges jelentkezni a neptunban, azon mindenki a saját döntése szerint vehet részt.)
A ppZH időpontja
(körülbelül a szorgalmi időszak közepétől) a neptunból
deríthető ki. Az itt írt dolgozatokat még aznap kijavítjuk és
biztosítjuk abba a betekintést. (Ennek a pontos időpontját a
dolgozatírás közben hirdetjük ki.) Aki a megtekintésen nem tud
megjelenni, az a dolgozatát kérésre később is megnézheti, de
ekkor már a dolgozat pontozásán nem tudunk változtatni.
A kijavított zárthelyi és
pótzárthelyi dolgozatokba betekintést biztosítunk.
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. Érdemes bölcsen élni
ezzel a lehetőséggel, tudva, hogy aki ugyanazon tárgyból hat
vizsgán is elégtelen eredményt ér el, azt az egyetem
törvényből fakadó kötelessége okán tanulmányi okból
elbocsátja. 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.