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 D

    A tantárgy angol neve: Advanced Mathematics for Informaticians D

    Adatlap utolsó módosítása: 2008. december 17.

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

    Mérnök informatikus szak
    MSc képzés
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    TE90MX43 1 4/0/0/v 4 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. Tóth Bálintegyetemi tanárSztochasztika Tanszék
    Dr. Szabados Tamásegyetemi docensSztochasztika Tanszék
    Dr. Vetier Andrásegyetemi docensSztochasztika Tanszék
    Dr. Székely Balázsegyetemi adjunktusSztochasztika Tanszék
    5. A tantárgy az alábbi témakörök ismeretére épít

    Sztochasztika elemei

    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyEredmény( "BMETE90MX58" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMETE90MX58", "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

    Sztochasztika 1. 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 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, és rávilágítunk a lehetséges alkalmazások körére.  A legfontosabb 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 alkalmazást mutatunk be. Bizonyításokat többnyire csak vázlatosan prezentálunk, viszont hangsúlyt helyezünk a szemléletre.

    Sztochasztika 2. 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 mérnök informatikus 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 Sztochasztika 1. (7 tényleges oktatási hét: 26 előadási óra). 1. 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.

    2. 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.

    3. Lovász lokális lemmája (2 óra). A módszer ismertetése, néhány egyszerű alkalmazása, a módszer algoritmikus változta.

    4. Véletlen és bonyolultsági osztályok (8 óra ea). 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.

    5. 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.

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

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

    3. Generátor- és karakterisztikus függvények. Alkalmazásaik: határeloszlások és nagy eltérések (8 óra). Generátor függvény, alaptulajdonságai. Konvolúció és keverék-eloszlások generátor-fü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, Kramer-tétel. 4. Sztochasztikus folyamatok elemei: Markov-láncok és Markov-folyamatok (8 óra ea). 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.

    5. Kitekintés: válogatás a modern valószínűségszámítás problémaköreiből. (4 óra ea). 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

    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]       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 óra56
    Félévközi készülés órákra10
    Felkészülés zárthelyire28
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés26
    Összesen120
    15. A tantárgy tematikáját kidolgozta
    Név:Beosztás:Tanszék, Int.:
    Dr. Rónyai Lajosegyetemi tanárAlgebra Tanszék
    Dr. Tóth Bálintegyetemi tanárSztochasztika Tanszék