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ó    

    Felsőbb matematika informatikusoknak - Rendszeroptimalizálás

    A tantárgy angol neve: Advanced Mathematics for Informatics - System Optimisation

    Adatlap utolsó módosítása: 2014. október 1.

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

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

    Felsőbb matematika

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA02 1 4/0/0/v 4  
    3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid, Számítástudományi és Információelméleti Tanszék
    A tantárgy tanszéki weboldala http://cs.bme.hu/rendszeropt
    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

    Dr. Szeszlér Dávid

    egyetemi docens

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

    Dr. Wiener Gábor

    egyetemi docens

    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

    lineáris algebra, gráfelmélet és algoritmuselmélet alapjai

    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZM117" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZM117", "FELVETEL", AktualisFelev()) > 0)

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

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

    1)      Lineáris és egészértékű programozás: Egerváry algoritmusa maximális összsúlyú párosítás és teljes párosítás keresésére páros gráfban. A lineáris programozás alapfeladata, kétváltozós feladatok megoldása grafikusan. Lineáris egyenlőtlenségrendszerek megoldása Fourier-Motzkin eliminációval.

    2)      Lineáris és egészértékű programozás: 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. A lineáris programozás alapfeladata mátrixos alakban.

    3)      Lineáris és egészértékű programozás: Szükséges és elégséges feltételek a lineáris program célfüggvényének korlátosságára. 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.

    4)      Lineáris és egészértékű programozás: Korlátozás és szétválasztás (Branch and Bound) módszer egészértékű programok megoldására. Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások: páros gráfok párosításai, hálózati folyamproblémák.

    5)      Matroidelmélet: Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang). Grafikus, lineáris és uniform matroidok. Mohó algoritmus matroidon. Dualitás, minorok, direkt összeg, összeg.

    6)      Matroidelmélet: Matroidelméleti algoritmusok (partíciós és metszet-algoritmusok, orákulumok). Matroidok reprezentálhatósága különböző testek felett, a grafikus, kografikus, reguláris, bináris és lineáris matroidok kapcsolata.

    7)      Matroidelmélet: 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

    8)      Közelítő algoritmusok: Additív és relatív hibával közelítő algoritmus fogalma, egyszerű példák. A halmazfedési feladat: NP-nehézsége, approximációs algoritmus. A Steiner-fa probléma általános és metrikus esete, approximációk.

    9)      Közelítő algoritmusok:  Az utazóügynök probléma, nevezetes heurisztikák az utazóügynök probléma euklideszi esetére. Teljesen polinomiális approximációs séma fogalma, a részösszeg probléma.

    10)  Ütemezési algoritmusok: Ütemezési feladatok típusai. Egygépes ütemezések, listás ütemező algoritmus párhuzamos gépek esetén. Listás ütemezés LPT, illetve leghosszabb út szerinti sorrendben. Hu algoritmusa, Coffman és Graham algoritmusa. Kapcsolat a ládapakolás feladattal.

    11)  Megbízható hálózatok tervezése: Lokális élösszefüggőség és élösszefüggőségi szám fogalma és meghatározása algoritmikusan. Nagamochi és Ibaraki 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.

    12)  Hálózatelméleti alkalmazások: 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.

    13)  Statikai alkalmazások: 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.

    14)  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)

    Heti 4 óra előadás

    10. Követelmények

     

    Az aláírás feltétele a nagyzárthelyi sikeres megírása.

    A vizsgaidőszakban:

    Szóbeli vizsga.

    Elővizsga: nincs

    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 aláíráspótló vizsgán lehet pótolni.

    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ákra12
    Felkészülés zárthelyire12
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés40
    Összesen120
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Szeszlér Dávid

    egyetemi docens

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