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 Optimisation

    Adatlap utolsó módosítása: 2009. szeptember 22.

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

     

    Doktori választható tárgy

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMAD238 ősz 4/0/0/v 5 1/1
    3. A tantárgyfelelős személy és tanszék Dr. Recski András,
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    egyetemi tanár

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

    Szeszlér Dávid

    egyetemi tanársegéd

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

    Wiener Gábor

    egyetemi adjunktus

    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

    A Bevezetés a Számításelméletbe I. és II. , valamint az Algoritmuselmélet tárgyak anyaga.

    6. Előtanulmányi rend
    Ajánlott:

    : -

    Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat: BMEVIMA5311 vagy BMEVISZM117 Rendszeroptimalizálás

    7. A tantárgy célkitűzése

    A kombinatorikus optimalizálás legfontosabb algoritmusainak, módszereinek, korlátainak ismertetése, valamint betekintés ezek műszaki alkalmazásaiba (megbízható hálózatok tervezése, villamos hálózatok klasszikus elmélete, VLSI tervezés, statika területeken).

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

    A lineáris programozás alapfeladata, megoldási módszerek, Farkas-lemma, dualitás, egészértékű programozás. Totális unimodularitás, alkalmazás páros gráfokra, Egerváry algoritmusa, alkalmazás hálózati folyamokra.

    Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang), dualitás, minorok, direkt összeg, összeg. Matroidelméleti algoritmusok (mohó algoritmus, matroid partíciós és metszet-algoritmusok, orákulumok). Matroid párosítási probléma. Matroidok és gráfok kapcsolata, vektorreprezentáció, geometriai reprezentáció. Tutte tételei (biz. nélkül).

    Közelítő algoritmusok, halmazfedési feladat, Steiner-fák, utazó ügynök probléma, nevezetes heurisztikák az utazó ügynök probléma euklideszi esetére.

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

    Alkalmazások a megbízható hálózatok tervezésében, az összefüggőség kiszámítása, Nagamochi és Ibaraki algoritmusa, Karger algoritmusa. Többszörösen összefüggő részgráfok, Khuller és Vishkin algoritmusa, Cheriyan és Thurimella algoritmusa. Az összefüggőség növelése, Plesnik algoritmusa.

    Alkalmazások a VLSI hálózatok huzalozásában (Gallai tétele és az egyetlen pontsor huzalozhatósága a Manhattan-modellben, csatornahuzalozás 2 és több rétegen, ˛switchbox˛-huzalozás több rétegen, Frank A. tétele az éldiszjunkt huzalozásra és ennek következményei).

    Alkalmazások a villamos hálózatok klasszikus elméletében, hálózatok egyértelmű megoldhatósága, a szabadsági fokok száma. Általánosítás többpólusú lineáris alkatrészeket is tartalmazó hálózatokra. Dualitás.

    Alkalmazások a rúdszerkezetek merevségének vizsgálatában, a probléma kitűzése, átfogalmazása lineáris algebrai feltétellé, a merevség definíciója, generikus merevség, Laman tétele, Lovász és Yemini tétele, a 3-dimenziós analógia nehézségei, kapcsolat a poliéderek vetületből való rekonstrukciójával, minimális számú csuklóval való rögzítés. Négyzetrácsok merevítése étlós rudakkal.

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

    (előadás, gyakorlat, laboratórium):

    előadás

    10. Követelmények

    a. A szorgalmi időszakban: egy zárthelyi, egy beadandó házi feladat

    b. A vizsgaidőszakban: szóbeli vizsga

    1. Elővizsga: nincs rá lehetőség.
    11. Pótlási lehetőségek

    Az elégtelen zárthelyi javítására, vagy a zárthelyi pótlására lehetőséget biztosítunk a szorgalmi időszak végén.

    12. Konzultációs lehetőségek

    Egyéni megbeszélés alapján.

    13. Jegyzet, tankönyv, felhasználható irodalom

    Dr. Jordán Tibor - Dr. Recski András –- Szeszlér Dávid: Rendszeroptimalizálás, Typotex, Budapest, 2004

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

    (a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

     

    Kontakt óra

    56

    Félévközi készülés órákra

    9

    Felkészülés zárthelyire

    9

    Házi feladat elkészítése

    36

    Kijelölt írásos tananyag elsajátítása

    ..

    Vizsgafelkészülés

    40

    Összesen

    150

    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    egyetemi tanár

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