Vizsgakérdések kidolgozása

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Algoritmusok álvéletlen számok előállítasára.

• Neumann-féle hatványközép
  • [math]u_0 := k \text{ jegy\H{u} bin\'{a}ris sz\'{a}m}[/math]
  • [math]u_n := u_{n-1}^2 \text{ k\"{o}z\'{e}ps\H{o} k db jegye}[/math]
  • Gyenge minőségű, mert
    • a ciklus hossza függ [math]u_0[/math]-tól, gyakran túl rövid.
    • nem egyenletes, a kisebb számok előállításának valószínűsége nagyobb.
• Neumann-féle szorzatközép
  • [math]u_n := u_{n-1} \cdot u_{n-2} \text{ k\"{o}z\'{e}ps\H{o} k db jegye}[/math]
  • A hatványközép módszer javítása.
• Hatványmaradék algoritmusok
  • Lehmer-féle algoritmus
    • [math]u_n := x^n \pmod{m}[/math], avagy [math]u_n := u_{n-1} \cdot x \pmod{m}[/math]. Tehát a sorozat [math]x[/math] egymás utáni hatványainak maradéka modulo [math]m[/math] lesz.
    • A ciklushossz az a legkisebb [math]q \geq 1[/math] kitevő lesz, amelyre [math]x^q \equiv 1 \pmod{m}[/math].
    • A leghosszabb ciklust akkor kapjuk adott [math]m[/math] esetén, ha [math]x[/math] primitív gyöke annak, azaz, ha [math]q = \varphi(m)[/math], ahol [math]\varphi(m)[/math] az [math]m[/math]-nél kisebb, [math]m[/math]-hez relatív prímek száma (ez az Euler-Fermat tételből következik).
    • [math]m[/math]-t érdemes prímnek választani, mert ekkor [math]\varphi(m) = m-1[/math] maximális lesz.
    • Ez a módszer ma is használatos, Lehmer vezette be 1949-ben, ő a következő paramétereket használta:
      • [math]x = 23[/math]
      • [math]m = 10^8 + 1[/math]
      • [math](u_0 = 47594118)[/math]
  • Javítás
    • Eltérő kezdetű sorozatok
      • [math]u_n := u_{n-1} \cdot x + c \pmod{m}[/math]
    • Több múltbéli érték felhasználása a következő elem generálásához
      • [math]u_n := \sum_{k=1}^K{u_{n-k} \cdot x_k}[/math]
• Fibonacci generátor algoritmus
  • A Fibonacci-sorozat maradékaival is jó minőségű, álvéletlen sorozat állítható elő.
    • [math]u_n := u_{n-1} + u_{n-2} \pmod{m}[/math], ahol [math]m = 2^k[/math].
      • Hibája, hogy az egymás után generált számok nem függetlenek.
    • [math]u_n := u_{n-5} + u_{n-17} \pmod{m}[/math], ahol [math]m = 2^k[/math].
      • Ez a javítás már megfelelő, független sorozatot generál.

Adatszerkezetek az események kezeléséhez diszkrét idejű szimulátorokban.

Az események kezelésével kapcsolatban két alapművelet van, amelyek nagyon gyorsan elvégezhetők kell legyenek:

• a, A következő elem keresése
• b, Új elem beszúrása

Az eseményeket tárolhatjuk:

• Láncolt listában
  • A keresés gyors, a beszúrás viszont lassú.
• Kupacban vagy más speciális adatszerkezetben
• Időleképzéssel (időkerékben)
  • Ez tulajdonképpen láncolt listák egy tömbje. Az időt felosztjuk [math]\Delta[/math] hosszú intervallumokra, egy tömbelem pedig egy intervallum eseményeit tartalmazza láncolt lista formában. (Pl. az [math]i.[/math] tömbelem az [math]((i-1) \cdot \Delta, \ i \cdot \Delta)[/math] időintervallum eseményeit tartalmazza.)
  • Az adatszerkezet hatékonysága [math]\Delta[/math] megválasztásán múlik. Ugyanis, ha
    • [math]\Delta[/math] túl nagy, gyakorlatilag egy láncolt listánk lesz. Így pedig nem nyerünk semmit a sima láncolt listás megvalósításhoz képest.
    • [math]\Delta[/math] túl kicsi, sok üres és egy elemet tartalmazó lista lesz. Ekkor pedig a következő elem keresése fog lelassulni.
  • Megoldás: adaptivitás.

Az időkerék implementációja:

• Felveszünk egy megfelelő méretű tömböt. A túlidőzített események (amelyek a tömb kapacitása miatt nem lennének tárolhatók), az utolsó cellába kerülnek. Az aktuális időpontot tömbindex formájában nyilvántartjuk.
• Ha végeztünk az adott cella eseményeinek feldolgozásával, akkor azokra már nincs szükség, a túlidőzített események átkerülnek ide.
• Átlépünk a következő cellára, azaz növeljük az indexet. Ha túlindexelnénk a tömböt, akkor az indexet nyilván újra az első elemre kell állítanunk.
• Megvalósíthatunk továbbá hierarchikus, több szintű időkereket is. Ekkor az időkerék tömbjének egy-egy eleme újabb időkereket tartalmaz, aminek tömbelemei újabbat, és így tovább.

A memóriamentes tulajdonság de�finíciója. Az exponenciális eloszlás memóriamentességének bizonyítása.

Definíció:

• Egy eloszlás akkor memóriamentes, ha egy esemény bekövetkezésének valószínűsége nem függ attól, hogy az előző bekövetkezés óta mennyi idő telt el.
• [math]P(X \lt t+n | X \gt n) = P(X \lt t), \text{ ahol } t, n \gt 0[/math]

Bizonyítás:

• [math]P(X \lt t+n | X \gt n) = 1 - P(X \gt t+n | X \gt n) = 1 - \frac{P(X \gt t+n, X \gt n)}{P(X \gt n)} = 1 - \frac{P(X \gt t+n)}{P(X \gt n)} = 1 - \frac{1 - P(X \lt t+n, X \gt n)}{1 - P(X \lt n)} = 1 - \frac{1 - (1 - e^{-\lambda (t+n)})}{1 - (1 - e^{-\lambda n})} = 1 - \frac{e^{-\lambda t}e^{-\lambda n}}{e^{-\lambda n}} = 1 - e^{-\lambda t} = P(X \lt t)[/math]

Diszkrét idejű Markov láncok irreducibilitása, aperiodicitása és visszatérősége.

• Az X diszkrét idejű Markov-láncot irreducibilisnek nevezzük, ha minden állapota minden állapotából elérhető, azaz minden [math]i,j \in S[/math]-re létezik [math]n_{ij}[/math] úgy, hogy [math]p_{ij}^{(n_{ij})} \gt 0[/math].
• Az X diszkrét idejű Markov-lánc egy [math]i \in S[/math] állapotát aperiodikus állapotnak nevezzük, ha létezik [math]n_i[/math], hogy minden [math]n \geq n_i[/math]-re [math]p_{ii}^{(n)} \gt 0[/math].
• Az X diszkrét Markov-lánc aperiodikus, ha minden állapota az.
• Legyen [math]f_{ij}^{(n)}[/math] annak a valószínűsége, hogy az i állapotból indítva a folyamat az n. lépésben jut a j állapotba először, és legyen [math]f_{ij}^{(0)} = 0[/math]. Az X diszkrét idejű Markov-lánc egy [math]i \in S[/math] állapotát visszatérő állapotnak nevezzük, ha [math]\sum_{n=1}^\infty{f_{ii}^{(n)} = 1}[/math], és nem visszatérő állapotnak, ha [math]\sum_{n=1}^\infty{f_{ii}^{(n)} \lt 1}[/math].
• Az X diszkrét Markov-lánc visszatérő, ha minden állapota visszatérő, és nem visszatérő, ha minden állapota nem visszatérő.
• Ha egy véges állapotú Markov-lánc irreducibilis, akkor van legalább egy visszatérő állapota, így az összes az, így a lánc is visszatérő.

Diszkrét idejű Markov láncok tranziens és egyensúlyi eloszlása, a stabilitás feltételei.

Jelölések:

• [math]p_i^{(n)} = P(X_n = i)[/math] - annak a valószínűsége, hogy a Markov-lánc az i. állapotban van n lépés után.
• [math]P^{(n)} = \begin{bmatrix} p_1^{(n)} & p_2^{(n)} & \ldots \end{bmatrix}[/math] - eloszlás n lépés után.
• [math]\Pi = \begin{bmatrix} p_{ij}^{(1)} \end{bmatrix}[/math] - az egylépéses valószínűségekből képzett ún. sztochasztikus mátrix.

Tranziens eloszlás

• [math]P^{(n)} = P^{(n-1)} \cdot \Pi = P^{(0)} \cdot \Pi^n[/math]

Egyensúlyi eloszlás

• [math]P = \lim_{n \to \infty} P^{(n)}[/math]
• A Markov-lánc stabil, ha a határérték létezik, az egy eloszlás és független a kezdeti [math]P^{(0)}[/math] eloszlástól.

A Poisson folyamat de�finí��ci�ója, tulajdons�ágai.

sokfelh.pdf 40-41.oldal jól leírja

Little formula felí��r�ása, bizony�í�t�ása.

sokfelh.pdf 9.oldal