Kombinatorikus optimalizálás
VISZMA09
2025/2026. tavaszi félév

időpontok   ütemterv, összefoglalók, feladatsorok    segédanyagok    jegyszerzés szabályai


Előadás:


Kurzuskód:
Előadó:
Időpont:
Helyszín:
1
 Héger Tamás (email: heger_KUKAC_cs.bme.hu) Kedd 10.15 - 11.45
IB 026



Gyakorlat:


Kurzuskód:
Gyakorlatvezető:
Időpont:
Helyszín:
11
 Héger Tamás (email: heger_KUKAC_cs.bme.hu) Csütörtök 08.30 - 10.00
QBF11
12 és 13
 Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) Csütörtök 08.30 - 10.00
QBF09


Zárthelyi, pótzárthelyi dolgozatok:


ZH kód:
Időpont:
Helyszín:
ZH1
Április 15. (szerda), 18:00-19:30
Q-I (Q épület, I-es (nagy) előadó)
PZH1
Április 29. (szerda), 18:00-19:30
E1B
ZH2
Május 14. (csütörtök), 18:00-19:30
Q-I
PZH2
Június 1. (hétfő), 10:00-12:00
Q-I (azaz Q1)
PPZH
Június 5. (péntek), 10:00-12:00
QBF13



Féléves ütemterv:


