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: 2009. május 7.

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

    Matematikus mesterszak

    Alkalmazott matematikus mesterszak
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZM029   3/1/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid,
    4. A tantárgy előadója

    Dr. Recski András

    Dr. Szeszlér Dávid

    Salamon Gábor

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

    . 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 és gyakorlat
    10. Követelmények Egy félévközi ZH, ennek legalább elégséges teljesítése a vizsgára bocsátás feltétele
    11. Pótlási lehetőségek TVSZ szerint
    12. Konzultációs lehetőségek Egyéni igény alapján
    13. Jegyzet, tankönyv, felhasználható irodalom

    Jordán Tibor, Recski András és Szeszlér Dávid: Kombinatorikus optimalizálás, Typotex

    Kiadó, Budapest, 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ákra14
    Felkészülés zárthelyire20
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés60
    Összesen150
    15. A tantárgy tematikáját kidolgozta Dr. Recski András és Dr. Szeszlér Dávid