Rendszeroptimalizálás

A tantárgy angol neve: System Optimisation

Adatlap utolsó módosítása: 2022. december 22.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar
Mérnökinformatikus MSc
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZMA10   4/0/0/v 5  
3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid,
A tantárgy tanszéki weboldala http://cs.bme.hu/rendszeropt
4. A tantárgy előadója Dr. Kaszanitzky Viktória, egyetemi docens, SZIT
Dr. Recski András, professor emeritus, SZIT
Dr. Szeszlér Dávid, egyetemi docens, SZIT
Dr. Wiener Gábor, egyetemi docens, SZIT
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( "BMEVISZMA02", "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA02", "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 azok korlátainak ismertetése mellett célul tűzi ki, hogy ezek gyakorlati alkalmazási lehetőségeit is bemutassa. A tantárgy által érintett főbb témakörök: lineáris- és egészértékű programozás, közelítő algoritmusok és ütemezési algoritmusok.

A tantárgy további célja, hogy a mérnökinformatikus BSc képzés Bevezetés a számításelméletbe 1 és 2, valamint Algoritmuselmélet című tárgyai 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-2. Lineáris és egészértékű programozás: A páros gráfban maximális méretű párosítás keresésére szolgáló javító utas algoritmus ismétlése. Egerváry algoritmusa maximális összsúlyú párosítás és teljes párosítás keresésére páros gráfban.

3-4. Lineáris és egészértékű programozás: A lineáris programozás alapfeladata, a megoldhatóság és korlátosság kérdései. Kétváltozós lineáris programozási feladatok grafikus megoldása. A lineáris programozás bonyolultsága. Gyakorlati életben felmerülő problémák formalizálása lineáris programozási feladatként.

5-6. Lineáris és egészértékű programozás: Az egészértékű programozás alapfeladata, annak bonyolultsága. Korlátozás és szétválasztás (Branch and Bound) módszer egészértékű programok megoldására. Gyakorlati életben felmerülő problémák formalizálása egészértékű programozási feladatokként.

7-8. Lineáris és egészértékű programozás: A lineáris programozás alapfeladatának mátrixos alakja. 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.

9-10. Lineáris és egészértékű programozás: Szükséges és elégséges feltételek a lineáris program célfüggvényének korlátosságára. A lineáris programozás dualitástétele.

11-12. Lineáris és egészértékű programozás: Hálózati folyamfeladatok formalizálása lineáris programozási feladatként: a maximális folyam, a minimális költségű folyam, illetve a többtermékes folyamprobléma.

13-14. Lineáris és egészértékű programozás: Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások páros gráfok párosításaival, hálózati folyamokkal és intervallumrendszerek színezésével kapcsolatos problémákra.

15-16. Közelítő algoritmusok: NP-nehéz problémák kezelése. NP-nehéz problémák polinomiális időben megoldható speciális esetei: erőforrások ütemezése, maximális független ponthalmaz keresése, élszínezés.

17-18. Közelítő algoritmusok: Additív hibával közelítő algoritmus fogalma. Additív hibával közelítő algoritmusok színezési problémákra, a leghosszabb kör keresésének feladata. Multiplikatív hibával közelítő algoritmus fogalma, a maximális páros részgráf probléma.

19-20. Közelítő algoritmusok: A minimális lefogó ponthalmaz probléma. A súlyozott halmazfedési feladat: NP-nehézsége, approximációs algoritmus.

21-22. Közelítő algoritmusok: Steiner-fák: approximációs algoritmus a metrikus és az általános esetre. Az utazóügynök probléma, 2-approximációs algoritmus az utazóügynök probléma metrikus esetére.

23-24. Közelítő algoritmusok: Christofides algoritmusa az utazóügynök probléma metrikus esetére. Teljesen polinomiális approximációs séma fogalma, a részösszeg probléma.

25-26. Ütemezési algoritmusok: Ütemezési feladatok típusai. Egygépes ütemezések, listás ütemező algoritmus párhuzamos gépek esetén. Listás ütemezés LPT, illetve leghosszabb út szerinti sorrendben megelőzési feltételekkel és azok nélkül, Hu algoritmusa.

27-28. 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) Heti 4 óra előadás

Mindegyik előadás második felében önálló feladatmegoldás zajlik.
10. Követelmények

Szorgalmi időszakban:

 

Zárthelyi dolgozat:

