BME VIK - Felsőbb matematika informatikusoknak

3. A tantárgyfelelős személy és tanszék Tóth Imre,

A tantárgy tanszéki weboldala https://math.bme.hu/~mogy/oktatas.html

4. A tantárgy előadója Tóth Imre

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( "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ó.

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

Valószínűségszámítási alapok ismétlése.

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.
Létezés és véletlen
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.
Néhány nevezetes randomizált algoritmus elemzése
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.
Lovász lokális lemmája

A módszer ismertetése, néhány egyszerű alkalmazása, a módszer algoritmikus változata.

VILLAMOSMÉRNÖKI ÉS INFORMATIKAI KAR AZ MSC KÉPZÉS PROGRAMJA
V 5.0 2023. február 22.
71
Véletlen és bonyolultsági osztályok
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.
Véletlen gráfok
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.
Konvergencia típusok
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.
Generátor- és karakterisztikus függvények. Alkalmazásaik: határeloszlások és nagy eltérések
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.
Sztochasztikus folyamatok elemei: Markov-láncok és Markov-folyamatok
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.
Kitekintés: válogatás a modern valószínűségszámítás problémaköreiből
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,