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ó    

    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