BMETE95AM39

Nyomtatóbarát változatNyomtatóbarát változat
Tantárgy azonosító adatok
A tárgy címe: 
Véletlen diszkrét struktúrák
A tárgy angol címe: 
Random Discrete Structures
2
0
0
v
Kredit: 
2
Ajánlott/Kötelező előtanulmányi rend
1.Követelménytárgy kódja: 
BMETE95AM24
1.Követelménytárgy (rövidített) címe: 
Valszám
A tantárgy felelős tanszéke: 
Sztochasztika Tanszék
A tantárgy felelős oktatója: 
Dr. Pete Gábor
A tantárgy felelős oktatójának beosztása: 
egyetemi docens
Akkreditációs adatok
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
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
A tantárgy szerepe a képzés céljának megvalósításában: 
szabadon választható tárgy matematikus BSc, MSc és PhD hallgatók számára
A tantárgy részletes tematikája magyarul és angolul: 

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.

Követelmények szorgalmi időszakban: 
Két hosszabb feladatsorból választható 4-4 darab HFbeadása, a jegy 50%-a.
Követelmények vizsgaidőszakban: 
Tételjegyzék alapján szóbeli vizsga, a jegy 50%-a.
Pótlási lehetőségek: 
Hibás HF-megoldások javíthatóak. Vizsga ismételhető.
Konzultációs lehetőségek: 
Hetenkénti fogadóóra, vizsgaidőszakban is.
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
A tárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
Kontakt óra: 
28
Félévközi felkészülés órákra: 
0
Felkészülés zárthelyire: 
0
Zárthelyik megírása: 
0
Házi feladat elkészítése: 
16
Kijelölt írásos tananyag elsajátítása (beszámoló): 
0
Egyéb elfoglaltság: 
0
Vizsgafelkészülés: 
16
Összesen: 
60
Ellenőrző adat: 
60
A tárgy tematikáját kidolgozta
Név: 
Dr. Pete Gábor
Beosztás: 
egyetemi docens
Munkahely (tanszék, kutatóintézet, stb.): 
Sztochasztika Tanszék
A tanszékvezető neve: 
Dr. Sándor Csaba
A tantárgy adatlapja PDF-ben: