Vizsgakérdések kidolgozása - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|TeljesitmenyElemzesVizsgakerdesKidolgozas}} ==Algoritmusok álvéletlen számok előállítasára.== * Neumann-féle hatványközép **
2012-10-22T09:48:24Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|TeljesitmenyElemzesVizsgakerdesKidolgozas}} ==Algoritmusok álvéletlen számok előállítasára.== * Neumann-féle hatványközép <mat…”

Új lap**
{{GlobalTemplate|Infoszak|TeljesitmenyElemzesVizsgakerdesKidolgozas}}

==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 < t+n | X > n) = P(X < t), \text{ ahol } t, n > 0</math>

Bizonyítás:
* <math>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)</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})} > 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)} > 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)} < 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.

==Diszkr�ét idejű bolyong�ások ismertet�ése, egyens�úlyi eloszl�ás levezet�ése.==

==Folytonos idejű Markov l�ancok irreducibilit�asa �es visszat�erős�ege.==

==Folytonos idejű Markov l�ancok tranziens �es egyens�ulyi eloszl�asa, a stabilit�as felt�etelei.==

==Folytonos idejű sz�let�és-hal�áloz�ási folyamatok ismertet�ése, egyens�úlyi eloszl�ás levezet�ése.==

==A Poisson folyamat de�finí��ci�ója, tulajdons�ágai.==
sokfelh.pdf 40-41.oldal jól leírja

==A sorban�áll�ási rendszerek Kendall-f�éle jel�l�ésrendszer�ének ismertet�ése.==

==Little formula felí��r�ása, bizony�í�t�ása.==
sokfelh.pdf 9.oldal

==Az M/M/1 sor egyens�úlyi eloszl�ása.==

==Átlagos ig�énysz�ám �és rendszeridő az M/M/1 sorban.==

==Az M/M/m sor egyens�úlyi eloszl�ása.==

==Az M/M/m/m sor egyens�úlyi eloszl�ása.==

==Átlagos ig�énysz�ám �és rendszeridő az M/M/m/m sorban.==

==Az Erlang-B �es Erlang-C formula jelent�ése, sz�ármaztat�ása.==

==Az Erlang-B formula levezet�ése, rekurzí��v sz�ám��ít�ása.==

==Az M/M/1//N sor egyens�úlyi eloszl�ása.==

==Átlagos ig�énysz�ám �és rendszeridő az M/M/1//N sorban.==

==Csoportos illetve t�bbl�épcsős �érkez�és �és kiszolg�al�ás modellez�ése.==

==Az Erlang �es a Hiperexponenci�ális eloszl�ások de�finí��ci�ója, tulajdons�ágai.==

==F�ázis t�í�pus�ú eloszl�ások definí��ci�ója, �értelmez�ése, alkalmaz�ási lehetős�égei.==

==A Pollaczek-Hichin v�árhat�oóért�ék-formula levezet�ése.==

==Az M/G/1 sor egyens�úlyi eloszl�ása, v�ázlatosan (evol�úci�ós egyenlet, �állapot�átmenetm�átrix alakja).==

==Sorban�áll�ási h�ál�ózatok oszt�ályoz�ása, Jackson tí��pus�ú h�ál�ózatok egyens�úlyi vizsg�álata.==

==Egyszerűs��ített modell a r�éselt ALOHA protokollra, maxim�ális �átvitel �és �átlagos k�ésleltet�és.==

[[Category:Infoszak]]