VISZA028 2024 tavasz

Gráfok és algoritmusok


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


Féléves ütemterv

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


Jegyzet, segédanyag

Előadásvideók és diasorok

Frank András: Diszkrét optimalizálás

Frank András: Gráfelmélet

Frank András: Kombinatorikus algoritmusok II.

Régebbi zh feladatok és megoldásaik.


É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 kijavított zárthelyi és pótzárthelyi dolgozatokba betekintést biztosítunk.

A számonkérések megírásakor az alábbi szabályok betartását követeljük meg.
Kérjük, hogy mindazon hallgatók, akikre a dolgozatíráskor speciális szabályokat kell alkalmazni, ezt legalább egy héttel a dolgozatírás előtt jelezzék az előadónak írt e-mailben. Az zárthelyikre osztályzatot nem adunk, hanem az azon szerzett pontszám számít a vizsgajegybe.


Vizsga:

Vizsgázni csak az jöhet, aki a neptunban jelentkezett az adott vizsgaalkalomra, továbbá a vizsgára jelentkezéshez érvényes aláírással rendelkezik. 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 bármilyen okból nincs a neptun által generált vizsgalapon. A jelentkezések és lemondások a vizsgát megelőző napon 12 órakor lezárulnak. Elővizsgát nem tartunk.

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.