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 villamosmérnököknek - Kombinatorikus optimalizálás

    A tantárgy angol neve: Advanced Mathematics for Electrical Engineers - Combinatorial Optimization

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

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

    Villamosmérnöki szak, MSc képzés

    Felsőbb matematika

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA06 1 2/1/0/f 3  
    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/villkombopt
    4. A tantárgy előadója

    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

    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( "BMETE90MX38" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMETTE90MX38", "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

    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 ezek korlátainak ismertetése mellett célul tűzi ki, hogy ezek műszaki alkalmazásaiba is betekintést nyújtson. Így terítékre kerülnek olyan átfogó algoritmikus megközelítéseket kínáló területek, mint  a lineáris és egészértékű programozás és a matroidelmélet, de emellett a tárgy betekintést nyújt a  megbízható hálózatok tervezése során felmerülő problémákba is. A tantárgy további célja, hogy a villamosmérnök BSc képzés A számítástudomány alapjai című tantárgya 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 és egészértékű programozás: Maximális méretű párosítás feladata páros gráfban: a javító utas algoritmus (ismétlé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.

    2)      Lineáris és egészértékű programozás: A lineáris programozás alapfeladata, kétváltozós feladatok megoldása grafikusan módszerrel. Lineáris egyenlőtlenségrendszerek megoldása Fourier-Motzkin eliminációval.

    3)      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.

    4)      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. Lineáris program duálisának fogalma általános alakban, illetve nemnegatív változók esetén is.

    5)      Lineáris és egészértékű programozás:  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.

    6)      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. Gyakorlati életben felmerülő problémák formalizálása egészértékű programozási feladatként.

    7)      Lineáris és egészértékű programozás: Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások a páros gráfok párosításainak területéről. Alkalmazások a hálózati folyamproblémák területéről: maximális folyam, minimális költségű folyam, többtermékes folyam feladatok.

    8)      Matroidelmélet: Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang). Nevezetes példák. Függetlenségi axiómák, bázisaxiómák és köraxiómák. Mohó algoritmus matroidon. A matroid két definíciójának ekvivalenciája.

    9)      Matroidelmélet: Matroid duálisának fogalma, kapcsolata a gráfelméleti duálissal. Elhagyás és összehúzás, kapcsolatuk a duálissal. Matroidok minorjai. Matroidok csonkolása, direkt összege és összege.

    10)  Matroidelmélet: Matroidelméleti algoritmusok: partíciós és metszet-algoritmusok. Matroidok megadása orákulummal. Példák és alkalmazások: párosítások páros gráfokban, fenyők, irányított Hamiton-utak.

    11)  Matroidelmélet: Nevezetes matroidosztályok: grafikus, ko-grafikus és lineáris matroidok. A grafikus matroidok reprezentálhatósága. A duális matroid és matroid minorjának reprezentálhatósága.

    12)  Megbízható hálózatok tervezése: Lokális él- és pontösszefüggőség, illetve globális él- és pontösszefüggőség fogalma, a vonatkozó Menger-tételek (ismétlés). Max-vissza sorrend, Nagamochi-Ibaraki algoritmusa az élösszefüggőség meghatározására.

    13)  Megbízható hálózatok tervezése: Algoritmus gráfok 2-élösszefüggővé növelésére, alsó becslés a szükséges élek számára. Algoritmus minimális költségű feszítő fenyő keresésére. Fülfelbontás, gráfok erősen összefüggővé irányítása.

    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 2 óra előadás és 1 óra gyakorlat.

    10. Követelmények

    A félév során három zárthelyi dolgozat lesz. A félév teljesítésének feltétele: minden zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a három zárthelyi átlagából adódik.

    11. Pótlási lehetőségek

    A szorgalmi időszakban minden zárthelyi dolgozathoz lesz pótlási (javítási) lehetőség. A pótlási héten írt második pótzárthelyi alkalmával egy tetszőleges zárthelyi dolgozat pótolható.

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

    Egyéni 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 óra42
    Félévközi készülés órákra9
    Felkészülés zárthelyire9
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés30
    Összesen90
    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