Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    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