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: 2006. július 1.

    Tantárgy lejárati dátuma: 2015. január 31.

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

    Műszaki Informatika Szak

    5. évfolyam - Elágazó II.

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

    -

    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

    Kontakt óra

    60

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

    15

    Felkészülés zárthelyire

    15

    Házi feladat elkészítése

    10

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

    ..

    Vizsgafelkészülés

    50

    Ö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