PseudonáhodnostPseudonáhodná je taková posloupnost čísel, která se zdá být statisticky náhodná, ale je vytvořena plně deterministickým a opakovatelným procesem.[1] Při programování se často používají generátory pseudonáhodných čísel, protože tradiční zdroje náhodnosti dostupné lidem (jako je např. házení kostkou) vyžadují fyzické procesy, které v počítačových programech nejsou dostupné, i když vývoj v technologii hardwarových generátorů náhodných čísel to zpochybnil. PozadíGeneracování náhodných čísel má mnoho použití, např. pro náhodné vzorkování, metody Monte Carlo, pro deskové nebo hazardní hry. Počítače jsou však deterministické stroje, což znamená, že vždy produkují stejný výsledek ze stejného výchozího bodu. Totéž platí i o mnoha fyzikálních procesech; k významným výjimkám petří radioaktivní rozpad a kvantová měření, které jsou považovány za skutečně náhodné procesy. Protože tyto procesy nepředstavují praktický zdroj náhodných čísel, používají se pseudonáhodná čísla, která v ideálním případě jsou stejně nepředvídatelné jako skutečně náhodné posloupnosti, přestože jsou generované deterministicky.[2] V mnoha aplikacích je deterministickým procesem počítačový algoritmus nazývaný generátor pseudonáhodných čísel, kterému musí být na začátku poskytnut vstupní parametr hnízdo náhodných čísel. Protože stejné hnízdo bude pokaždé generovat stejnou posloupnost, je důležité, aby bylo hnízdo dobře zvoleno a uchováno v tajnosti, zejména v bezpečnostních aplikacích, kde nepředvídatelnost klíče má kritický význam.[3] V některých případech, kdy je důležité, aby posloupnost byla prokazatelně nepředpověditelná, se používají fyzikální zdroje náhodných čísel, jako je radioaktivní rozpad, atmosférický elektromagnetický šum zachycený přijímačem rádiových vln naladěným mezi stanice nebo prodlevy mezi stisky kláves.[1][4] Časová investice nutná pro získání těchto čísla vede ke kompromisu: použití některých těchto fyzikálních jevů pouze jako hnízda pro generátor pseudonáhodných čísel. HistorieVědci, kteří potřebovali náhodná čísla, je před příchodem moderních počítačů museli generovat různými prostředky (vrhem kostkou, taháním karet, pomocí rulety,[5] atd.) nebo používat existující tabulky náhodných čísel. První pokus poskytnout vědcům hotový zdroj náhodných čísel se uskutečnil v roce 1927, kdy vydavatelství Cambridge University Press publikovalo tabulku 41600 čísel vyvinutou L.H.C. Tippettem. V roce 1947 společnost RAND Corporation generovala čísla elektronickou simulací rulety;[5] výsledky byly nakonec publikovány v roce 1955 jako A Million Random Digits with 100,000 Normal Deviates. Ve výpočetní složitostiV teoretické informatice je rozdělení pravděpodobnosti pseudonáhodné vůči třídě protivníků, pokud ji žádný protivník z této třídy nedokáže rozlišit od rovnoměrného rozdělení.[6] Tento pojem pseudonáhodnosti je studován v teorii výpočetní složitosti a má aplikace v kryptografii. Formálně: nechť S a T jsou konečné množiny a nechť F = {f: S → T} je třída funkcí. Rozdělení pravděpodobnosti D nad S je ε-pseudonáhodné vůči F, pokud pro každé f v F je statistická vzdálenost mezi rozděleními a , kde je vzorkováno z D a je vzorkováno z rovnoměrného rozdělení na S, nejvýše ε. V typických aplikacích popisuje třída F výpočetní model s omezenými zdroji a zajímáme se o návrh rozdělení D s určitými vlastnostmi, které jsou pseudonáhodné vůči F. Rozdělení D je často specifikovánoi jako výstup generátoru pseudonáhodných čísel.[7] OdkazyReferenceV tomto článku byl použit překlad textu z článku Pseudorandomness na anglické Wikipedii.
Literatura
Související článkyExterní odkazy
|