1. hét
február 17.
1. előadás:
Gráfok kromatikus száma, független csúcshalmazok, alsó és felső korlátok a kromatikus számra, mohó színezés. Páros (kétosztályú) gráfok, jellemzés körökkel.
Fleiner Tamás diái (élszínezés az előadáson már nem volt).
február 19. 1. gyakorlat, néhány feladat megoldásával.
2. hét
február 24.
2. előadás:
A BME Formula Racing Team bemutatkozása (tagfelvétel március 1-ig).
Élkromatikus szám, triviális becslés, Vizing és Shannon tételei (nem biz). Kőnig élszínezési tétele páros gráfokra (nem biz). Maximális párosítások, lefogó ponthalmazok, kapcsolat a megfelelő gráfparaméterek között. Párosítás növelése javító úttal tetszőleges gráfban; ha a párosítás nem maximális, akkor van javító út. Javító utas algoritmus páros gráfok maximális méretű párosításának keresésére.
Fleiner Tamás diái: élszínezések (a vége felé), folyamok, párosítások (még csak egy kis részét fedtük le az előadáson).
február 26. 2. gyakorlat, néhány feladat megoldásával.
3. hét
március 3.
3. előadás:
Páros gráfok mátrixreprezentációja, maximális párosítás keresése javító úttal a mátrixreprezentációban. Ha már nincs javító út: Hall tétele, Kőnig tétele páros gráfok maximális párosításainak és minimális lefogó ponthalmazainak méretéről. Maximális súlyú párosítások, súlyozott lefogások, kapcsolatuk.
Fleiner Tamás diái: folyamok, párosítások (ennek a végén van az előadáson vetített példa a javító utas algoritmus futtatására mátrixreprezentációban), max súlyú párosítások (ennek kb az első fele volt eddig az előadáson).
március 5. 3. gyakorlat, néhány feladat megoldásával.
4. hét
március 10.
4. előadás:
Egerváry tétele, a magyar módszer. Hálózati folyamok, vágások, maximális folyam, minimális vágás, optimalitási kritérium, MFMC- (Ford--Fulkerson-) tétel. Folyam növelése javító úttal.
Fleiner Tamás diái: magyar módszer (órán kivetített példa a vége felé), folyamok.
március 12. 4. gyakorlat, néhány feladat megoldásával.
5. hét
március 17.
5. előadás:
Hálózati folyamok: javítóutas algoritmus, egészértékűségi lemma, néhány általánosabb feladat visszavezetése az alapfeladatra. Lineáris egyenlőtlenségrendszerek, lineáris programozási (LP) feladat. Az LP feladat geometriai interpretálása és megoldása két változó esetén. Lineáris egyenlőtlenségrendszerek megoldása a Fourier--Motzkin-elimináció segísével (egyelőre az eljárás helyességét nem igazoltuk).
Fleiner Tamás diái (lineráis egyenlőtlenségek, FM-elimináció). A folyamokhoz kapcsolódó tananyag az előző diasoron szerepel, az előadáson veített példa itt.
március 19. 5. gyakorlat, nehány feladat megoldásával.
6. hét
március 24.
Nincs előadás (dékáni szünet a Simonyi Konferencia miatt).
március 26. 6. előadás (VÁLTOZÁS!)
FM elimináció helyessége, megoldhatóság esetén megoldás konstruálása fordított sorrendű értékadással, példa ezen a diasoron (középtájt). Ha az FM-elimináció során tilos sort kapunk, akkor a tilos sor előáll a kibővített együtthatómátrix sorainak nemnegatív együtthatós lineáris kombinációjaként. Lineáris egyenlőtlenségrendszerek mátrixos alakja. Farkas-lemma. Kanonikus alakú lineáris programozási (LP) feladat megoldhatóságának és a célfüggvény korlátosságának vizsgálatára, alternatív egyenlőtlenségrendszerek felírása a Farkas-lemma alapján. Duális LP rendszer felírása, az optimális célfüggvényértékek egybeesése.
Fleiner Tamás diái (lineáris programozás, dualitás).
7. hét
március 31.
6. gyakorlat, nehány feladat megoldásával.
április 2. Nincs gyakorlat (tavaszi szünet)
8. hét
április 7.
Nincs előadás (tavaszi szünet).
április 9. Nincs gyakorlat (tavaszi szünet).
9. hét
április 14. Nincs előadás
EA helyett konzultáció lesz az 1. ZH-ra való minél eredményesebb felkészülés érdekében.
április 15. Első ZH. Tananyag: az első 6 gyakorlat anyaga. Időpont, helyszín: 18:00-19:30, Q-I (Q épület, I-es (nagy) előadó).
Feladatsor, pontozási útmutató (mintamegoldásokkal).
április 16. 7. gyakorlat, néhány feladat megoldásával.
10. hét
április 21.
7. előadás
Lineáris programozás dualitástétele, sztenderd alakú LP duálisának felírása. Egészértékű programozási (IP) feladat, TU mátrixok, TU mátrixszal és egész jobboldalakkal felírt LP-nek ha van megoldása, illetve optimális megoldása, akkor van egészértékű megoldása, illetve optimális megoldása is. (Irányított) gráfok illeszkedési mátrixa.
Fleiner Tamás diái: dualitás, egészértékű programozás.
április 22. 8. gyakorlat, néhány feladat megoldásával.
11. hét
április 28.
8. előadás
Irányított gráfok és páros gráfok illeszkedési mátrixa TU. Max súlyú párosítás keresése IP feladatként TU együtthatómátrixszal. Gráfok többszörös összefüggősége: lokálisan (két csúcs viszonylatában )és globálisan (az egész gráfra vonatkozóan) értelmezett k-szoros összefüggőség és élösszefüggőség. Vágások, éldiszjunkt, illetve belsejükben pontdiszjunkt utak, Menger tételei.
április 29. Első pótZH (18:00, E1B). Feladatsor, pontozási útmutató.
április 30. 9. gyakorlat, néhány feladat megoldásával.
12. hét
május 5.
9. előadás

