Generátor náhodných čísiel: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
doplnene citacie, TRNG, PRNG, odkazy, detaily |
d Revízia InternetArchiveBot používateľa 178.40.224.167 (diskusia) bola vrátená Značky: vrátenie SWViewer [1.4] |
||
| (23 medziľahlých úprav od 19 ďalších používateľov nie je zobrazených) | |||
| Riadok 1: | Riadok 1: | ||
'''Generátor náhodných čísel''' je zariadenie alebo procedúra, ktorá generuje čísla ktoré naozaj sú alebo len pripomínajú náhodné čísla. |
'''Generátor náhodných čísel''' je zariadenie alebo procedúra, ktorá generuje čísla ktoré naozaj sú alebo len pripomínajú náhodné čísla. |
||
== Úvod == |
== Úvod == |
||
Jedna z najdôležitejších metodológií k riešeniu problémov v [[Operačný výskum|operačnom výskume]], [[Numerická analýza|numerickej analýze]], rôznych [[počítačová simulácia|simuláciách]], [[Rozhodovanie|rozhodovaní]], [[Počítačová grafika|počítačovej grafike]], [[Kryptológia|kryptológií]], dátovej [[Komunikácia|komunikácií]], internet bankingu a [[Štatistika|štatistike]] je nasadenie [[experiment]]ov, či postupov založených na [[Náhoda|náhode]]. Príkladom z histórie je [[Archimedes zo Syrakúz]], ktorý sa takto pokúšal aproximovať hodnotu [[Ludolfovo číslo|π]]. |
|||
Metóda náhodných experimentov prešla od roku 1940 rýchlym vývojom vpred. Obrovský rozmach [[počítač]]ov a nárast výpočtových kapacít, dovolil generovanie skutočne veľkého množstva vysokých náhodných [[Číslo (matematika)|čísel]]. |
|||
Na začiatku sa nová metóda používala hlavne na riešenie problémov, ktoré boli spojené s [[Jadrová elektráreň|jadrovými elektrárňami]] a vývojom [[Atómová bomba|atómovej bomby]] v [[Projekt Manhattan|projekte Manhattan]]. Čoskoro sa ale zistilo, že tieto metódy sa hodia aj na riešenie veľkého množstva [[Ekonómia|ekonomických]], [[Matematika|matematických]] a [[Fyzika|fyzikálnych]] problémov. |
|||
[[John von Neumann|John Von Neuman]], ktorý sa považuje za otca myšlienky, nazval tieto metódy [[Metóda Monte Carlo|Monte Carlo]].<ref>{{Citácia knihy |
|||
Jedna z najdôležitejších metódologií k riešeniu problémov v [[Operačný_výskum|operačnom výskume]], [[Numerická_analýza|numerickej analýze]], rôznych [[Simulácia|simuláciách]], [[Rozhodovanie|rozhodovaní]], [[Počítačová_grafika|počítačovej grafike]], [[Kryptológia|kryptológií]], dátovej [[Komunikácia|komunikácií]], internet bankingu a [[Štatistika|štatistike]] je nasadenie [[Experiment|experimentov]], či postupov založených na [[Náhoda|náhode]]. Príkladom z histórie je [[Archimedes]], ktorý sa takto pokúšal aproximovať hodnotu [[Ludolfovo_číslo|π]]. |
|||
Metóda náhodných experimentov prešla od roku 1940 rýchlym vývojom vpred. Obrovský rozmach [[Počítač|počítačov]] a nárast výpočtových kapacít, dovolil generovanie skutočne veľkého množstva vysokých náhodných [[Číslo_(matematika)|čísel]]. |
|||
Na začiatku sa nová metóda používala hlavne na riešenie problémov, ktoré boli spojené s [[Jadrová_elektráreň|jadrovými elektrárňami]] a vývojom [[Atómová_bomba|atómovej bomby]] v [[Projekt_Manhattan|projekte Manhattan]]. Čoskoro sa ale zistilo, že tieto metódy sa hodia aj na riešenie veľkého množstva [[Ekonómia|ekonomických]], [[Matematika|matematických]] a [[Fyzika|fyzikálnych]] problémov. |
|||
[[John_von_Neumann|John Von Neuman]], ktorý sa považuje za otca myšlienky, nazval tieto metódy [[Metóda_Monte_Carlo|Monte Carlo]]. <ref> {{Citácia knihy |
|||
| priezvisko = Deák |
| priezvisko = Deák |
||
| meno = Istvan |
| meno = Istvan |
||
| Riadok 22: | Riadok 19: | ||
| strany = 9 |
| strany = 9 |
||
| jazyk = Anglický |
| jazyk = Anglický |
||
}} |
}}</ref> |
||
== Rozdelenie generátorov náhodných čísel == |
== Rozdelenie generátorov náhodných čísel == |
||
Hardwarové generátory založené na snímaní fyzikálneho deja, inak sa označujú ako TRNG (True Random Number Generator) – generátory skutočne náhodných čísel. Z televízie napríklad poznáme zariadenie na žrebovanie čísel športky. |
|||
Generovanie náhodných čísel na základe určitých [[Algoritmus|algoritmov]], inak sa označujú ako PRNG (Pseudo-Random Number Generator) – generátory pseudonáhodných čísel. |
|||
Tabuľky náhodných čísel |
|||
Hardwarové generátory založené na snímaní fyzikálneho deja, inak sa označujú ako TRNG (True Random Number Generator) - generátory skutočne náhodných čísel. Z televízie napríklad poznáme zariadenie na losovanie čísel športky. |
|||
Generovanie náhodných čísel na základe určitých [[Algoritmus|algoritmov]], inak sa označujú ako PRNG (Pseudo-Random Number Generator) - pseudo náhodné generátory. |
|||
Tabuľky náhodných čísel |
|||
''(Pri preklade do slovenčiny vznikajú nepresnosti, preto sa odporúča používať výrazy TRNG a PRNG.)'' |
''(Pri preklade do slovenčiny vznikajú nepresnosti, preto sa odporúča používať výrazy TRNG a PRNG.)'' |
||
== Základné vlastnosti generátorov náhodných čísel == |
== Základné vlastnosti generátorov náhodných čísel == |
||
* dlhá [[perióda]], v ideálnom prípade nekonečne dlhá, v súčasnosti napr. generátor [[Mersenne Twister]] dosahuje periódu 2<sup>19937</sup>-1 |
|||
* rovnomerné a s rastúcou [[Dĺžka|dĺžkou]] [[Sekvencia|sekvencie]] čoraz lepšie zaplnenie [[interval]]u (pokiaľ možno malo by platiť aj pre ľubovoľné subsekvencie) |
|||
* opakovateľnosť,čiže schopnosť opakovane generovať tú istú sekvenciu [[Pseudonáhodné číslo|pseudonáhodných čísel]] pomocou jednoducho špecifikovaných počiatočných podmienok |
|||
* dlhá [[Perióda|perióda]], v ideálnom prípade nekonečne dlhá, v súčasnosti napr. generátor [[Mersenne Twister]] dosahuje periódu 2<sup>19937</sup>-1 |
|||
* rovnomerné a s rastúcou [[Dĺžka|dĺžkou]] [[Sekvencia|sekvencie]] čoraz lepšie zaplnenie [[Interval|intervalu]] (pokiaľ možno malo by platiť aj pre ľubovoľné subsekvencie) |
|||
* opakovatelnosť ,čiže schopnosť opakovane generovať tú istú sekvenciu [[Pseudonáhodné_číslo|pseudonáhodných čísel]] pomocou jednoducho špecifikovaných počiatočných podmienok |
|||
* čas generovania je zanedbateľný oproti času operácií ktoré vytvorenú sekvenciu používajú |
* čas generovania je zanedbateľný oproti času operácií ktoré vytvorenú sekvenciu používajú |
||
* požiadavky na [[ |
* požiadavky na [[Pamäť (počítač)|pamäť]] a portabilita – implementácia nenáročná na pamäť a vo vyššom [[Programovací jazyk|programovacom jazyku]] |
||
* dobré štatistické vlastnosti, čo znamená, že generátor musí úspešne zdolať súbor štatistických testov, teoretických (ak sú k dispozícii) <ref> |
* dobré štatistické vlastnosti, čo znamená, že generátor musí úspešne zdolať súbor štatistických testov, teoretických (ak sú k dispozícii) <ref name=v2005>{{Citácia elektronického dokumentu |
||
| priezvisko = Vargic |
| priezvisko = Vargic |
||
| meno = Radoslav |
| meno = Radoslav |
||
| odkaz na autora = |
| odkaz na autora = |
||
| titul = Ing. |
| titul = Ing., PhD. |
||
| url = http://www.ktl.elf.stuba.sk/~vargic/mas/mas2005/Generovanie%20n%E1hodn%FDch%20%E8%EDse09.pdf |
| url = http://www.ktl.elf.stuba.sk/~vargic/mas/mas2005/Generovanie%20n%E1hodn%FDch%20%E8%EDse09.pdf |
||
| dátum vydania = 2005 |
| dátum vydania = 2005 |
||
| Riadok 55: | Riadok 46: | ||
| miesto = Bratislava |
| miesto = Bratislava |
||
| jazyk = SK |
| jazyk = SK |
||
}} |
}}</ref> |
||
== Výhody a nevýhody TRNG a PRNG generátorov == |
== Výhody a nevýhody TRNG a PRNG generátorov == |
||
=== TRNG (True Random Number Generator) === |
|||
Hlavná výhoda TRNG je nemožnosť predpovedať, alebo [[odhad]]núť generovanú postupnosť. Generátor je neperiodický a vyznačuje sa zložitejšou štruktúrou. Pri získavaní náhodných čísel musíme počítať s hardwarovým zdržaním. |
|||
=== TRNG (True Random Number Generator) === |
|||
Hlavná výhoda TRNG je nemožnosť predpovedať, alebo odhadnúť generovanú postupnosť. Generátor je neperiodický a vyznačuje sa zložitejšou štruktúrou. Pri získavaní náhodných čísel musíme počítať s hardwarovým zdržaním. |
|||
=== PRNG (Pseudo-Random Number Generator) === |
=== PRNG (Pseudo-Random Number Generator) === |
||
Medzi hlavné výhody PRNG patrí jednoduchosť a rýchlosť. Nevýhodou je, že po určitom čase bude generátor poskytovať rovnaké výstupy. Preto pri jeho konštrukcii prevláda snaha o čo najväčšie predĺženie tejto periódy, ideálne na [[Nekonečno|nekonečne dlho]]. |
|||
Neutrálnou vlastnosťou je schopnosť generátora poskytovať rovnaké výstupy z rovnakého počiatočného vstupu. (tzv.[[seed]]). Táto jeho schopnosť sa napríklad využíva, ak chceme meniť [[Parameter|parametre]] [[Počítačová simulácia|simulácie]], v ktorej požadujeme rovnaké vstupné dáta.<ref>{{Citácia elektronického dokumentu |
|||
Medzi hlavné výhody PRNG patrí jednoduchosť a rýchlosť. Nevýhodou je, že po určitom čase bude generátor poskytovať rovnaké výstupy. Preto pri jeho konštrukcii prevláda snaha o čo najväčšie predĺženie tejto peródy, ideálne na nekonečne dlho. |
|||
Neutrálnou vlastnosťou je schopnosť generátora poskytovať rovnaké výstupy z rovnakého počiatočného vstupu. (tzv.seed). Táto jeho schopnosť sa napríklad využíva, ak chceme meniť parametre simulácie, v ktorej požadujeme rovnaké vstupné data. <ref>{{Citácia elektronického dokumentu |
|||
| priezvisko = ZOUHAR |
| priezvisko = ZOUHAR |
||
| meno = Petr |
| meno = Petr |
||
| Riadok 83: | Riadok 66: | ||
| miesto = Brno |
| miesto = Brno |
||
| jazyk = Český |
| jazyk = Český |
||
}} |
}}</ref> |
||
== Generátory TRNG (prirodzene náhodných čísel) == |
== Generátory TRNG (prirodzene náhodných čísel) == |
||
môžeme získať priradením číselnej hodnoty [[Fyzikálny jav|fyzikálnemu javu]], alebo stavu [[Fyzikálna sústava|fyzikálneho systému]], či [[Fyzikálna veličina|fyzikálnej veličiny]] v danom [[okamih]]u nám môže poskytnúť vhodný [[zdroj]] [[Náhodné číslo|náhodných čísel]]. Je potrebné vybrať taký [[fyzikálny jav]], u ktorého sa predpokladá [[Náhoda|náhodné správanie]]. |
|||
môžeme získať priradením číselnej hodnoty [[Fyzikálny_jav|fyzikálnemu javu]], alebo stavu [[Fyzikálna_sústava|fyzikálneho systému]], či [[Fyzikálna_veličina|fyzikálnej veličiny]] v danom [[Okamih|okamihu]] nám môže poskytnúť vhodný [[Zdroj|zdroj]] [[Náhodné_číslo|náhodných čísel]]. Je potrebné vybrať taký [[Fyzikálny_jav|fyzikálny jav]], u ktorého sa predpokladá [[Náhoda|náhodné správanie]]. |
|||
Napríklad |
Napríklad |
||
* [[ |
* [[Rádiový šum|radiový šum]], |
||
rôzne druhy [[Radiácia|radiácie]] : |
rôzne druhy [[Radiácia|radiácie]] : |
||
* [[ |
* [[Ionizujúce žiarenie]], |
||
* [[ |
* [[Žiarenie gama]], |
||
* [[ |
* [[Röntgenové žiarenie]], |
||
* [[ |
* [[Rádiové žiarenie]] |
||
* [[ |
* [[Kozmické žiarenie]]. |
||
Za vhodný zdroj náhodných [[Dáta|dát]] môžeme považovať aj [[Hmota_(fyzika)#Pohyb|pohyb atómov]], prúdenie [[Voda|vody]], premenlivú [[Teplota|teplotu]] [[Prostredie|prostredia]] atď. Pri [[Získavanie|získavaní]] prirodzených [[Náhodné_číslo|náhodných čísel]] používame rôzne na to uspôsobené [[Merací_prístroj|meradla]] a iné [[Mechanika_(rozlišovacia_stránka)|mechanické]] [[Prostriedok_(pomôcka)|prostriedky]]. Nevýhodou tohto prístupu môže byť [[Porucha|porucha]] [[Prístroj|prístroja]], ktorú môžeme odhaliť až po dlhom [[Čas_(fyzika)|čase]]. Obzvlášť nepríjemné je, ak táto [[Chyba|chyba]] spôsobí nejaké vážne nedostatky vo výpočtoch. |
|||
Za vhodný zdroj náhodných [[Dáta|dát]] môžeme považovať aj [[Hmota (fyzika)#Pohyb|pohyb atómov]], prúdenie [[Voda|vody]], premenlivú [[Teplota|teplotu]] [[Prostredie|prostredia]] atď. Pri [[Získavanie|získavaní]] prirodzených [[Náhodné číslo|náhodných čísel]] používame rôzne na to uspôsobené [[Merací prístroj|meradla]] a iné [[Mechanika (rozlišovacia stránka)|mechanické]] [[Prostriedok (pomôcka)|prostriedky]]. Nevýhodou tohto prístupu môže byť [[porucha]] [[prístroj]]a, ktorú môžeme odhaliť až po dlhom [[Čas (fyzika)|čase]]. Obzvlášť nepríjemné je, ak táto [[chyba]] spôsobí nejaké vážne nedostatky vo výpočtoch. |
|||
=== Získavanie prirodzene náhodných čísel === |
=== Získavanie prirodzene náhodných čísel === |
||
==== Generátor založený na využití šumu ==== |
|||
Za [[zdroj]] náhodných dát možno považovať sústavu, ktorá sa skladá z [[Telefónna linka|telefónnej linky]] alebo [[tranzistor]]u, na ktorých vzniká [[rádiový šum]] a určitého [[signál]]neho [[Prístroj|zariadenia]]. Toto zariadenie je schopné registrovať [[Udalosť|udalosti]], kedy šum prekročí predom stanovenú kritickú [[Hranica|hranicu]] ''c''. Po [[Doba|dobu]] na [[Začiatok|začiatku]] presne stanoveného času ''Δt''. Pri prekročení kritickej hranice šumu zapíšeme 1, v opačnom prípade 0. Týchto zariadení môžeme mať niekoľko v paralelnom zapojení. Pri správnom výbere času ''t'' a hranice ''c'', môžeme získať náhodné číslo o veľkosti ''k'' [[bit]]ov v [[Rovnomerné rozdelenie pravdepodobnosti|rovnomernom rozložení]] {0,1}.<ref>{{Citácia knihy |
|||
==== Generátor založený na využití šumu ==== |
|||
[[Súbor:Sum 01.jpg|thumb|Sum 01]] |
|||
Za [[Zdroj|zdroj]] náhodných dát možeme považovať sústavu, ktorá sa skladá z [[Telefónna_linka|telefónnej linky]] alebo [[Tranzistor|tranzistoru]], na ktorých vzniká [[Rádiový_šum|rádiový šum]] a určitého [[Signál|signálneho]] [[Prístroj|zariadenia]]. Toto zariadenie je schopné registrovať [[Udalosť|udalosti]], kedy šum prekročí predom stanovenú kritickú [[Hranica|hranicu]] ''c''. Po [[Doba|dobu]] na [[Začiatok|začiatku]] presne stanoveného času ''Δt''. Pri prekročení kritickej hranice šumu zapíšeme 1, v opačnom prípade 0. Týchto zariadení môžeme mať niekoľko v paralelnom zapojení. Pri správnom výbere času ''t'' a hranice ''c'', môžeme získať náhodné číslo o veľkosti ''k'' [[Bit|bitov]] v [[Rovnomerné_rozdelenie_pravdepodobnosti|rovnomernom rozložení]] {0,1}. <ref>{{Citácia knihy |
|||
| priezvisko = Deák |
| priezvisko = Deák |
||
| meno = Istvan |
| meno = Istvan |
||
| Riadok 121: | Riadok 98: | ||
| jazyk = Anglický |
| jazyk = Anglický |
||
}}</ref> |
}}</ref> |
||
==== Generátor založený na využití gama žiarenia ==== |
==== Generátor založený na využití gama žiarenia ==== |
||
Iným zdrojom prirodzene náhodných čísel je prístroj, ktorý je založený na náhodnom emitovaní [[Gama žiarenie|gama častíc]]. |
|||
Iným zdrojom prirodzene náhodných čísel je prístroj, ktorý je založený na náhodnom emitovaní [[Gama_žiarenie|gama častíc]]. |
|||
Skladá sa z : |
Skladá sa z : |
||
* [[ |
* [[Generátor častíc|generátor]] [[Žiarenie gama|gama]] [[Elementárna častica|častíc]] |
||
* ''X'' [[ |
* ''X'' [[Časticový detektor|detektorov gama častíc]] |
||
* časový [[ |
* časový [[spínač]] |
||
Určitá časť emitovaných gama častíc od prvého signálu časového [[ |
Určitá časť emitovaných gama častíc od prvého signálu časového [[spínač]]a až po druhý signál je registrovaná prým [[Časticový detektor|detektorom]] [[Žiarenie gama|gama]] častíc. |
||
Od druhého k tretiemu časovému signálu sú emitované častice zachytené druhým detektorom. |
Od druhého k tretiemu časovému signálu sú emitované častice zachytené druhým detektorom. |
||
Od tretieho signálu k štvrtému sú častice |
Od tretieho signálu k štvrtému sú častice zachytené na treťom detektore atď. až po ''X''. |
||
[[ |
[[Signál]] registrovaný ''i''-tym detektorom označím ''S<sub>i</sub>'', za určitý časový okamih ''Δt''. Celá [[procedúra]] je trikrát zopakovaná a je vygenerované číslo ''S<sub>ii</sub>'' a ''S<sub>iii</sub>''. |
||
Posledný (najmenej signifikantný) bit získaný z [[ |
Posledný (najmenej signifikantný) bit získaný z [[Binárna operácia|binárneho]] zápisu [[Súčet|súčtu]] ''S<sub>i</sub>''+''S<sub>ii</sub>''+''S<sub>iii</sub>'' je v tomto prípade považovaný za náhodný bit. Potom tento spôsob ponúka ''X'' náhodných bitov v jednom kroku v čase 3Δt.<ref>{{Citácia knihy |
||
| priezvisko = Deák |
| priezvisko = Deák |
||
| meno = Istvan |
| meno = Istvan |
||
| Riadok 153: | Riadok 127: | ||
| jazyk = Anglický |
| jazyk = Anglický |
||
}}</ref> |
}}</ref> |
||
==== Využitie náhodných udalostí vo vesmíre ==== |
==== Využitie náhodných udalostí vo vesmíre ==== |
||
Z pohľadu generovania náhodných čísel je zaujímavý [[projekt]] spoločnosti Yuzoz. Tá sa v [[Minulosť|minulosti]] pripravovala na spustenie [[Služba|služby]] generovania náhodných čísel s využitím náhodných úkazov vo [[vesmír]]e. Podľa slov zakladateľa Jeff Manbera, za zdroj dát by mali slúžiť údaje o [[Slnečná aktivita|solárnej aktivite]], [[Kozmické žiarenie|kozmickom prúdení]]. Projekt počítal s [[Komercia|komerčným využitím]]. V [[Súčasnosť|súčasnosti]] je projekt už zastavený.<ref>{{Citácia elektronického dokumentu |
|||
Z pohľadu generovania náhodných čísel je zaujimavý [[Projekt|projekt]] spoločnosti Yuzoz. Tá sa v [[Minulosť|minulosti]] pripravovala na spustenie [[Služba|služby]] generovania náhodných čísel s využitím náhodných úkazov vo [[Vesmír|vesmíre]]. Podľa slov zakladateľa Jeff Manbera, za zdroj dát by mali slúžiť údaje o [[Slnečná_aktivita|solárnej aktivite]], [[Kozmické_žiarenie|kozmickom prúdení]]. Projek počítal s [[Komercia|komerčným využitím]]. V [[Súčasnosť|súčasnosti]] je projekt už zastavený. <ref>{{Citácia elektronického dokumentu |
|||
| priezvisko = Boyle |
| priezvisko = Boyle |
||
| meno = Alan |
| meno = Alan |
||
| Riadok 170: | Riadok 141: | ||
| miesto = |
| miesto = |
||
| jazyk = Anglický |
| jazyk = Anglický |
||
| url archívu = https://web.archive.org/web/20110107214706/http://cosmiclog.msnbc.msn.com/_news/2006/11/09/4351132-letting-the-stars-decide |
|||
}} </ref> |
|||
| dátum archivácie = 2011-01-07 |
|||
}}</ref> |
|||
== Generátory PRNG (pseudo náhodných čísel) == |
== Generátory PRNG (pseudo náhodných čísel) == |
||
=== Kongruenčný generátor === |
|||
[[Pseudonáhodné číslo|pseudonáhodné čísla]] sú generované [[Algoritmus|algoritmom]] v digitálnych [[počítač]]och. Získané čísla sú kompletne deterministické, pretože sú generované na základe algoritmu a hodnoty nejakého [[Parameter|parametru]], s možnosťou výberu počiatočnej hodnoty, ktorá determinuje celú sekvenciu. V praxi nás uspokojí skutočnosť, že tieto čísla vyzerajú ako by boli z náhodného zdroja. |
|||
=== Kongruenčný generátor === |
|||
[[Pseudonáhodné_číslo|pseudonáhodné čísla]] sú generovaná [[Algoritmus|algoritmom]] v digitálnych [[Počítač|počítačoch]]. Získané čísla sú kompletne deterministické, pretože sú generované na základe algoritmu a hodnoty nejakého [[Parameter|parametru]], s možnosťou výberu počiatočnej hodnoty, ktorá determinuje celú sekvenciu. V praxi nás uspokojí skutočnosť, že tieto čísla vyzerajú ako by boli z náhodného zdroja. |
|||
==== Lineárny kongruenčný generátor ==== |
==== Lineárny kongruenčný generátor ==== |
||
hodnoty sú generované pomocou vzťahu |
hodnoty sú generované pomocou vzťahu |
||
x<sub>''n''</sub> = (ax<sub>''n''-1</sub>+c) mod ''m'' |
x<sub>''n''</sub> = (ax<sub>''n''-1</sub>+c) mod ''m'' |
||
kde operácia mod je |
kde operácia mod je zvyšok po celočíselnom delení, a, c, m sú konštanty. Počiatočná hodnota x<sub>0</sub> sa nazýva seed (semienko - násada do generátora). |
||
==== Inverzný kongruenčný generátor ==== |
==== Inverzný kongruenčný generátor ==== |
||
* Maximálne dosiahnuteľná perióda je m |
|||
* [[Inverzný prvok]] sa počíta inverzným [[Euklidov algoritmus|Euklidovým algoritmom]] na nájdenie celočíselných [[Riešenie rovnice|riešení rovnice]] 1=⋅+⋅mkxx |
|||
* Sú vhodné na použitie pre [[Algoritmus|paralelné algoritmy]].<ref name=v2005 /> |
|||
=== Metódy zlepšenia vlastností PRNG === |
|||
==== Skladaním aritmetických výstupov z niekoľkých generátorov ==== |
|||
z<sub>n</sub> = (x<sub>n</sub> + y<sub>n</sub>) mod ''m'' |
|||
kde x<sub>n</sub> resp. y<sub>n</sub> sú výstupy z pôvodných generátorov. Vhodné je voliť nesúdeliteľné veľkosti periód jednotlivých generátorov. |
|||
==== Premiešavanie (shuffling) ==== |
|||
* Maximálne dosiahnuteľná perióda je m |
|||
Metóda na dodatočné zlepšenie vlastnosti generátora [[Pseudonáhodné číslo|pseudonáhodných čísel]]. Je založená na využití existujúceho generátora, ktorý pre premiešavací algoritmus generuje semienka ([[seeds]]) a mení tak poradie vstupných hodnôt. Existuje niekoľko modifikácií tejto metódy. |
|||
* Inverzný prvok sa počíta inverzným Euklidovým algoritmom na nájdenie celočíselných riešení rovnice 1=⋅+⋅mkxx |
|||
Prvých k hodnôt uložíme do poľa a (k+1)-tu hodnotu do pomocnej premennej idx. Výstupné hodnoty potom generujeme v dvoch krokoch nasledovne: |
|||
* ICG, EICG majú podstatne lepšie autokorelačné vlastnosti ako LCG |
|||
* pomocou premennej idx vyberieme hodnotu z poľa ktorá bude našim výstupom a na uvoľnené miesto vložíme novú vstupnú hodnotu |
|||
* Sú vhodné na použitie pre paralelné algoritmy. <ref> {{Citácia elektronického dokumentu |
|||
* výstupnú hodnotu okopírujeme do premennej idx.<ref>{{Citácia elektronického dokumentu |
|||
| priezvisko = Vargic |
| priezvisko = Vargic |
||
| meno = Radoslav |
| meno = Radoslav |
||
| odkaz na autora = |
| odkaz na autora = |
||
| titul = Ing. |
| titul = Ing., PhD. |
||
| url = http://www.ktl.elf.stuba.sk/~vargic/mas/ |
| url = http://www.ktl.elf.stuba.sk/~vargic/mas/mas2002/cviko1/cvika_g1a.doc |
||
| dátum vydania = |
| dátum vydania = 2002 |
||
| vydavateľ = Slovenská technická univerzita, |
| vydavateľ = Slovenská technická univerzita, |
||
| miesto = Bratislava |
| miesto = Bratislava |
||
| jazyk = SK |
| jazyk = SK |
||
}} |
}}</ref> |
||
== Pozri aj == |
== Pozri aj == |
||
* [[náhoda]] |
* [[náhoda]] |
||
| Riadok 213: | Riadok 187: | ||
* [[pseudonáhodné číslo]] |
* [[pseudonáhodné číslo]] |
||
== Zdroje a referencie == |
|||
* {{Citácia knihy |
|||
==Externé odkazy== |
|||
| priezvisko = Deák |
|||
* [http://excelnavod.sweb.cz/randbetween-nahodne-cislo.html| Náhodné čisla v MS Excel] |
|||
| meno = István |
|||
* [http://php.vrana.cz/nahodna-cisla.php| pHp generátor náhodných čísel] |
|||
| odkaz na autora = |
|||
* [http://random.mat.sbg.ac.at/links/rando.html| Random number generator - The pLab project {{eng icon}}] |
|||
| titul = Random number generators and simulation |
|||
| vydavateľ = |
|||
| miesto = |
|||
== Zdroje == |
|||
| rok = 1990 |
|||
| isbn = 963-05-5316-3 |
|||
| kapitola = |
|||
{{cite book |
|||
| strany = |
|||
| title = Random number generators and simulation |
|||
| jazyk = |
|||
| author = Deák I. |
|||
| year = 1990 |
|||
| ISBN = 963 05 5316 3 |
|||
}} |
}} |
||
<references/> |
|||
== Externé odkazy == |
|||
<references/> |
|||
* [http://excelnavod.sweb.cz/randbetween-nahodne-cislo.html Náhodné čísla v MS Excel] {{Webarchive|url=https://web.archive.org/web/20110122104257/http://excelnavod.sweb.cz/randbetween-nahodne-cislo.html |date=2011-01-22 }} |
|||
* [http://php.vrana.cz/nahodna-cisla.php pHp generátor náhodných čísel] |
|||
* [http://random.mat.sbg.ac.at/links/rando.html Random number generator – The pLab project {{eng icon}}] {{Webarchive|url=https://web.archive.org/web/20110414153615/http://random.mat.sbg.ac.at/links/rando.html |date=2011-04-14 }} |
|||
[[Kategória:Algoritmy]] |
|||
[[bg:Генератор на случайни числа]] |
|||
[[cs:Generátor náhodných čísel]] |
|||
[[da:Slumptalsgenerator]] |
|||
[[de:Zufallszahlengenerator]] |
|||
[[en:Random number generation]] |
|||
[[es:Generador de números aleatorios]] |
|||
[[fa:تولید اعداد تصادفی]] |
|||
[[fr:Générateur de nombres aléatoires]] |
|||
[[nl:Toevalsgenerator]] |
|||
[[pl:Generator liczb losowych]] |
|||
[[sv:Slumptalsgenerator]] |
|||
[[tr:Rastgele sayı üretimi]] |
|||
[[uk:Генерація випадкових чисел]] |
|||
[[ur:تصادفی عدد مولّد]] |
|||
[[zh:随机数发生器]] |
|||
Aktuálna revízia z 18:12, 7. november 2023
Generátor náhodných čísel je zariadenie alebo procedúra, ktorá generuje čísla ktoré naozaj sú alebo len pripomínajú náhodné čísla.
Úvod
[upraviť | upraviť zdroj]Jedna z najdôležitejších metodológií k riešeniu problémov v operačnom výskume, numerickej analýze, rôznych simuláciách, rozhodovaní, počítačovej grafike, kryptológií, dátovej komunikácií, internet bankingu a štatistike je nasadenie experimentov, či postupov založených na náhode. Príkladom z histórie je Archimedes zo Syrakúz, ktorý sa takto pokúšal aproximovať hodnotu π.
Metóda náhodných experimentov prešla od roku 1940 rýchlym vývojom vpred. Obrovský rozmach počítačov a nárast výpočtových kapacít, dovolil generovanie skutočne veľkého množstva vysokých náhodných čísel. Na začiatku sa nová metóda používala hlavne na riešenie problémov, ktoré boli spojené s jadrovými elektrárňami a vývojom atómovej bomby v projekte Manhattan. Čoskoro sa ale zistilo, že tieto metódy sa hodia aj na riešenie veľkého množstva ekonomických, matematických a fyzikálnych problémov.
John Von Neuman, ktorý sa považuje za otca myšlienky, nazval tieto metódy Monte Carlo.[1]
Rozdelenie generátorov náhodných čísel
[upraviť | upraviť zdroj]Hardwarové generátory založené na snímaní fyzikálneho deja, inak sa označujú ako TRNG (True Random Number Generator) – generátory skutočne náhodných čísel. Z televízie napríklad poznáme zariadenie na žrebovanie čísel športky.
Generovanie náhodných čísel na základe určitých algoritmov, inak sa označujú ako PRNG (Pseudo-Random Number Generator) – generátory pseudonáhodných čísel.
Tabuľky náhodných čísel
(Pri preklade do slovenčiny vznikajú nepresnosti, preto sa odporúča používať výrazy TRNG a PRNG.)
Základné vlastnosti generátorov náhodných čísel
[upraviť | upraviť zdroj]- dlhá perióda, v ideálnom prípade nekonečne dlhá, v súčasnosti napr. generátor Mersenne Twister dosahuje periódu 219937-1
- rovnomerné a s rastúcou dĺžkou sekvencie čoraz lepšie zaplnenie intervalu (pokiaľ možno malo by platiť aj pre ľubovoľné subsekvencie)
- opakovateľnosť,čiže schopnosť opakovane generovať tú istú sekvenciu pseudonáhodných čísel pomocou jednoducho špecifikovaných počiatočných podmienok
- čas generovania je zanedbateľný oproti času operácií ktoré vytvorenú sekvenciu používajú
- požiadavky na pamäť a portabilita – implementácia nenáročná na pamäť a vo vyššom programovacom jazyku
- dobré štatistické vlastnosti, čo znamená, že generátor musí úspešne zdolať súbor štatistických testov, teoretických (ak sú k dispozícii) [2]
Výhody a nevýhody TRNG a PRNG generátorov
[upraviť | upraviť zdroj]TRNG (True Random Number Generator)
[upraviť | upraviť zdroj]Hlavná výhoda TRNG je nemožnosť predpovedať, alebo odhadnúť generovanú postupnosť. Generátor je neperiodický a vyznačuje sa zložitejšou štruktúrou. Pri získavaní náhodných čísel musíme počítať s hardwarovým zdržaním.
PRNG (Pseudo-Random Number Generator)
[upraviť | upraviť zdroj]Medzi hlavné výhody PRNG patrí jednoduchosť a rýchlosť. Nevýhodou je, že po určitom čase bude generátor poskytovať rovnaké výstupy. Preto pri jeho konštrukcii prevláda snaha o čo najväčšie predĺženie tejto periódy, ideálne na nekonečne dlho. Neutrálnou vlastnosťou je schopnosť generátora poskytovať rovnaké výstupy z rovnakého počiatočného vstupu. (tzv.seed). Táto jeho schopnosť sa napríklad využíva, ak chceme meniť parametre simulácie, v ktorej požadujeme rovnaké vstupné dáta.[3]
Generátory TRNG (prirodzene náhodných čísel)
[upraviť | upraviť zdroj]môžeme získať priradením číselnej hodnoty fyzikálnemu javu, alebo stavu fyzikálneho systému, či fyzikálnej veličiny v danom okamihu nám môže poskytnúť vhodný zdroj náhodných čísel. Je potrebné vybrať taký fyzikálny jav, u ktorého sa predpokladá náhodné správanie.
Napríklad
rôzne druhy radiácie :
Za vhodný zdroj náhodných dát môžeme považovať aj pohyb atómov, prúdenie vody, premenlivú teplotu prostredia atď. Pri získavaní prirodzených náhodných čísel používame rôzne na to uspôsobené meradla a iné mechanické prostriedky. Nevýhodou tohto prístupu môže byť porucha prístroja, ktorú môžeme odhaliť až po dlhom čase. Obzvlášť nepríjemné je, ak táto chyba spôsobí nejaké vážne nedostatky vo výpočtoch.
Získavanie prirodzene náhodných čísel
[upraviť | upraviť zdroj]Generátor založený na využití šumu
[upraviť | upraviť zdroj]Za zdroj náhodných dát možno považovať sústavu, ktorá sa skladá z telefónnej linky alebo tranzistoru, na ktorých vzniká rádiový šum a určitého signálneho zariadenia. Toto zariadenie je schopné registrovať udalosti, kedy šum prekročí predom stanovenú kritickú hranicu c. Po dobu na začiatku presne stanoveného času Δt. Pri prekročení kritickej hranice šumu zapíšeme 1, v opačnom prípade 0. Týchto zariadení môžeme mať niekoľko v paralelnom zapojení. Pri správnom výbere času t a hranice c, môžeme získať náhodné číslo o veľkosti k bitov v rovnomernom rozložení {0,1}.[4]
Generátor založený na využití gama žiarenia
[upraviť | upraviť zdroj]Iným zdrojom prirodzene náhodných čísel je prístroj, ktorý je založený na náhodnom emitovaní gama častíc.
Skladá sa z :
- generátor gama častíc
- X detektorov gama častíc
- časový spínač
Určitá časť emitovaných gama častíc od prvého signálu časového spínača až po druhý signál je registrovaná prým detektorom gama častíc.
Od druhého k tretiemu časovému signálu sú emitované častice zachytené druhým detektorom.
Od tretieho signálu k štvrtému sú častice zachytené na treťom detektore atď. až po X.
Signál registrovaný i-tym detektorom označím Si, za určitý časový okamih Δt. Celá procedúra je trikrát zopakovaná a je vygenerované číslo Sii a Siii. Posledný (najmenej signifikantný) bit získaný z binárneho zápisu súčtu Si+Sii+Siii je v tomto prípade považovaný za náhodný bit. Potom tento spôsob ponúka X náhodných bitov v jednom kroku v čase 3Δt.[5]
Využitie náhodných udalostí vo vesmíre
[upraviť | upraviť zdroj]Z pohľadu generovania náhodných čísel je zaujímavý projekt spoločnosti Yuzoz. Tá sa v minulosti pripravovala na spustenie služby generovania náhodných čísel s využitím náhodných úkazov vo vesmíre. Podľa slov zakladateľa Jeff Manbera, za zdroj dát by mali slúžiť údaje o solárnej aktivite, kozmickom prúdení. Projekt počítal s komerčným využitím. V súčasnosti je projekt už zastavený.[6]
Generátory PRNG (pseudo náhodných čísel)
[upraviť | upraviť zdroj]Kongruenčný generátor
[upraviť | upraviť zdroj]pseudonáhodné čísla sú generované algoritmom v digitálnych počítačoch. Získané čísla sú kompletne deterministické, pretože sú generované na základe algoritmu a hodnoty nejakého parametru, s možnosťou výberu počiatočnej hodnoty, ktorá determinuje celú sekvenciu. V praxi nás uspokojí skutočnosť, že tieto čísla vyzerajú ako by boli z náhodného zdroja.
Lineárny kongruenčný generátor
[upraviť | upraviť zdroj]hodnoty sú generované pomocou vzťahu
xn = (axn-1+c) mod m kde operácia mod je zvyšok po celočíselnom delení, a, c, m sú konštanty. Počiatočná hodnota x0 sa nazýva seed (semienko - násada do generátora).
Inverzný kongruenčný generátor
[upraviť | upraviť zdroj]- Maximálne dosiahnuteľná perióda je m
- Inverzný prvok sa počíta inverzným Euklidovým algoritmom na nájdenie celočíselných riešení rovnice 1=⋅+⋅mkxx
- Sú vhodné na použitie pre paralelné algoritmy.[2]
Metódy zlepšenia vlastností PRNG
[upraviť | upraviť zdroj]Skladaním aritmetických výstupov z niekoľkých generátorov
[upraviť | upraviť zdroj]zn = (xn + yn) mod m
kde xn resp. yn sú výstupy z pôvodných generátorov. Vhodné je voliť nesúdeliteľné veľkosti periód jednotlivých generátorov.
Premiešavanie (shuffling)
[upraviť | upraviť zdroj]Metóda na dodatočné zlepšenie vlastnosti generátora pseudonáhodných čísel. Je založená na využití existujúceho generátora, ktorý pre premiešavací algoritmus generuje semienka (seeds) a mení tak poradie vstupných hodnôt. Existuje niekoľko modifikácií tejto metódy. Prvých k hodnôt uložíme do poľa a (k+1)-tu hodnotu do pomocnej premennej idx. Výstupné hodnoty potom generujeme v dvoch krokoch nasledovne:
- pomocou premennej idx vyberieme hodnotu z poľa ktorá bude našim výstupom a na uvoľnené miesto vložíme novú vstupnú hodnotu
- výstupnú hodnotu okopírujeme do premennej idx.[7]
Pozri aj
[upraviť | upraviť zdroj]Zdroje a referencie
[upraviť | upraviť zdroj]- DEÁK, István. Random number generators and simulation. [s.l.] : [s.n.], 1990. ISBN 963-05-5316-3.
- ↑ DEÁK, Istvan. Random numbers generators and simulation. Budapest : Akademiai Kiado, 1990. ISBN 963 05 5316 3. Kapitola Introduction, s. 9. (Anglický)
- ↑ a b VARGIC, Radoslav. Ing., PhD. [online]. Bratislava: Slovenská technická univerzita,, 2005. Dostupné online.
- ↑ ZOUHAR, Petr. Ing. [online]. Brno: Vysoké učení technické v Brně, FEAKT, 2009/2010. Dostupné online. (Český)
- ↑ DEÁK, Istvan. Random numbers generators and simulation. Budapest : Akademiai Kiado, 1990. ISBN 963 05 5316 3. Kapitola Natural random numbers, s. 33. (Anglický)
- ↑ DEÁK, Istvan. Random numbers generators and simulation. Budapest : Akademiai Kiado, 1990. ISBN 963 05 5316 3. Kapitola Natural random numbers, s. 34. (Anglický)
- ↑ BOYLE, Alan. Cosmic Log [online]. 9.nov 2006. Dostupné online. Archivované 2011-01-07 z originálu. (Anglický)
- ↑ VARGIC, Radoslav. Ing., PhD. [online]. Bratislava: Slovenská technická univerzita,, 2002. Dostupné online.