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ó    

    Felsőbb matematika informatikusoknak - Rendszeroptimalizálás

    A tantárgy angol neve: Advanced Mathematics for Informatics - System Optimisation

    Adatlap utolsó módosítása: 2019. december 10.

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

    Mérnökinformatikus szak, MSc képzés

    Felsőbb matematika

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA02 1 4/0/0/v 4  
    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

    Név:

    Beosztás:

    Tanszék, Int.:

    Csehi Csongor Györgyegyetemi tanársegéd
     Számítástudományi és Információelméleti Tanszék

    Dr. Recski András

    egyetemi tanár

    Számítástudományi és Információelméleti Tanszék

    Dr. Szeszlér Dávid

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

    Dr. Wiener Gábor

    egyetemi docens

    Számítástudományi  és Információelméleti Tanszék

    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( "BMEVISZM117" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZM117", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZMA10" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA10", "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 életbeli 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, ütemezési algoritmusok és  megbízható hálózatok tervezése.

    8. A tantárgy részletes tematikája

    1)      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.

    2)      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.

    3)      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.

    4)      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.

    5)      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.

    6)      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.

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

    8)      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.

    9)      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.

    10)  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.

    11)  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.

    12)  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.

    13)  Ü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.

    14)  Megbízható hálózatok tervezése: Lokális élösszefüggőség és élösszefüggőségi szám fogalma és meghatározása algoritmikusan. Nagamochi és Ibaraki algoritmusa. Minimális méretű 2-élösszefüggő, illetve 2-összefüggő részgráfok keresése: Khuller-Vishkin és Cheriyan-Thurimella algoritmus. Gráfok 2-élösszefüggővé növelése: Plesnik algoritmusa.

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

    Heti 4 óra előadás

    10. Követelmények 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 teljesítmény elérése. A zárthelyin elért, ennél jobb eredménnyel a tárgy vizsgajegye is megszerezhető: 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.

    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.

    A vizsgaidőszakban:

    Aki a zárthelyivel nem szerzett (legalább elégséges) vizsgajegyet vagy a zárthelyi eredménye alapján 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 zárthelyi eredménye alapján 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.

    Elővizsga: nincs

    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 aláíráspótló vizsgán 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.

    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.

     


    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ákra12
    Felkészülés zárthelyire12
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés40
    Összesen120
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Szeszlér Dávid

    egyetemi docens

    Számítástudományi  Információelméleti Tanszék