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: 2008. november 10.

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

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


     
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZM117 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

    Dr. Recski András egyetemi tanár, Dr. Szeszlér Dávid egyetemi docens, Dr. Wiener Gábor egyetemi docens

    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 korlátainak ismertetése mellett célul tűzi ki, hogy ezek műszaki alkalmazásaiba is betekintést nyújtson. A szemeszter első felében olyan átfogó, általános módszereket mutat be, amelyek a gyakorlati élet számtalan területén eredményesen alkalmazhatónak bizonyultak. Így terítékre kerül a lineáris programozás, a matroidelmélet, a közelítő algoritmusok, valamint az ütemezési algoritmusok témaköre. A félév második felében négy olyan műszaki esettanulmányt tárgyal, amelyek részben a fenti általános módszerek, részben a kombinatorikus szemléletű megközelítés eredményességét és hatékonyságát illusztrálják. Így betekintést nyújt a megbízható hálózatok tervezése, a villamos hálózatok klasszikus elmélete, a nagy bonyolultságú hálózatok huzalozása és a statika területén felmerülő kombinatorikus jellegű feladatokba.

     

    A tantárgy további célja, hogy a mérnökinformatikus BSc képzés Bevezetés a számításelméletbe I. és II., 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. Lineáris programozás (16 óra):

    A lineáris programozás alapfeladata, megoldási módszerek, a probléma bonyolultsága. Farkas-lemma, a lineáris programozás dualitástétele. Egészértékű programozás, a feladat bonyolultsága, korlátozás és szétválasztás (Branch and Bound). Totálisan unimoduláris mátrixok és alkalmazásuk páros gráfokra, Egerváry algoritmusa, alkalmazás hálózati folyamokra.

    2. Matroidelmélet (12 óra):

    Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang). Mohó algoritmus matroidon. Dualitás, minorok, direkt összeg, összeg. Matroidelméleti algoritmusok (partíciós és metszet-algoritmusok, orákulumok). Grafikus, kografikus, reguláris, bináris és lineáris matroid fogalma, ezek kapcsolata. Bináris, reguláris és grafikus matroidok jellemzése tiltott minorokkal, Tutte tételei, Seymour tétele. A k-polimatroid rangfüggvény fogalma. A 2‑polimatroid-matching probléma, ennek bonyolultsága

     

    3. Közelítő algoritmusok (4 óra):Additív és relatív hibával közelítő algoritmus fogalma. Halmazfedési feladat, a Steiner-fa probléma, utazó ügynök probléma, nevezetes heurisztikák az utazó ügynök probléma euklideszi esetére. Polinomiális approximációs séma, a részösszeg probléma.

     

    4. Ütemezési algoritmusok (4 óra):

    Ütemezési feladatok típusai. Egygépes ütemezések, listás ütemező algoritmus párhuzamos gépek esetén, Hu algoritmusa, Coffman és Graham algoritmusa.

    5. Megbízható hálózatok tervezése (4 óra):

    Lokális élösszefüggőség és élösszefüggőségi szám fogalma. Nagamochi és Ibaraki algoritmusa, Karger algoritmusa. Minimális méretű 2-élösszefüggő, illetve 2-összefüggő részgráfok keresése, Khuller és Vishkin algoritmusa, Cheriyan és Thurimella algoritmusa. Gráfok 2-élösszefüggővé növelése, Plesnik algoritmusa.

    6. Nagybonyolultságú hálózatok huzalozása (4 óra):

    A részletes huzalozás feladata. Egyetlen pontsor huzalozása a Manhattan modellben, Gallai algoritmusa. Csatornahuzalozás 2 rétegen a megszorítás nélküli, illetve több rétegen a Manhattan modellben. Switchboxhuzalozás több rétegen. Éldiszjunkt huzalozás, Frank tétele.

    7. Hálózatelméleti alkalmazások (4 óra):

    Klasszikus villamos hálózatok egyértelmű megoldhatósága, Kirchhoff tételei. Általánosítás a transzformátorokat vagy girátorokat is tartalmazó hálózatokra, algoritmusok a feltételek ellenőrzésére. Általánosítás lineáris sokkapukat tartalmazó hálózatokra. Villamos hálózatok duálisa.

    8. Statikai alkalmazások (4 óra)

    Rúdszerkezetek merevségének vizsgálata, a probléma lineáris algebrai megfogalmazása. A rudakban ébredő erők kiszámítása, Maxwell-Cremona diagram. A generikus merevség fogalma, Laman tétele, Lovász és Yemini tétele. Síkbeli négyzetrácsok és egyszintes épületek átlós merevítése.
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) előadás
    10. Követelmények
    • szorgalmi időszakban: az aláírás feltétele egy nagyzárthelyi sikeres megírása, továbbá a lineáris programozás anyagrészből egy beadandó házi feladat elkészítése. A házi feladatot névre szólóan adjuk ki, ezek hallgatónként különbözők.
    • vizsgaidőszakban: szóbeli vizsga
    11. Pótlási lehetőségek

    A nagyzárthelyit a szorgalmi időszakban írt pótzárthelyin, vagy a pótlási héten írt pótpótzárthelyin (ez a Neptunban aláíráspótló vizsga néven szerepel) lehet pótolni.

    A házi feladat késedelmes leadásának határideje a pótlási időszak vége.

    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.
    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ákra9
    Felkészülés zárthelyire9
    Házi feladat elkészítése6
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés40
    Összesen120
    15. A tantárgy tematikáját kidolgozta Dr. Recski András egyetemi tanár, Dr. Szeszlér Dávid egyetemi docens, Dr. Wiener Gábor egyetemi docens