Véletlen bolyongás gráfokon, gráfok spektruma, izoperimetrikus egyenlőtlenségek

A tantárgy angol neve: Random Roaming on Graphs, the Spectra of Graphs, Isoperimetric Inequalities

Adatlap utolsó módosítása: 2006. július 1.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Informatikai tudományok

doktori iskola

Választható tárgy
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VIMAD101   4/0/0/v 5 1/1
3. A tantárgyfelelős személy és tanszék Dr. Telcs András,
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr Telcs András

Egy. doc.

SZIT
5. A tantárgy az alábbi témakörök ismeretére épít

Valószínúségszámítás

6. Előtanulmányi rend
Ajánlott:

Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat:

Neptun-kód Cím

7. A tantárgy célkitűzése

A véletlen bolyongások egyszerűségüknél fogva rengeteg tudományágban használatosak. A fizikában a diffúziót modellezhetjük vele homogén, inhomogén és porózus közegben illetve fraktálokon. A biológiában a fehérék csavarodását a gének fejlődését írhatjuk le véletlen bolyongással. Az informatikus számára a mobil felhasználó mozgását írja le véletlen bolyongás, de az IP csomagok továbbításának egyik modellje is bolyongás. A tárgy szépségét az úja és újra felbukkanó fizikai interpretáció, szemléletes kép adja, elsajátítása nem igényel nagy matematikai apparátust. A félév során megismerkedünk az egyszerű rácson folyó bolyongás tulajdonságain kezdve a fraktálokon folyó bolyongás rejtelmeiig bezárólag sok jelenséggel. Használunk sok valószínűségszámítást, pici fizikát, például az Ohm törvényt.

8. A tantárgy részletes tematikája

Bevezetés, valószínűségi változók, bolyongás rácson és gráfon

Markov láncok alapjai, visszatérőség

tükrözési elv, tönkremenés valószínűség

Generátor fv

első elérés, visszatérés, Pólya tétele I

reverzibilis Markov láncok,

Sajátérték, sajátvektor

Dirichlet feladat, ujra elérési valószínűségek

Polya tétel II

maximum elv, Dirichlet elv, Thomson elv

Martingálok, harmonikus függvények és mértékek

ellenállás és menekülési valószínűség

az ingázási idő

Wald azonosság I,II.

Bolyongás véletlen közegben, Sinaj bolyongás

Ray-Knight elmélet

bolyongás fraktális gráfokon

Green függvény

kilépési idő, Einstein reláció

izoperimetrikus és egyéb egyenlőtlenségek

stabilitás, konvergencia

átmenet valószínűségek becslése I

átmenet valószínűségek becslése II
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

(előadás, gyakorlat, laboratórium):

előadás

10. Követelmények

a. A szorgalmi időszakban: házifeladatok beadása

b. A vizsgaidőszakban: vizsga

  1. Elővizsga:
11. Pótlási lehetőségek

nincs

12. Konzultációs lehetőségek

heti egy meghatározott időpontban

13. Jegyzet, tankönyv, felhasználható irodalom

Peter G. Doyle, Snell. J. Laurie, Random Walks and Electrical Networks (Carus Mathematical Monographs, No 22)

Random Walks on Infinite Graphs and Groups (Cambridge Tracts in Mathematics)

Saját jegyzet

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

(a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

Kontakt óra

60

Félévközi készülés órákra

30

Felkészülés zárthelyire

Házi feladat elkészítése

Kijelölt írásos tananyag elsajátítása

30

..

Vizsgafelkészülés

30

Összesen

150
15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Telcs András

Egy. doc.

SZIT