Vizsgakérdések kidolgozása

Ez az oldal a korábbi SCH wikiről lett áthozva.

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
  • Értelmezés sikertelen (formai hiba): {\displaystyle u_0 := k \text{ jegy\H{u} bin\'{a}ris sz\'{a}m}}
  • Értelmezés sikertelen (formai hiba): {\displaystyle u_n := u_{n-1}^2 \text{ k\"{o}z\'{e}ps\H{o} k db jegye}}
  • Gyenge minőségű, mert
    • a ciklus hossza függ $u_{0}$-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
  • Értelmezés sikertelen (formai hiba): {\displaystyle u_n := u_{n-1} \cdot u_{n-2} \text{ k\"{o}z\'{e}ps\H{o} k db jegye}}
  • A hatványközép módszer javítása.
• Hatványmaradék algoritmusok
  • Lehmer-féle algoritmus
    • $u_{n}:=x^{n}{\pmod {m}}$, avagy $u_{n}:=u_{n-1}\cdot x{\pmod {m}}$. Tehát a sorozat Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x} egymás utáni hatványainak maradéka modulo Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m} lesz.
    • A ciklushossz az a legkisebb Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle q \geq 1} kitevő lesz, amelyre Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x^q \equiv 1 \pmod{m}} .
    • A leghosszabb ciklust akkor kapjuk adott Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m} esetén, ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x} primitív gyöke annak, azaz, ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle q = \varphi(m)} , ahol Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \varphi(m)} az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m} -nél kisebb, Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m} -hez relatív prímek száma (ez az Euler-Fermat tételből következik).
    • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m} -t érdemes prímnek választani, mert ekkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \varphi(m) = m-1} maximális lesz.
    • Ez a módszer ma is használatos, Lehmer vezette be 1949-ben, ő a következő paramétereket használta:
      • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x = 23}
      • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m = 10^8 + 1}
      • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (u_0 = 47594118)}
  • Javítás
    • Eltérő kezdetű sorozatok
      • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u_n := u_{n-1} \cdot x + c \pmod{m}}
    • Több múltbéli érték felhasználása a következő elem generálásához
      • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u_n := \sum_{k=1}^K{u_{n-k} \cdot x_k}}
• Fibonacci generátor algoritmus
  • A Fibonacci-sorozat maradékaival is jó minőségű, álvéletlen sorozat állítható elő.
    • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u_n := u_{n-1} + u_{n-2} \pmod{m}} , ahol Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m = 2^k} .
      • Hibája, hogy az egymás után generált számok nem függetlenek.
    • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u_n := u_{n-5} + u_{n-17} \pmod{m}} , ahol Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m = 2^k} .
      • 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \Delta} hosszú intervallumokra, egy tömbelem pedig egy intervallum eseményeit tartalmazza láncolt lista formában. (Pl. az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} tömbelem az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle ((i-1) \cdot \Delta, \ i \cdot \Delta)} időintervallum eseményeit tartalmazza.)
  • Az adatszerkezet hatékonysága Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \Delta} megválasztásán múlik. Ugyanis, ha
    • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \Delta} 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.
    • Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \Delta} 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.
• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P(X < t+n | X > n) = P(X < t), \text{ ahol } t, n > 0}

Bizonyítás:

• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P(X < t+n | X > n) = 1 - P(X > t+n | X > n) = 1 - \frac{P(X > t+n, X > n)}{P(X > n)} = 1 - \frac{P(X > t+n)}{P(X > n)} = 1 - \frac{1 - P(X < t+n, X > n)}{1 - P(X < 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 < t)}

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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i,j \in S} -re létezik Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n_{ij}} úgy, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p_{ij}^{(n_{ij})} > 0} .
• Az X diszkrét idejű Markov-lánc egy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i \in S} állapotát aperiodikus állapotnak nevezzük, ha létezik Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n_i} , hogy minden Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n \geq n_i} -re Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p_{ii}^{(n)} > 0} .
• Az X diszkrét Markov-lánc aperiodikus, ha minden állapota az.
• Legyen Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f_{ij}^{(n)}} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f_{ij}^{(0)} = 0} . Az X diszkrét idejű Markov-lánc egy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i \in S} állapotát visszatérő állapotnak nevezzük, ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \sum_{n=1}^\infty{f_{ii}^{(n)} = 1}} , és nem visszatérő állapotnak, ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \sum_{n=1}^\infty{f_{ii}^{(n)} < 1}} .
• 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:

• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p_i^{(n)} = P(X_n = i)} - annak a valószínűsége, hogy a Markov-lánc az i. állapotban van n lépés után.
• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P^{(n)} = \begin{bmatrix} p_1^{(n)} & p_2^{(n)} & \ldots \end{bmatrix}} - eloszlás n lépés után.
• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \Pi = \begin{bmatrix} p_{ij}^{(1)} \end{bmatrix}} - az egylépéses valószínűségekből képzett ún. sztochasztikus mátrix.

Tranziens eloszlás

• $P^{(n)}=P^{(n-1)}\cdot \Pi =P^{(0)}\cdot \Pi ^{n}$

Egyensúlyi eloszlás

• $P=\lim _{n\to \infty }P^{(n)}$
• A Markov-lánc stabil, ha a határérték létezik, az egy eloszlás és független a kezdeti $P^{(0)}$ 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