A félév folyamán egyetlen zárthelyit íratunk. A félévvégi aláírás megszerzésének feltétele a zárthelyin legalább 40%-os eredmény elérése.

Nagy házi feladat:

Két beadandó házi feladatot tűzünk ki: egyet a lineáris és egészértékű programozás, egyet pedig a közelítő és ütemezési algoritmusok anyagrészből. Ezeknek a feladatoknak a megoldása a megfelelő, tanult anyagrészek gyakorlati alkalmazását kívánja meg. A nagy házi feladatok beadása és azoknak az elfogadása feltétele a tárgyból kapható megajánlott jegy megszerzésének (lásd alább).

Korábbi félévben szerzett aláírás:

Azok a hallgatók, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyit, hogy a korábbi zárthelyi eredményein javítsanak. Erre az esetre az alábbi feltételek vonatkoznak:

  • Ha sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe (lásd lentebb) az így kapott eredmény számít bele (akkor is, ha ez rosszabb).
  • Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be.
  • Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését.

Vizsgaidőszakban:

 

A tárgy vizsgajegye kétféleképpen szerezhető meg.

Megajánlott jegy:

Megajánlott vizsgajegy megszerzéséhez két feltételt kell teljesíteni:

  • a két nagy házi feladat (lásd fentebb) beadása és elfogadása;
  • a zárthelyin (beleértve a pótlásokat is) legalább 55%-os eredmény elérése.

Azoknak, akik ezeket teljesítik, a zárthelyin elért eredményük alapján ajánlunk meg vizsgajegyet:

  • legalább 55%-os eredményért elégséges,
  • legalább 70%-os eredményért közepes,
  • legalább 85%-os eredményért pedig jó

vizsgajegyet ajánlunk meg.

Megajánlott jegyet vizsgakurzuson nem lehet szerezni.

Szóbeli vizsga:

Aki aláírással rendelkezik, de a zárthelyivel és a nagy házi feladatokkal nem szerzett (legalább elégséges) megajánlott jegyet, vagy a megszerzett megajánlott jegyén javítani szeretne, az a vizsgaidőszakban szóbeli vizsgát tehet. Ha egy hallgató jelentkezik a Neptunban a vizsgára, akkor a megajánlott jegyét a továbbiakban nem tekintjük érvényesnek. Ilyenkor a vizsgajegyben a zárthelyi eredményét 40%-os súllyal vesszük figyelembe.

11. Pótlási lehetőségek A zárthelyit a szorgalmi időszakban írt pótzárthelyin vagy a pótlási héten írt díjköteles pótlási alkalmon lehet pótolni. Ezeken korábban megírt, eredményes zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: ha a hallgató az aláíráshoz szükséges 40%-os eredményt elérte, de a javítónak szánt zárthelyi új pontszáma 40% alatti, akkor a hallgató az aláírást megkapja, de a zárthelyi eredményét a vizsgán 40%-oskét vesszük figyelembe. Ha azonban egy hallgató egy zárthelyin legalább 55%-os eredményt ér el, majd egy javítónak szánt új zárthelyin 55% alatti eredményt ér el, akkor a (fentiek szerinti) megajánlott jegyét elveszíti.

A beadott, de el nem fogadott nagy házi feladatok tetszőleges számú alkalommal újra beadhatók, amíg elfogadásra nem kerülnek. A nagy házi feladatok (utolsó) beadására a pótlási hét utolsó előtti munkanapjának végéig van lehetőség.
12. Konzultációs lehetőségek Előzetes 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, 2011.

A közelítő algoritmusok és az ütemezési algoritmusok anyagrészhez a tárgy honlapján elérhető online jegyzet is rendelkezésre áll: https://cs.bme.hu/rendszeropt/kozelito.pdf

Ugyancsak elérhető a tárgy honlapján egy online jegyzet a lineáris és egészértékű programozás anyagrész végéhez, az "Egészértékű programozás totálisan unimoduláris együtthatómátrixszal" témakörhöz: https://cs.bme.hu/rendszeropt/ip+tu.pdf

A zárthelyikre való felkészülést az elmúlt több, mint 10 év zárthelyi példasorai és az azokhoz készült pontozási útmutatók segítik, melyek szintén a honlapról érhetők el.
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ákra28
Felkészülés zárthelyire18
Házi feladat elkészítése12
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés36
Összesen150
15. A tantárgy tematikáját kidolgozta Dr. Szeszlér Dávid, egyetemi docens, SZIT