BME VIK - Felsőbb matematika informatikusoknak

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 Lajos	egyetemi tanár	TTK Algebra Tanszék
Dr. Bálint Péter	egyetemi docens	TTK Sztochasztika Tanszék
Dr. Pete Gábor	egyetemi docens	TTK Sztochasztika Tanszék
Dr. Tóth Imre Péter	egyetemi docens	TTK 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

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