BME VIK - Felsőbb matematika informatikusoknak D

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álint	egyetemi tanár	Sztochasztika Tanszék
Dr. Szabados Tamás	egyetemi docens	Sztochasztika Tanszék
Dr. Vetier András	egyetemi docens	Sztochasztika Tanszék
Dr. Székely Balázs	egyetemi adjunktus	Sztochasztika 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 óra	56
Félévközi készülés órákra	10
Felkészülés zárthelyire	28
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés	26
Összesen	120

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

Név:	Beosztás:	Tanszék, Int.:
Dr. Rónyai Lajos	egyetemi tanár	Algebra Tanszék
Dr. Tóth Bálint	egyetemi tanár	Sztochasztika Tanszék