Kombinatorikus optimalizálás

A tantárgy angol neve: Combinatorial Optimization

Adatlap utolsó módosítása: 2023. január 11.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Villamosmérnöki Szak MSc

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZMA09   2/2/0/v 5  
3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,
A tantárgy tanszéki weboldala www.cs.bme.hu/villkombopt
4. A tantárgy előadója

Fleiner Tamás

5. A tantárgy az alábbi témakörök ismeretére épít

lineáris algebra, gráfelmélet és algoritmuselmélet alapjai



6. Előtanulmányi rend
Kötelező:
NEM
(TárgyEredmény( "BMEVISZMA06", "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA06", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

7. A tantárgy célkitűzése

A tantárgy az operációkutatás és a kombinatorikus optimalizálás néhány területére nyújt bevezetést. A téma legfontosabb algoritmusainak, módszereinek és ezek korlátainak ismertetése mellett célul tűzi ki, hogy ezek műszaki alkalmazásaiba is betekintést nyújtson. Így terítékre kerülnek olyan átfogó algoritmikus megközelítéseket kínáló területek, mint a hálózati folyamok elmélete és a lineáris és egészértékű programozás, de emellett a tárgy betekintést nyújt a megbízható hálózatok tervezése során felmerülő magasabb összefüggőséggel kapcsolatos problémák mellett a közelítő algoritmusok és az ütemezéselmélet világába is. A tantárgy további célja, hogy a villamosmérnök BSc képzés A számítástudomány alapjai című tantárgya során korábban megszerzett ismereteket alkalmazza, elmélyítse, azok elméleti hátterét jobban megvilágítsa.

8. A tantárgy részletes tematikája
  1. Hálózati folyamok, Ford-Fulkerson-algoritmus, egészértékűségi lemma, a folyamprobléma egyszerű általánosításai.

  2. Páros gráfok karakterizációja, maximális méretű párosítás páros gráfban. Kőnig, Frobenius és Hall tételei.

  3. Gráfszínezések. Alsó és felső korlát a kromatikus számra. Gráfok élszínezése, Vizing tétele. Páros gráfok élszínezése az egészértékűségi lemma segítségével

  4. Egerváry algoritmusa maximális összsúlyú párosítás és teljes párosítás keresésére páros gráfban.

  5. Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata, kétváltozós feladatok megoldása grafikus módszerrel. Lineáris egyenlőtlenségrendszerek megoldása Fourier-Motzkin eliminációval. Szükséges és elégséges feltételek lineáris egyenletrendszerek nemnegatív változókkal való, illetve lineáris egyenlőtlenségrendszerek megoldhatóságára: a Farkas-lemma.

  6. A lineáris programozás alapfeladata mátrixos alakban. Szükséges és elégséges feltételek a lineáris program célfüggvényének korlátosságára. Lineáris program duálisának fogalma, különféle alakban felírt lineáris programok duálisai.

  7. A lineáris programozás dualitástétele. A lineáris programozás feladatának algoritmikus bonyolultsága. Az egészértékű programozás alapfeladata, annak bonyolultsága. Optimalizálási problémák formalizálása egészértékű programozási feladatként.

  8. Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások a páros gráfok párosításainak és a hálózati folyamproblémák területéről: maximális folyam, minimális költségű folyam, ill. többtermékes folyam feladatok.

  9. Lokális él- és pontösszefüggőség, illetve globális él- és pontösszefüggőség fogalma, a vonatkozó Menger-tételek (ismétlés). Max-vissza sorrend, Nagamochi-Ibaraki algoritmusa az élösszefüggőség meghatározására.

  10. Algoritmus gráfok 2-élösszefüggővé növelésére, alsó becslés a szükséges élek számára. Algoritmus minimális költségű feszítő fenyő keresésére. Fülfelbontás, gráfok erősen összefüggővé irányítása.

  11. Közelítő algoritmusok. Élkromatikus szám, síkgráf kromatikus szám közelítése additív hibával, leghosszabb kör additív hibával való közelíthetetlensége. 2-közelítés a lefogó ponthalmaz méretére, logaritmikus közelítés a halmazfedési problémára.

  12. Ütemezési problémák. Alapfogalmak, jelölésrendszer, hasznos módszerek: SPT sorrend és listás ütemezés. FD és FFD heurisztikák a ládapakolási problémára.

  13. Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.


9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

A tárgyhoz előadások és gyakorlatok tartoznak.

10. Követelmények

Szorgalmi időszakban

A szorgalmi időszakban két, zárthelyi dolgozat formájában megírt összegző teljesítményértékelés lesz. Mindkét dolgozat 4-4 feladatból áll, az elérhető összpontszám dolgozatonként 50. Az aláírás feltétele, hogy mindegyik dolgozat pontszáma legalább 20 legyen.

Vizsgaidőszakban

Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik. Megszerzett aláírás esetén megajánlott osztályzat jár a hallgatónak a zárthelyiken élért összpontszáma alapján az alábbiak szerint: 40 ponttól elégséges, 55-től közepes, 70-től jó, 85-től pedig jeles. A megajánlott osztályzat elfogadásáról a pótlási héten kell értesíteni az előadót. Aki elfogadja a megajánlott osztályzatot, az nem jöhet szóbelizni. Aki nem értesíti az előadót az elfogadásról, az szóbeli vizsgán szerezheti meg az érdemjegyét. A szóbelin legfeljebb egy osztályzatot lehet javítani a megajánlott jegyen, rontani korlátlanul lehet.

11. Pótlási lehetőségek

Mindkét zárthelyi dolgozathoz egy pótlási/javítási alkalmat biztosítunk. A szóbeli vizsga javítása a hatályos TVSZ szerint történik.

12. Konzultációs lehetőségek

A ZH előtti gyakorlaton konzultációs lehetőséget biztosítunk. További konzultáció egyeztetés szerint.

13. Jegyzet, tankönyv, felhasználható irodalom
  • Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004.

  • Előadás diasorok


14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra56
Félévközi készülés órákra44
Felkészülés zárthelyire30
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés20
Összesen150
15. A tantárgy tematikáját kidolgozta

Fleiner Tamás


IMSc tematika és módszer N/A
IMSc pontozás N/A