A tantárgy szerepe a képzés céljának megvalósításában:
VIK Mérnökinformatikus MSc képzés kötelezően választható tárgya
A tantárgy részletes tematikája magyarul és angolul:
1. Valószínűségszámítási alapok ismétlés.
2. Létezés és véletlen.
3. Néhány nevezetes randomizált algoritmus elemzése.
4. Lovász lokális lemmája.
5. Véletlen és bonyolultsági osztályok.
6. Véletlen gráfok.
7. Konvergencia típusok.
8. Generátor- és karakterisztikus függvények. Alkalmazásaik: határeloszlások és nagy eltérések.
9. Sztochasztikus folyamatok elemei: Markov-láncok és Markov-folyamatok.
10. Kitekintés: válogatás a modern valószínűségszámítás problémaköreiből.
Követelmények szorgalmi időszakban:
2 zárthelyi dolgozat teljesítése. Az aláírás megszerzésének feltétele a zárthelyi dolgozatok teljesítése egyenként legalább 40%-ra.
Követelmények vizsgaidőszakban:
A vizsgán a tárgy mindkét feléből el kell érni az elégséges szintet. A vizsgajegy megállapítása 50-50%-ban a zárthelyik eredménye és a vizsga alapján történik.
Konzultációs lehetőségek:
Szükség esetén a számonkérések előtt a hallgatókkal egyeztetve.
Jegyzet, tankönyv, felhasználható irodalom:
Bollobás: Random Graphs, Cambridge University Press, 2001., Rényi: Valószínűségszámítás. Tankönyvkiadó, 1972.
Rónyai, Ivanyos, Szabó: Algoritmusok. Typotex, 2000., Mitzenmacher, Upfal: Probability and Computing. Cambridge University Press, 2005.
Papadimitriou: Számítási bonyolultság. Novadat, 1999., Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
Nyomtatóbarát változat
