Komplex rendszerek szimulációs módszerei (ff2n1s04/1)

1. Komplex hálózatok (2017 tavasz)

([1] Chapter 1)

  • Erdős-Rényi gráf generálása, p függvényében fokszám eloszlás, perkolációs küszöb, átmérő mérése és összevetése az analitikus eredményekkel.
  • Az összekötöttségi mátrix spektrumának felvétele, a félkör törvény igazolása numerikusan (pár bonyodalom ami általában nehezítheti a feladatot)
  • Klikk keresés, a Bron-Kerbosch algoritmus implementációja
  • Kis-világ és skálafüggetlen gráfok generálása, azok elemzés az ER gráfokhoz hasonlóan
  • Gráfok robusztusságának vizsgálata élek/csúcsok eltávolításával szemben
  • Hálózatok valódi adatokból (a bátraknak): Agyi hálózatok: OpenConnectome, Filmek: Netflix , Internet: DIMES , Gének: co-expression, GEO DataServer

2. Kaotikus dinamika (2017 tavasz)

([1] Chapter 2)

  • Készítsük el a logisztikus leképezés bifurkációs diagramját!
  • Készítsünk egy interaktív ábrát a logisztikus leképezésről, melyen r értéke szabadon állítható. A kiválasztott r értékhez az ábra gyártsa le az $x_n(n)$ idősort, az $x_{n+1}(x_n)$ 2D Poincaré plotot és az $x_n(n)$ idősor Fourier-transzformáltját. Az interaktív ábra kódja mellékletben szerepeljen, a beadott PDF fájl legfeljebb néhány screenshotot tartalmazzon.
  • Vizsgáljuk meg a logisztikus leképezés Ljapunov-exponensét a stabil fixpontokkal rendelkező és a kaotikus tartományban!
  • Szimuláljuk a Lorenz-modellt és vizsgáljuk a rendszer viselkedését különböző paramétertartományokon. A kaotikus tartományon mérjük le a különös attraktor box-counting dimenzióját és korrelációs dimenzióját! Hasonlítsuk össze a kapott eredményeket, diszkutáljuk az esetleges eltéréseket az irodalmi értéktől.
  • Szorgalmi feladat (a helyes megoldásért +10 pont szerezhető, mely azonban a minimumkövetelménybe nem számít bele): Ábrázoljuk a klasszikus Hénon-leképezés attraktorát. Ábrázoljuk a $D(Q)$ általánosított dimenziót $Q$ függvényében, illetve az $f(\alpha)$ multifraktál spektrumot $\alpha$ függvényében. A megoldásban segít a Wikipedia megfelelő szócikke, illetve egy leírás a multifraktálokról.
  • Szorgalmi feladat (a helyes megoldásért +3 pont szerezhető, mely azonban a minimumkövetelménybe nem számít bele): Határozzuk meg egy természetben előforduló fraktált ábrázoló képen (még jobb, ha saját!) a fraktáldimenziót. (Sok-sok segítség.)

További segédanyagok:

  • A fizika numerikus módszerei I. tantárgy anyaga (Python alapok, interaktív ábrák, jupyter notebook környezet)
  • Diákjegyzet Csordás András Nemlináris dinamika és káosz című kurzusához (Bővebben a dinamikai rendszerekről, fraktálokról, fraktáldimenziókról)

3. Sejtautomaták (2017 tavasz)

