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 B

    A tantárgy angol neve: Advanced Mathematics for Electrical Engineers B

    Adatlap utolsó módosítása: 2010. február 4.

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

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

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    TE90MX38 1 4/2/0/v 6 1/1
    3. A tantárgyfelelős személy és tanszék Dr. Tóth Bálint,
    4. A tantárgy előadója
    Név:Beosztás:Tanszék, Intézet:
    Dr. Recski Andrásegyetemi tanárSzámtud. és Infoelm. Tsz.
    Dr. Szeszlér Dávidegyetemi adjunktusSzámtud. és Infoelm. Tsz.
    Dr. Wiener Gáboregyetemi adjunktusSzámtud. és Infoelm. Tsz.
    Dr. Szabados Tamásegyetemi docensSztochasztika Tanszék
    Dr. Székely Balázs egyetemi adjunktusSztochasztika Tanszék
    Dr. Tóth Bálintegyetemi tanárSztochasztika Tanszék
    Dr. Vetier Andrásegyetemi docensSztochasztika Tanszék
    5. A tantárgy az alábbi témakörök ismeretére épít

    Kombinatorika és valószínűségszámítás alapjai

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

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

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    Ajánlott:
    ---
    7. A tantárgy célkitűzése Kombinatorikus optimalizálás. 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 korlátainak ismertetése mellett célul tűzi ki, hogy ezek műszaki alkalmazásaiba is betekintést nyújtson. A szemeszter első felében olyan átfogó, általános módszereket mutat be, amelyek a gyakorlati élet számtalan területén eredményesen alkalmazhatónak bizonyultak. Így terítékre kerül a lineáris programozás, a matroidelmélet, a közelítő algoritmusok, valamint az ütemezési algoritmusok témaköre. A félév második felében három olyan műszaki esettanulmányt tárgyal, amelyek részben a fenti általános módszerek, részben a kombinatorikus szemléletű megközelítés eredményességét és hatékonyságát illusztrálják. Így betekintést nyújt a megbízható hálózatok tervezése, a villamos hálózatok klasszikus elmélete és a nagy bonyolultságú hálózatok huzalozása kapcsán felmerülő kombinatorikus jellegű feladatokba. 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. A tantárgy követelményeit eredményesen teljesítő minden hallgatótól elvárható, hogy:
    – értse és konkrét feladatokban, példákon alkalmazni tudja a tárgyalt fogalmakat és ismereteket,
    – a gyakorlati élet által felvetett problémákban felismerje a tanult módszerek alkalmazási lehetőségeit,
    – példákon keresztül illusztrálni tudja a kombinatorikus optimalizálás gyakorlati alkalmazási lehetőségeit.

    Sztochasztika. A valószínűségszámítás és sztochasztikus folyamatok elmélete néhány haladóbb témakörének bemutatása a villamosmérnöki mesterképzésben résztvevő hallgatóknak. A hangsúlyokat a jelenségek megértetésére és az alkalmazásokra helyezzük. Széles körben (a tantárgy témakörén kívül is) alkalmazható technikákat prezentálunk, rávilágítunk más matematikai és matematikán kívüli természettudományos és műszaki területekkel való összefüggésekre. Alapelv: minden egyes témához sok konkrét példát, számolást, konkrét alkalmazást mutatunk be. Bizonyításokat többnyire csak vázlatosan prezentálunk, viszont hangsúlyt helyezünk a szemléletre és a (matematikai és egyéb) jelenségekre.

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

    Kombinatorikus optimalizálás. (7 tényleges oktatási hét: 28 előadási  + 14 gyakorlati óra).

    1. Lineáris programozás (8 óra elmélet/előadás + 4 óra gyakorlat ): A lineáris programozás alapfeladata. 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, illetve hálózati folyamokra.

    2. Matroidelmélet (6 óra elmélet/előadás + 3 óra gyakorlat). 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).

    3. Közelítő algoritmusok (3 óra elmélet/előadás + 1 óra gyakorlat). 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.

    4. Ütemezési algoritmusok (3 óra elmélet/előadás + 2 óra gyakorlat). Ü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 (2 óra elmélet/előadás + 1 óra gyakorlat). 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 (3 óra elmélet/előadás + 2 óra gyakorlat). 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.

    7. Hálózatelméleti alkalmazások (3 óra elmélet/előadás + 1 óra gyakorlat). 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.

    Sztochasztika (7 tényleges oktatási hét: 28 előadási  + 14 gyakorlati óra).

    1. Valószínűségszámítási alapok ismétlése, eloszlások “függvénytana” (4 óra ea, 2 óra gyak). Valószínűségi változó, eloszlásfüggvény, sűrűségfüggvény. Várható érték, szórásnégyzet, magasabb momentumok. Nevezetes eloszlások. Együttesen értelmezett valószínűségi változók, együttes eloszlás- és sűrűségfüggvény. Várható érték vektor, kovariancia mátrix, alaptulajdonságai, Cauchy-Schwarz-egyenlőtlenség. Nevezetes többdimenziós eloszlások. Sűrűségfüggvények transzformációja leképezésekkel. Többdimenziós normális eloszlás.


    2. Generátor- és momentumgeneráló függvények. Határeloszlások és nagy eltérések (8 óra ea, 4 óra gyak). Generátorfüggvény, alaptulajdonságai. Konvolúció és keverék-eloszlások generátorfüggvénye. Alkalmazások, elágazó folyamatok. Momentumgeneráló függvény, tulajdonságok. Centrális határeloszlás tétel. Nagy eltérések elemei: Bernstein- egyenlőtlenség, Chernoff-korlát, Höeffding-egyenlőtlenség, Kramer-tétel. Alkalmazások sorbanállási problémákra és kapacitás méretezésre.

    3. Sztochasztikus folyamatok elemei: Markov-láncok és Markov-folyamatok (8 óra ea, 4 óra gyak). Mi is egy sztochasztikus folyamat? Véges állapotterű Markov-láncok, állapotok osztályozása, irreducibilitás, periódus, aperiodicitás. Stacionárius mérték, hosszú idejű viselkedés, ergodicitás. Megszámlálható állapotterű Markov-láncok. Alkalmazás születési-halálozási folyamatokra és sorbanállási problémákra. Folytonos idejű Markov-láncok elemei: Poisson folyamat, ugrási ráták, szemléletes jellemzés. Kolmogorov-Chapman egyenletek, infinitezimális generátor. Sorbanállási alkalmazások.

    4. A matematikai statisztika elemei (4 óra ea, 2 óra gyak). Mintavétel, becslések, hipotézisek, statisztikai próbák: u-próba, t-próba, F-próba, khi-négyzet-próba. Maximum likelihood becslés. Lineáris és nemlineáris regresszió.

    5. Gyengén stacionárius folyamatok: spektrál-felbontás, spektrál-elmélet elemei (4 óra ea, 2 óra gyak). Gyengén stacionárius folyamatok Z-n, R-en, jellemzésük a kovariancia-függvénnyel, realizációjuk Gauss-folyamatként. Trigonometrikus folyamatok, autoregresszív és mozgó átlag folyamatok. Stacionárius folyamat spektrális felbontása. Példák. Szűrés, példák szűrőkre.

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

    A tárgy anyaga előadásokon és gyakorlatokon kerül ismertetésre.

    10. Követelmények

    a.              A szorgalmi időszakban: két zárthelyi

    b.             A vizsgaidőszakban: a két tárgyblokkból közös vizsga. A vizsgajegy megállapítása felerészben a zárthelyik eredménye és felerészben a vizsga alapján történik

    Az aláírás megszerzésének feltétele a zárthelyi dolgozatok teljesítése egyenként legalább 40%-ra. A vizsgára bocsátás feltétele az aláírás megléte.

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

    -         mindenki legfeljebb egy zárthelyit pótolhat, de azt esetleg kétszer

    -         két pótzárthelyit tartunk a szorgalmi időszakban, de minden hallgató legfeljebb az egyiken vehet részt (akinek két sikertelen zh-ja van, nem kaphat aláírást)

    -         egy további pót-pótzárthelyit tartunk a pótlási héten (két feladatsorral, amelyiken mindenki a pótlandó (egy) zárthelyijét pótolhatja).

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

    Vizsgák előtt a hallgatókkal egyeztetve.

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

    [1]       Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004.

    [2]       Prékopa András: Valószínűségszámítás műszakiaknak. Műszaki Könyvkiadó Budapest.

    [3]       Rényi Alfréd: Valószínűségszámítás. Tankönyvkiadó Budapest, 1972.

    [4]       Richard Durrett: Probability: Theory and Examples. Duxbury Press, 1995.

     

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra84
    Félévközi készülés órákra30
    Felkészülés zárthelyire30
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés36
    Összesen180