VISZMA09 2023  tavasz

Kombinatorikus optimalizálás


Előadó  Fleiner Tamás (fleiner@cs.bme.hu)

Előadás  kedd    10:30-12:00  IB025 (Márc 21: STFKis)

Gyakorlatok

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11
csütörtök 8:25-9:55 Fleiner Tamás
R505
12
csütörtök 8:25-9:55 Héger Tamás R504



Féléves ütemterv

1.hét
február 28.
1. előadás
Gráfok kromatikus száma, alsó és felső korlátok, mohó színezés. Páros gráfok, élkromatikus szám, Kőnig tétele páros gráfok élszínezéséről.
március 2. 1. gyakorlat 
2.hét március 7. 2. előadás
Hálózati folyamok, javító utas algoritmus, Ford-Fulkerson-tétel, EgÉr-lemma, páros gráfok maximális párosításai. Az alternáló utas algoritmus futtatása a páros gráf mátrixreprezentációján.
március 9.
2. gyakorlat 
3.hét március 14. 3. előadás
Maximális súlyú párosítások, Egerváry magyar módszere. 
március 16. 3. gyakorlat 
4.hét március 21.
4. előadás         Helyszín: STFKis
Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma.
máricus 23. 4. gyakorlat 
5.hét március 28. 5. előadás
Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel.
március 30. 5. gyakorlat 
6.hét április 4.
6. előadás
IP feladat, duálisa, optimális megoldás viszonya az LP-hez. TU mátrix definíciója, TU tulajdonságot megőrző operációk. TU mátrixokkal adott IP optimuma. Irányított gráf incidenciamátrixának TU tulajdonsága. Maximális súlyú párosítás LP alakja, ennek duálisa és közgazdaságtani interpretációja, piaci egyensúly.
LP és IP feladat megoldásának bonyolultsága, hálózati folyamok LP alakja, duálisa, pontenciálok. Ford-Fulkerson tétel levezetése a dualitástételből. Idén elmarad: intervallummátrix TU tulajdonsága, intervallumrendszer egyenletes színezése.
Az I. ZH anyaga eddig tart.
április 6. Tavaszi szünet, nincs gyakorlat
7.hét április 11. Tavaszi szünet, nincs előadás
április 13. 6. gyakorlat 
8.hét április 18. 7. előadás
ZH előtti konzultáció
Néhány eddigi gyakorlat megoldása
április 19. 18-20, IB025, I. ZH megoldások
április 20. 7. gyakorlat
ZH megbeszélés
9.hét április 25.
8. előadás
Gráfok magasabb összefüggősége, annak meghatározása folyamalgoritmussal. Blokkok és 2-komponensek. A maxvissza sorrenden alapuló Nagamochi-Ibaraki algoritmus minimális vágás meghatározására.  Gráf 2-(él)összefüggővé tétele minimális számú új él hozzáadásával.
április 27. 8. gyakorlat 
10.hét május 2.
9. előadás
2-(él)összefüggő gráfok fülfelbontása, Robbins tétele erősen összefüggő irányítás létezéséről.
május 3.
18-20, IB025, I. pZH
május 4.
9. gyakorlat
11.hét
május 9.
10. előadás
Közelítő algoritmusok. Élkromatikus szám, síkgráf kromatikus szám közelítése additív hibával. 2-közelítés a lefogó ponthalmaz méretére, logaritmikus közelítés a halmazfedési problémára. Ütemezési problémák. Alapfogalmak, jelölésrendszer, hasznos módszerek: SPT sorrend és listás ütemezés. FF és FFD heurisztikák a ládapakolási problémára.
május 11.
10. gyakorlat
12.hét
május 16.
11. előadás  
Megoldásvázlatok
ZH előtti konzultáció
május 18.
 ZH előtti konzultáció
május 18.  18-20, IB025, II. ZH megoldások
13.hét május 23.
12. előadás
2k-élösszefüggő gráfok előállítási tétele, gráf vágásfüggvényének szubmoduláris tulajdonsága, Lovász leemelési tétele, Nash-Williams tétele k-élösszefüggő irányítás létezéséről. 
május 25.
11. gyakorlat
14.hét május 30.
13. előadás

június 1.

pótlási hét június 5.
8-10, II. pZH IB134




Jegyzet, segédanyag


Jordán Tibor, Recski András, Szeszlér Dávid:
Rendszeroptimalizálás, Typotex Kiadó, 2004.

Ez a jegyzet amellett, hogy az előadáson tárgyalt anyagnál jóval bővebb, elektronikus formában olcsón és könnyen beszerezhető.
 
Ezen kívül még a
korábbi ZH feladatok és a megoldásaik is segítik a felkészülést. (A VISZMA06 kurzus nem teljesen azonos a jelenleg futó VISZMA09-cel, ezért a korábbi ZH-k feladatai az idén számonkért tananyagnak csak egy részét fedi le.)



Értékelés, tárgykövetelmények, vizsga

Zárthelyik, pótzárthelyik, aláírás:

A félév során két 90 perces, négy 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 biztosítjuk pótlás lehetőségét. 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é.
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

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. A szóbeli vizsgán egy tételt sorsolunk a vizsgázónak, aminek a 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ó.