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 - Sztochasztika

    A tantárgy angol neve: Advanced Mathematics for Informaticians - Stochastics

    Adatlap utolsó módosítása: 2017. szeptember 1.

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

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

    Közös tantárgy         

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    TE90MX58 2 4/0/0/v 4  
    3. A tantárgyfelelős személy és tanszék Tóth Imre,
    4. A tantárgy előadója
    Név:Beosztás:Tanszék, Intézet:
    Dr. Rónyai Lajosegyetemi tanárTTK Algebra Tanszék
    Dr. Bálint Péteregyetemi docensTTK Sztochasztika Tanszék
    Dr. Pete Gáboregyetemi docensTTK Sztochasztika Tanszék
    Dr. Tóth Imre Péteregyetemi docensTTK Sztochasztika Tanszék
    5. A tantárgy az alábbi témakörök ismeretére épít Valószínűségszámítás alapjai.
    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyEredmény( "BMETE90MX43" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMETE90MX43", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMETE90MX77" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMETE90MX77", "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 A véletlen és a valószínűségszámítási módszerek fontos szerepet játszanak az informatikában, elsősorban a randomizált algoritmusokon, valamint a sztochasztikus folyamatok elméletén  keresztül. A feldolgozott anyag betekintést nyújt ebbe a világba.  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, a lehetséges alkalmazások körére. Fontos célunk, hogy a hallgatóink képesek legyenek  randomizált algoritmusok tervezésére és elemzésére. 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 1. Valószínűségszámítási alapok ismétlése (4 óra): 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. Létezés és véletlen (4 óra): Véletlent használó egzisztanciabizonyítások (az ún. Erdős-módszer) nevezetes példákon keresztül (hipergráf 2-színezése, Ramsey-gráfok, stb.), ezek algoritmikus vonatkozásai. A Turán-tétel véletlent használó bizonyítása. Derandomizálás.
     
    3. Néhány nevezetes randomizált algoritmus elemzése (8 óra): A gyorsrendezés várható lépésszáma . A Rabin—Miller-prímteszt elemzése. A Schwartz—Zippel-lemma és közvetlen alkalmazásai (Tutte-determináns, mátrixszorzás ellenőrzése). Randomizált mintaillesztés. Minimális feszítőfa számítása lineáris várható időben. Bolyongások és algoritmusok.
     
    4. Lovász lokális lemmája (4 óra): A módszer ismertetése, néhány egyszerű alkalmazása, a módszer algoritmikus változta.
     
    5. Véletlen és bonyolultsági osztályok (8 óra): Az RP és a Las Vegas nyelvosztályok, példákkal. Az IP nyelvosztály: nem izomorrf gráfok, IP=PSPACE lényeges részének a bizonyítása. Nulla ismeretű bizonyítás fogalma, példák. A BPP nyelvosztály, a BPP és a P viszonyával foglalkozó néhány eredmény vázlatos ismertetése. Az RL nyelvosztály.
     
    6. Véletlen gráfok (4 óra): Erdős-Rényi-gráfok, néhány gráftulajdonság (pl. összefüggőség) evolúciója. Barabási-Albert-gráfok, alkalmazásuk (számítógépes-, szociális-, biológiai-) hálózatok modellezésére.
     
    7. Konvergencia típusok (4 óra): Sztochasztikus konvergencia fogalma és a nagy számok gyenge törvénye. L^p-beli konvergencia. Majdnem biztos konvergencia, Borel-Cantelli lemmák és a nagy számok erős törvénye. Valószínűségi eloszlások gyenge konvergenciája és határeloszlás-tételek. 
     
    8. Generátor- és karakterisztikus függvények. Alkalmazásaik: határeloszlások és nagy eltérések (8 óra): Generátorfüggvény, alaptulajdonságai. Konvolúció és keverék-eloszlások generátorfüggvénye. Alkalmazások: elágazó folyamatok, bolyongások. Karakterisztikus függvény, alaptulajdonságai. Fourier-analízis elemei, inverzió, momentum-probléma. Folytonossági tétel, következménye: határeloszlás-tételek. Nagy számok törvényei és centrális határeloszlás tétel karakterisztikus függvény módszerével. Stabilitás, stabilis eloszlások, gyenge konvergencia stabilishoz. Nagy eltérések elemei: Bernstein-egyenlőtlenség, Chernoff-korlát, Cramér-tétel. 
     
    9. Sztochasztikus folyamatok elemei: Markov-láncok és Markov-folyamatok (8 óra): Mi is egy sztochasztikus folyamat? Véges állapotterű Markov-láncok, állapotok osztályozása, irreducibilitás, periódus, aperiodicitás. Lineáris algebrai eszköztár: sztochasztikus mátrixok, hatás előre (függvényekre), hatás hátra (mértékekre). Stacionárius mérték, hosszú idejű viselkedés, ergodicitás. Reverzibilis Markov-láncok, MCMC elemei. Megszámlálható állapotterű Markov-láncok: tranziencia, null-rekurrencia, pozitív rekurrencia jellemzése. Alkalmazás születési-halálozási folyamatokra, bolyongásokra (Pólya-tétel). Folytonos idejű Markov-láncok elemei: Poisson folyamat, ugrási ráták, szemléletes jellemzés. Sztochasztikus mátrixok egy-paraméteres félcsoportja: Kolmogorov-Chapman egyenletek, infinitezimális generátor, kapcsolat mátrix-analízissel.
     
    10. Kitekintés: válogatás a modern valószínűségszámítás problémaköreiből (4 óra): Perkoláció: az alapprobléma, kapcsolat véletlen gráfokkal, alaptételek, fázisátmenet. “Kártyakeverés matematikája”: Markov-láncok konvergenciájának kérdésköre, hányszor keverjük meg a kártyacsomagot, hogy (közel) egyenletes eloszlású véletlen sorrendet kapjunk?
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) A tárgy anyaga előadásokon kerül ismertetésre.
    10. Követelmények
    1. A szorgalmi időszakban: egy összegző értékelés zárthelyi dolgozat formájában. Az aláírás megszerzésének (és egyeben a vizsgára bocsátásnak) a feltétele a dolgozat legalább elégséges szintű teljesítése.
    2. A vizsgaidőszakban: írásbeli teljesítményértékelésből és a félévközi zárthelyi dolgozat eredményének beszámításából álló kombinált vizsga. A vizsgajegy megállapítása felerészben a zárthelyi dolgozat eredménye és felerészben a vizsgadolgozat eredménye alapján történik.

     

    11. Pótlási lehetőségek A zárthelyi a TVSZ szerint egyszer pótolható.
    12. Konzultációs lehetőségek Szükség esetén a számonkérések előtt a hallgatókkal egyeztetve.
    13. Jegyzet, tankönyv, felhasználható irodalom [1] Bollobás: Random Graphs, Cambridge University Press, 2001.
    [2] Rényi: Valószínűségszámítás. Tankönyvkiadó, 1972.
    [3] Rónyai, Ivanyos, Szabó: Algoritmusok. Typotex, 2000.
    [4] Mitzenmacher, Upfal: Probability and Computing. Cambridge University Press, 2005.
    [5] Papadimitriou: Számítási bonyolultság. Novadat, 1999.
    [6] Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
    [7] Prékopa: Valószínűségszámítás műszakiaknak. Műszaki Könyvkiadó Budapest.
    [8] Durrett: Probability: Theory and Examples. Duxbury Press, 1995.
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra

    56

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

    10

    Felkészülés zárthelyire

    14

    Házi feladat elkészítése

    -

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

    -

    Vizsgafelkészülés

    40

    Összesen

    120

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

    Dr. Rónyai Lajos egyetemi tanár, Algebra Tanszék;
    Dr. Tóth Bálint egyetemi tanár, Sztochasztika Tanszék;
    Dr. Szabados Tamás egyetemi docens, Sztochasztika Tanszék;
    Dr. Székely Balázs egyetemi docens, Sztochasztika Tanszék