([1] Chapter 3)

  • Ismerkedjünk meg a sejtautomaták működésével és statisztikai leírásával:

  • Vizsgáljuk meg, hogy a S. Wolfram által meghatározott négy kategóriába hogyan oszthatóak be az 1 dimenziós kétállapotú elemi sejtautomaták! Hasonlítsuk össze az alábbi módszereket!

    • Tesztelésnek generáljuk le mind a 256 szabályt és vizsgáljuk meg vizuálisan a viselkedést. (A beadott pdf fájlban legfeljebb néhány érdekes ábra szerepeljen!)
    • Számoljuk ki a fraktáldimenziót illetve a térbeli és időbeli entrópiákat!
    • Számoljuk ki a C. Langton által bevezetett lambdát!
    • Minden osztályból néhány kiválasztott szabály néhány cellájának időbeli viselkedésére számoljunk teljesítménysűrűség-spektrumot!
  • Implementáljuk az alábbi egyszerű járványterjedési modellt egy 2D négyzetrácson Moore-szomszédsággal:
    • A cellák lehetséges állapotai:
      • 0 - üres,
      • 1 - egészséges, de fertőzhető,
      • 2 - fertőzőtt,
      • 3 - gyógyult/immunis.
    • A dinamikai szabályok:
      • Egy üres sejt üres marad.
      • Egy egészséges sejt fertőzötté válik, ha 2 vagy több szomszédja fertőzött.
      • Egy fertőzött sejt meggyógyul, ha 4 vagy kevesebb szomszédja fertőzött.
      • Egy gyógyult vagy immunis sejt többé nem fertőződhet meg.
    • Az algoritmus változtatandó paraméterei:
      • A kezdeti $p_0$ valószínűség, hogy egy adott helyen létezik sejt. (Tehát $1-p_0$ valószínűséggel üres egy cella.)
      • A kezdeti $p_i$ valószínűség, hogy egy létező sejt fertőzött.
    • Vizsgáljuk az alábbiakat:
      • Vizsgáljuk a rendszer komplexitását (valamelyik fent definiált mérték szerint) attól függően, hogy milyen kezdeti paramétereket választunk.
      • Vizsgáljuk a rendszer végállapotai közti hasonlóságot. (Például a kölcsönös információtartalom mérésével.)
      • Vizsgáljuk a járvány során megfertőzött sejtek számát, illetve a stacionárius állapot eléréséhez szükséges időt a kezdeti paraméterek függvényében (ábrázoljuk 3D ábrán). Próbáljuk a tapasztalatokat általánosan megfogalmazni a járványterjedéssel kapcsolatban. Térjünk ki a modell előnyeire és gyenge pontjaira. Tegyünk javaslatokat (esetleg kísérletet is) a modell finomítására.

  • Vizsgáljunk egy 2D négyzetrácsot Moore-szomszédsággal.

    • A cellák lehetséges állapotai:
      • 0 - tartózkodó,
      • 1 - együttműködő,
      • 2 - áruló.
    • A cellák minden iteráció során ún. fogolydilemma-játékot játszanak szomszédaikkal külön-külön. Ha mindkét sejt együttműködik, mindkettőjük jutalma 1. Ha mindketten árulók, mindkettőjük "jutalma" 0. Ha az egyikük áruló, másikuk együttműködő, az áruló jutalma $b$ ($2>b>1$), az együttműködő "jutalma" pedig 0. Egy tartózkodó sejt jutalma minden esetben $s$ ($1>s>0$). Egy együttműködő sejt jutalma tartózkodóval találkozva 1, egy áruló jutalma tartózkodóval találkozva 0.
    • A dinamikai szabályok:
      • Minden iteráció során a szomszédokkal játszott fogolydilemma-játékok jutalmai az adott sejtre összeadódnak.
      • Amennyiben a sejt szomszédai közül van, akinek a jutalma nagyobb, mint a sejté, a sejt a következő lépésben átveszi legsikeresebb szomszédja stratégiáját. Ha több különböző stratégia közül kell így választani, véletlenül választ.
      • Ha a sejt a legsikeresebb a szomszédságában, megtartja korábbi stratégiáját.
    • Az algoritmus változtatandó paraméterei:
      • A $b$ paraméter értéke.
      • Az $s$ paraméter értéke.
    • Vizsgáljuk az alábbiakat:
      • Milyen stacionárius állapotai lesznek a rendszernek?
      • A $b$ és $s$ paraméterek változtatása milyen hatással van a különböző stratégiájú sejtek arányára?
      • Látunk-e önszerveződési folyamatokat, igaz-e hogy hasonló a hasonlóval szeret együtt élni? Diszkutáljuk!
      • Mennyiben befolyásolja az eredményeket, ha másféle szomszédságot, esetleg másféle rácsot választunk?

  • Szorgalmi feladat (a helyes megoldásért +2 pont szerezhető, mely azonban a minimumkövetelménybe nem számít bele): Telepítsük a Golly szimulátort, és vizsgáljuk meg a Conway féle "Life" automatát illetve egy másik szabadon választott szabály néhány komplexitás mérték szerint! (Golly script leírás és példák ).

  • Szorgalmi feladat (a helyes megoldásért +4 pont szerezhető, mely azonban a minimumkövetelménybe nem számít bele): Készítsük el a rácsgáz HPP és FHP modelljének szimulációját és szimuláljunk egyszerű áramlási példát (akadály körül, végtelen csőben áramlási profil, stb)! Segítség: Python kód , Matlab kód, Golly: Other-Rules/HPP-demo.rle.
  • Szorgalmi feladat (a helyes megoldásért +5 pont szerezhető, mely azonban a minimumkövetelménybe nem számít bele): A sejtautomaták általánosíthatóak nem csak rácsokra, de tetszőleges reguláris gráfra is (minden csomópontnak ugyanannyi bemenő éle van). Ilyen modellt ír le Stuart Kauffman NK-modellje, melyet a könyv 3. fejezete részletesen tárgyal. Értsük meg a modellt, majd generáljuk az összes N=3, K=1 gráfot az összes lehetséges (fix) szabállyal! Vizsgáljuk meg az állapotteret, számoljuk le a diszjunkt vonzási tartományokat! (hasonlóan mint 86. old. 3.3.b ábra). Vegyük az N=10, K=1 esetet véletlen gráfokkal. Nézzük meg néhány fix véletlen realizáción a tiszta identitás, tiszta negálás, illetve ezek véletlen keverékeként alkotott szabályok esetén a vonzási tartományok terét! (hasonlóan a 98. old. 3.9 ábrához).
  • Szorgalmi feladat (a megoldásért maximálisan +10 pont szerezhető, mely azonban a minimumkövetelménybe nem számít bele): A szomszédsági viszonyok egy lehetséges általánosítása, ha négyzetrács helyett különböző gráfmodelleket alkalmazunk a "sejtek" közötti kapcsolatok leírására. Vizsgáljuk meg a kötelező feladatok között leírt járványmodell viselkedését (stacionárius állapot, fertőzöttek száma, paraméterfüggés) az 1. projekt gráfmodelljeire (pl. ER, BA, WS), esetleg az SNAP oldalról egy valós kapcsolati hálózatra is! Értelmezzük a tapasztalatainkat!

