Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    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