Kombinatorikus optimalizálás
VISZMA09
2023/2024. tavaszi félév


Figyelem: a 03.19-i előadás a IE007 teremben lesz.

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 025



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
R 504
12
 Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) Csütörtök 08.25 - 09.55
R 505



Féléves ütemterv:


1. hét
február 13.
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, Brooks tétele. Páros gráfok. Élkromatikus szám, Vizing és Shannon tételei.
Fleiner Tamás diái
február 15. 1. gyakorlat, megoldásokkal.
2. hét
február 20.
2. előadás:
Kőnig élszínezési tétele. Maximális párosítások, lefogó ponthalmazok. Párosítás növelése javító úttal tetszőleges gráfban, részletesebben páros gráfokban. Kőnig tétele páros gráfok maximális párosításainak és minimális lefogó ponthalmazainak méretéről. Hall-tétel.
Fleiner Tamás diái (a 7. (avagy 46.) diától)
február 22. 2. gyakorlat, néhány feladat megoldásával.
3. hét
február 27.
3. előadás:
Maximális súlyú párosítások, súlyozott lefogások, Egerváry tétele, a magyar módszer.
Fleiner Tamás diái
február 29. 3. gyakorlat, néhány feladat megoldásával (frissült 03.07-én).
4. hét
március 5.
4. előadás:
Hálózati folyamok, vágások, maximális folyam, minimális vágás, segédgráfos eljárás, MFMC- (Ford--Fulkerson-) tétel.
Fleiner Tamás diái (1-6, avagy 1-45), diasor a javító utas eljárásról.
március 7. 4. gyakorlat, néhány feladat megoldásával
5. hét
március 12.
5. előadás (tervezet):
Hálózati folyamok: egészértékűségi lemma, néhány általánosabb feladat visszavezetése az alapfeladatra. Lineáris egyenlőtlenségrendszerek, Fourier--Motzkin-elimináció. 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.
Fleiner Tamás diái (lineráis egyenlőtlenségek) (a folyamokhoz kapcsolódó tananyag az előző diasoron szerepel).
március 14. 5. gyakorlat, néhány feladat megoldásával
6. hét
március 19.
6. előadás: a helyszín az IE007
Lineáris egyenlőtlenségrendszerek mátrixos alakja. Farkas-lemma. Lineáris programozási feladat (feltételek, célfüggvény), geometriai interpretáció két ismeretlen esetén, optimális megoldás keresése. Lineáris programozás 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.
Fleiner Tamás diái (lineáris programozás, dualitás)
március 21. 6. gyakorlat, néhány feladat megoldásával
7. hét
március 26.
7. előadás
Konzultáció lesz az 1. ZH-ra való minél eredményesebb felkészülés érdekében.

március 28. nincs gyakorlat (tavaszi szünet)
8. hét
április 2.
nincs előadás (tavaszi szünet)
április 4. nincs gyakorlat (tavaszi szünet)
9. hét
április 8.
1. ZH: 18-20, Q-II. Tananyag: az első 6 gyakorlat anyaga. ZH feladatsor, javítókulcs.
április 9. 8. előadás

Dualitástétel, egészértékű programozás.
Fleiner Tamás diái: dualitás, egészértékű programozás.
április 11. 7. gyakorlat, néhány feladat megoldásával.
10. hét
április 16.
9. előadás

Egészértékű programozás: LP relaxált, kapcsolat a IP és az LP relaxált (optimális) megoldásai közt. TU mátrixok, TU mátrixszal és egész jobboldallal adott LP egész megoldásai. Irányított gráfok, páros gráfok illeszkedési mátrixa TU. Az LP és az IP feladatok bonyolultsága. Hálózatok megbízhatósága: többszörös élö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 száma.
Fleiner Tamás diái: egészértékű programozás, többszörös összefüggőség.
április 18. 8. gyakorlat, néhány feladat megoldásával.
11. hét
április 23.
10. előadás

Többszörös (él)összefüggőség. 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. Maxvissza sorrend, gráf élösszefüggőségének meghatározása (Nagamochi-Ibaraki-algoritmus). 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.
Fleiner Tamás diái: többszörös összefüggőség, fülfelbontás.
április 24. 1. PZH: 18-20, E1C feladatsor, javítókulcs.
április 25. 9. gyakorlat, néhány feladat megoldásával.
12. hét
április 30.
11. előadás
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.
Fleiner Tamás diái: approximációs algoritmusok, ütemezési feladatok
május 2. 10. gyakorlat, néhány feladat megoldásával.
13. hét
május 7.
12. előadás

2. ZH előtti konzultáció.
május 9. 11. gyakorlat: 2. ZH előtti konzultáció, új feladatsor nincs.
május 9. 2. ZH: 18-20, Q-II. Tananyag: 7-10 feladatsorok anyaga (LP dualitástól ütemezésig / ládapakolásig). feladatsor, javítókulcs.
14. hét
május 14.
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ái
május 16. 12. gyakorlat
15. hét
május 21.
14. előadás
LP é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 23. 13. gyakorlat: konzultáció a 2. PZH-ra.
16. hét
(pótlási hét)
május 27.
2. PZH 8-10, IB025, feladatsor, javítókulcs.
17. hét
(első vizsgahét)
június 3. (hétfő)
PPZH 10-12, IE220
18. hét
(második vizsgahét)
június 10. (hétfő)
Megajánlott jegy elfogadására szolgáló vizsga


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