4. Neuronhálózatok (2017 tavasz)

  • Készítsük el a Hopfield-modell implementációját Hopfield eredeti cikke alapján! Igazoljuk kísérletileg a később elméletileg is igazolt kritikus $p=0.14N$ kapacitás értéket (sok véletlen minta, többször megismételve a statisztika javításáért)! Javaslat: legyen $N$ legalább 100, de valószínűleg pár ezres érték is kezelhető. (Hopfield eredeti cikke)
  • Tanítsuk meg a Hopfield-modellt betűk felismerésére! Tanító- és teszthalmazként használhatunk pl. "kézzel írt" karaktereket. (Kiegészítő feladat a TTF vagy egyéb karakterformátum olvasása és "bemeneti vektorrá" alakítása.) Karakterek helyett kereshetünk más tanítóhalmazt a mesterséges intelligencia adatbázisban. Vizsgáljuk meg, hogy ilyen nem véletlen mintákra mekkora a kritikus kapacitás!
  • Implementáljuk a háttéranyagok (coursera, perceptron, perceptron szabály) alapján a perceptron szabályt! Próbáljuk meg az egyes karaktereket (pl. "A" vagy "nem A") a perceptronoknak (karakterenként 1 perceptron) megtanítani. (Hasonlóan mint az alábbi feladatleírásban). A perceptron vagy a Hopfield-modell ad jobb eredményt?
  • Szorgalmi feladat (a megoldásért maximálisan +8 pont szerezhető, mely azonban a minimumkövetelménybe nem számít bele): A 80-as évek végén népszerű neuronhálózatok az azóta megnövekedett tanítóhalmazok és számítógép-kapacitás miatt látványosan újraéledtek és nagy sikereket érnek el (pl. AlphaGo). Legjobban elterjedt módszer a Deep Learning, amely nagyon sok mesterséges neuronból alkotott hálózatot tanít. Könnyen elindítható Python wrapper is rendelkezésre áll, ami a GPU-k párhuzamos kapacitását is kihasználja. Indítsuk el a csomag példáit és módosítsuk úgy, hogy a karakterfelismerési problémát oldja meg!

Szoftverek:

Gráf elemző csomagok

Gráfok síkba ágyazása, ábrázolás

Jegyzőkönyvek beküldése:

  • komplexszim(kukac)gmail.com

Irodalom:

Valid XHTML 1.0 | Copyright © Istvan Csabai 2009-2017