Budapesti Műszaki és Gazdaságtudományi Egyetem
Természettudományi Kar		 Tantárgy Adatlap
Tantárgy kód BMETE95AM39
Tantárgy azonosító adatok
1. A tárgy címe Véletlen diszkrét struktúrák
2. A tárgy angol címe Random Discrete Structures
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 2 + 0 + 0 v Kredit 2
4. Ajánlott/kötelező előtanulmányi rend
vagy Tantárgy kód 1 Rövid cím 1 Tantárgy kód 2 Rövid cím 2 Tantárgy kód 3 Rövid cím 3
4.1 BMETE95AM24 Valszám
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Sztochasztika Tanszék
7. A tantárgy felelős oktatója Dr. Pete Gábor beosztása egyetemi docens
Akkreditációs adatok
8. Akkreditációra benyújtás időpontja 2015.12.08. Akkreditációs bizottság döntési időpontja 2016.01.25
Tematika
9. A tantárgy az alábbi témakörök ismeretére épít
Valószínűségszámítás, kombinatorika, lineáris algebra és funkcionálanalízis alapjai
10. A tantárgy szerepe a képzés céljának megvalósításában (szak, kötelező, kötelezően választható, szabadon választható)
szabadon választható tárgy matematikus BSc, MSc és PhD hallgatók számára
11. A tárgy részletes tematikája
1. A véletlen módszer a kombinatorikában (Ramsey-számok becslései, érdekes tulajdonságú gráfok létezése, stb.). 2. Kombinatorikus számelmélet (Erdős-Kac tétel a prímtényezők véletlenségéről, esetleg később Roth-tétel a 3 hosszú számtani sorozatokról). 3. Erdős-Rényi gráf fázisátmenetei. 4. Perkolációelmélet alapjai. 5. Koncentráció bizonyítások: második momentum módszer, Janson-egyenlőtlenség, Lovász Lokális Lemma, Azuma-Hoeffding martingál- koncentráció, Russo-formula, diszkrét Fourier-analízis alapjai. 6. Barabási-Albert skálafüggetlen gráfok. 7. Gráfokon való bolyongás keverési sebességének becslései: a) csatolásokkal, megállási időkkel, b) spektrális módszerekkel, c) izoperimetrikus tulajdonságokból, a Morris-Peres evolving sets módszer segítségével, d) elektromos hálózatokkal. 8. Propp-Wilson Coupling From The Past mintavételezési módszer. 9. Expanderek, nem-amenabilitás, Banach-Tarski paradoxon.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban		 Két hosszabb feladatsorból választható 4-4 darab HFbeadása, a jegy 50%-a. vizsga-
időszakban		 Tételjegyzék alapján szóbeli vizsga, a jegy 50%-a.
13. Pótlási lehetőségek
Hibás HF-megoldások javíthatóak. Vizsga ismételhető.
14. Konzultációs lehetőségek
Hetenkénti fogadóóra, vizsgaidőszakban is.
15. Jegyzet, tankönyv, felhasználható irodalom
N. Alon, J, Spencer: The probabilistic method, 3rd Edition. Wiley Interscience, 2008.
D. Levin, Y. Peres, E. Wilmer. Markov chains and mixing times. AMS 2008. http://pages.uoregon.edu/dlevin/MARKOV/
G. Grimmett. Probability on graphs. Cambridge University Press, 2010. http://www.statslab.cam.ac.uk/~grg/books/pgs.html
16. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
16.1 Kontakt óra
28
16.2 Félévközi felkészülés órákra
0
16.3 Felkészülés zárthelyire
0
16.4 Zárthelyik megírása
0
16.5 Házi feladat elkészítése
16
16.6 Kijelölt írásos tananyag elsajátítása (beszámoló)
0
16.7 Egyéb elfoglaltság
0
16.8 Vizsgafelkészülés
16
16.9 Összesen
60
17. Ellenőrző adat Kredit * 30
60
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Pete Gábor
egyetemi docens
Sztochasztika Tanszék
A tanszékvezető
19. Neve aláírása
Dr. Sándor Csaba