Kombinatorikus optimalizálás
VISZMA09
2024/2025. 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.25 - 09.55
IB 139
12 és 13
 Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) Csütörtök 08.30 - 10.00
QBF13


Zárthelyi, pótzárthelyi dolgozatok:


ZH kód:
Időpont:
Helyszín:
ZH1
Április 2. (szerda), 18-20
Q-I
PZH1
Április 16. (szerda), 18-20
Q-I
ZH2
Május 8. (csütörtök), 18-20
E1B, E1C
PZH2
Május 19. (hétfő), 18-20
Q-II
PPZH
Május 26. (hétfő), ?
?



Féléves ütemterv:

Ami még eljövendő, az csak tervezet. A múlt biztos.

1. hét
február 11.
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. A BME Formula Racing Team bemutatkozása (tagfelvétel feb. 23-ig).
Fleiner Tamás diái (1-7. dia / 1-94. oldal (léptetés))
február 13. 1. gyakorlat, néhány feladat megoldásával.
2. hét
február 18.
2. előadás:
Páros (kétosztályú) gráfok, jellemzés körökkel. Élkromatikus szám, triviális becslés, Vizing és Shannon tételei (nem biz). Kőnig élszínezési tétele. 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 (még nem biz).
Fleiner Tamás diái: előző diasor (8-9.dia / 95-119. oldal)
február 20. 2. gyakorlat, néhány feladat megoldásával és tippekkel.
3. hét
február 25.
3. előadás:
Párosítások növelése javító úttal, ha egy párosítás nem a legnagyobb, akkor van javító út. Részletesebben páros gráfokban: alternáló és javító utak keresése élek irányításával / mátrixreprezentációban (vetített példa (68-81. oldal (10. dia))); mi következik abból, ha egy páros gráfban már nincs javító út (Kőnig tétele páros gráfok maximális párosításainak és minimális lefogó ponthalmazainak méretéről, deficites Hall-tétel, Hall-tétel), konstruktív bizonyítékok egy párosítás maximalitására. Maximális súlyú párosítások, súlyozott lefogások.
Fleiner Tamás diái: párosítások (53. oldaltól), súlyozott párosítások (4. diáig / 20. oldal, de előadáson még nem minden szerepelt).
február 27. 3. gyakorlat és néhány feladat megoldása.
4. hét
március 4.
4. előadás:
Egerváry tétele, a magyar módszer (az EA-n vetített példa (26-33. oldal (6. dia))). Hálózati folyamok, vágások, folyam nagysága, vágás kapacitása, kapcsolatuk.
Fleiner Tamás diái a magyar módszerről és a folyamokról (1-19. oldal (1-4. dia)).
március 6. 4. gyakorlat, és néhány feladat megoldása.
5. hét
március 11.
5. előadás:
Hálózati folyamok: maximális folyam, minimális vágás, folyam növelése és minimális vágás keresése javító utakkal (segédgráfos eljárás), MFMC- (Ford--Fulkerson-) tétel. Egészértékűségi lemma, alkalmazás páros gráfok maximális párosításaira. Néhány általánosabb feladat visszavezetése az alapfeladatra.
Fleiner Tamás diái.
március 13. 5. gyakorlat, néhány feladat megoldásával.
6. hét
március 18.
6. előadás:
Lineáris egyenlőtlenségrendszerek, Fourier--Motzkin-elimináció. Tilos sor előállítása az eredeti egyenlőtlenségekből. Fleiner Tamás diái: Fourier--Motzkin-elimináció, Farkas-lemma.
március 20. 6. gyakorlat, néhány feladat megoldásával.
7. hét
március 25.
7. előadás
Lineáris egyenlőtlenségrendszerek mátrixos alakja. Farkas-lemma. Lineáris programozási (LP) feladat (feltételek, célfüggvény), geometriai interpretáció két ismeretlen esetén, optimális megoldás keresése. Lineáris programozási feladat sztenderd alakja. Lineáris feltételeket kielégítő megoldás létezésének és a célfüggvény korlátosságának vizsgálata, alternatív egyenlőtlenségrendszerek felírása a Farkas-lemma alapján. Duális lineáris program (DLP), kapcsolat a célfüggvények optimális értékei között.
Fleiner Tamás diái: lineáris programozás, dualitás.
március 27. 7. gyakorlat, néhány feladat megoldásával.
8. hét
április 1.
EA helyett konzultáció lesz az 1. ZH-ra való minél eredményesebb felkészülés érdekében.
április 2.
1. ZH: 18-20, Q-I. Tananyag: az eddigi 7 gyakorlat anyaga. Feladatsor, pontozási útmutató.
április 3. 8. gyakorlat (IP modellek felírása), néhány feladat megoldásával.
9. hét
április 8. 8. előadás
Ha az LP és a DLP is megoldható, akkor az optimális célfüggvényértékek megegyeznek. LP feladatok általánosított sztenderd alakja, azok duálisa. Egészértékű és vegyes programozási feladatok (IP / MIP), LP relaxált, kapcsolat a IP és az LP relaxált megoldáshalmazai között, továbbá az IP és az LP relaxált célfüggvényének optimuma, valamint a duális LP és annak IP megszorításának optimális célfüggvényértékei között. Az LP és az IP feladatok bonyolultsága.
Fleiner Tamás diái: dualitás, egészértékű programozás.
április 10. 9. gyakorlat.
10. hét
április 15.
9. előadás
Gráfok kromatikus száma IP feladatként, gyakorlati implementáció, GLPK és Gurobi szoftvercsomagok működésének bemutatása. TU mátrixok, TU mátrixszal és egész jobboldallal adott LP egész megoldásai. Műveletek TU mátrixokkal, melyek megőrzik a TU tulajdonságot. Irányított gráfok, páros gráfok illeszkedési mátrixa TU.
Fleiner Tamás diái: egészértékű programozás.
április 16.
1. PótZH: 18-20, Q-I. Tananyag: ugyanaz, mint az 1. ZH anyaga. Feladatsor és pontozási útmutató.
április 17. Nincs gyakorlat (tavaszi szünet).
11. hét
április 22.
Nincs előadás (tavaszi szünet).
április 24. Nincs gyakorlat (tavaszi szünet)..
12. hét
április 29.
10. előadás
Hálózatok megbízhatósága: többszörös élösszefüggőség és összefüggőség lokálisan / globálisan (két csúcs viszonylatában / a gráf egészén) értelmezve. Menger tétele. Gráfok élösszefüggőségi, összefüggőségi száma. Lokális élösszefüggőség meghatározása folyamokkal. Maxvissza sorrend, gráf (globális) élösszefüggőségének meghatározása (Nagamochi-Ibaraki-algoritmus).
Fleiner Tamás diái: többszörös összefüggőség.
május 1. Nincs gyakorlat (állami szünet). Gyakorló feladatsor: gyakorló feladatsor.
13. hét
május 6.
11. előadás
Az előző két előadás témájához kapcsolódó gyakorló feladatok megoldásának prezentálása (a közelgő ZH-ra való tekintettel).
május 8. 10. gyakorlat: konzultáció (készülés a 2. ZH-ra), új feladatsor nincs.
május 8. 2. ZH: 18-20, E1B és E1C. Tananyag: többszörös összefüggőségig.
14. hét
május 13.
12. előadás
Elvágó élek, 2-komponensek, izolált, levél és belső komponensek, a 2-komponensek és elvágó élek erdője. Elvágó pontok, blokkok, maxblokkok, izolált és levél blokkok, a T_2(G) gráf. Gráfok kétszeresen (él)összefüggővé tételéhez szükséges minimális élek száma. Kétszeresen (él)összefüggő gráfok szerkezete, fülfelbontásuk. Egy gráf pontosan akkor kétszeresen (él)összefüggő, ha van megfelelő fülfelbontása.
Approximációs algoritmusok: abszolút (additív) és relatív (multiplikatív) hiba, példák. Ütemezési feladatok, optimalizálandó célfüggvények, átfutási idő minimalizálása egy gépre (triviális), két gépre (reménytelen). SPT sorrend optimalitása az átlagos befejezési időre egy gépen. Listás ütemezés (LS) relatív hibája általános, illetve LPT sorrend esetén. Ládapakolás, FF és FFD algorimtus. fülfelbontás, approximációs algoritmusok, ütemezési feladatok.
május 15. 11. gyakorlat:
15. hét
május 19.
2. PZH: 18-20, Q-II. Tananyag: a 2. ZH tananyaga, kiegészítve a 11. gyakorlat tananyagával.
május 20.
13. előadás
Lovász leemelési tétele, csúcsok teljes leemelése, $2k$-élösszefüggő gráfok előállítása (élek behúzása, összecsípése).
Fleiner Tamás diáiLP és IP a gyakorlatban: IP modell a halmazfedési problémára, illetve a kétgépes ütemezés feladat átfutási idejének minimalizálására, ezek megoldása kétféle IP/LP solver segítségével. Közelítő megoldás a halmazfedési problémára az LP relaxált optimális megoldásának kerekítéséből (a leggyakoribb elem gyakoriságának függvényében). Karger randomizált algoritmusa minimális súlyú vágás meghatározására.
A diákon ezekből csak Karger algoritmusa szerepel, a 10. előadásnál belinkelt diasoron.
május 22. 12. gyakorlat


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 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ó.