Gráfok él- és pontösszefüggésének meghatározása folyamokkal. Max-vissza sorrend, élösszefüggőség meghatározása a Nagamochi-Ibaraki algoritmussal. Elvágó élek, 2-komponensek. Egy gráf kétszeresen élösszfüggővé tételéhez szükséges behúzandó élek minimális száma.
Fleiner Tamás diái.
május 7. 10. gyakorlat, néhány feladat megoldásával.
13. hét
május 12.
10. előadás
Egy gráf kétszeresen összefüggővé tételéhez szükséges élek minimális száma. Kétszeresen összefüggő gráfok ekvivalens jellemzései. Fülfelbontás. Kétszeres (él)összefüggőség és fülfelbontás kapcsolata.
május 14. 11. gyakorlat: készülés a 2. ZH-ra (konzultáció), új feladatsor nincs.
május 14. 2. ZH: 18-20, Q-I. Tananyag a 10. gyakorlatig. Feladatsor, pontozási útmutató (javított változat).
14. hét
május 19.
11. előadás
Robbinst tétele egy gráf erősen összefüggővé irányíthatóságáról. Közelító algoritmusok, abszolút és relatív hiba, példák. A halmazfedési feladat, mohó algoritmus.

május 21. 12. gyakorlat: feladatsor.
15. hét
május 26.
Az előadás elmarad.


május 28. A gyakorlat elmarad.
15. hét
június 1 (hétfő)
Második pótzh: feladatsor, pontozási útmutató.


június 5 (péntek). Pót-pót ZH (díjköteles pótlás, Neptunban kell rá regisztrálni). 10:00-12:00, QBF13.


Jegyzet, segédanyag


Tárgykövetelmények, értékelés, vizsga

Zárthelyik, pótzárthelyik:

A félév során kettő darab, 90 perces, négy vagy öt feladatból álló zárthelyi lesz, mindegyiken 50 pont szerezhető. A legalább elégséges félévközi jegy feltétele, hogy mindkét zárthelyi sikeres legyen (azaz az elérhető 50 pont 40%-át, konkrétan legalább 20 pontot érjen).

Mindkét zárthelyi esetében egy-egy alkalommal biztosítunk pótlási lehetőséget. Ilyenkor az adott témakörben meg nem írt zárthelyi pótolható, ill. 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 ha egy sikeresen megírt ZH javítása 20 pontnál kevesebbet ér: ekkor az adott ZH végső pontszáma a sikeres számonkérés minimális pontszáma, azaz 20 lesz.

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 a tényt legalább egy héttel a dolgozatírás előtt e-mailben jelezzék az előadó felé.


Zárthelyik értékelése, megajánlott jegy:

Az egyes zárthelyikre osztályzatot nem adunk, hanem a legalább egy számonkérésen megjelenő hallgatók összpontszámát konvertáljuk megajánlott jeggyé az alábbiak szerint, azzal a további megkötéssel, hogy az elégtelennél jobb osztályzathoz mindkét ZH-nak sikeresnek kell lennie. (Aki egyetlen ZH-t sem ír meg, az "nem teljesítette" bejegyzést kap erre a kurzusra.)

0-39 pont
elégtelen
40-54 pont
elégséges
55-69 pont
közepes
70-84 pont

85-100 pont
jeles


Megajánlott jegy elfogadása, vizsga:

A megajánlott jegyet elfogadni úgy lehet, hogy jelentkezni kell az e célból létrehozott szóbeli vizsgaalkalomra. Mindenki, aki erre a vizsgaalkalomra jelentkezik, automatikusan a megajánlott jegyét kapja.

Aki nem fogadja el a megajánlott jegyét (azaz nem jelentkezik erre a speciális vizsgára), az szóbeli vizsgát tehet, amin legfeljebb egy osztályzatot tud javítani a megajánlott jegyén (rontani viszont korlátlanul tud). A szóbeli vizsgához vizsgatételsor tartozik, ami a félév végére alakul ki, és majd itt érhető el, ebben részletesebb tájékoztató is található a vizsgáról. A szóbeli vizsgán egy tételt sorsolunk a vizsgázónak, melynek kidolgozására 30 percet biztosítunk. A vizsga során ellenőrző kérdések erejéig a többi tételbe is belekérdezhetünk, a ZH által le nem fedett anyagrészből biztosan kap kérdést a vizsgázó.