If you're seeing this message, it means we're having trouble loading external resources on our website.

Pokud používáš webový filtr, ujisti se, že domény: *.kastatic.org and *.kasandbox.org jsou vyloučeny z filtrování.

Hlavní obsah

Generátory pseudonáhodných čísel

Náhodná čísla vs. generátory pseudonáhodných čísel Tvůrce: Brit Cruise.

Chceš se zapojit do diskuze?

Zatím žádné příspěvky.
Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.

Transkript

Při pozorování okolního světa se velmi často setkáme s náhodnými kolísáními. Skutečně náhodná čísla můžeme získat měřením tohoto kolísání, kterému se říká šum. Měřením šumu, přesněji řečeno jeho vzorkováním, můžeme získat čísla. Například měřením elektrického proudu televizního šumu v průběhu času získáme posloupnost skutečně náhodných čísel. Tuto posloupnost můžeme zobrazit jako cestu, která mění směr podle každého čísla. Tomu se říká 'random walk' (náhodná procházka). Všimněte si, že v žádném měřítku neexistuje vzorec pohybu. V žádném bodě se nedá další pohyb předpovědět. Říká se, že náhodné procesy jsou nedeterministické, protože se nedají determinovat (předpovědět) dopředu. Stroje jsou naopak deterministické. Jejich fungování je předvídatelné a opakovatelné. V roce 1946 pracoval John von Neumann na výpočtech pro armádu. Přesněji řečeno byl cílem návrh vodíkové bomby. S použitím počítače ENIAC chtěl opakovaně vypočítat, jaké procesy probíhají při jaderné fúzi. K tomu ale byl potřeba rychlý přístup ke zdroji náhodných čísel, který by se dal využívat opakovaně. ENIAC však měl malou vnitřní paměť a nemohl tak ukládat dlouhé náhodné posloupnosti. Proto vytvořil Neumann algoritmus, aby mechanicky simuloval náhodnost. Nejdříve vybral skutečně náhodné číslo, zvané 'seed' (semínko). Toto číslo můžeme získat například měřením šumu nebo aktuálního času v milisekundách. Potom se stane semínko vstupem jednoduchého výpočtu. Semínko se umocní a výstupem bude prostřední část výsledku. Tento výstup se použije jako nové semínko, a to se opakuje kolikrát je potřeba. Toto je známé jako 'Middle-square method'. A je to jeden z mnohých generátorů pseudonáhodných čísel. Náhodnost sekvence závisí jen na náhodnosti počátečního semínka. Stejné semínko, stejná sekvence. Jaký je tedy rozdíl mezi náhodně a pseudonáhodně vytvořenými sekvencemi? Ukažme si každou sekvenci jako 'random walk' (náhodnou procházku). Vypadají podobně, dokud nezrychlíme. Pseudonáhodná sekvence se po čase začne opakovat. Toto se stává, když algoritmus použije semínko, který už použil, a proto se bude cyklus opakovat. Délka, po které se posloupnost bude opakovat, se nazývá perioda. Perioda závisí na délce počátečního semínka. Když použijeme dvojciferné semínko, může algoritmus vytvořit nejvíce 100 čísel před novým použitím semínka a opakováním cyklu. Při trojciferném semínku se cyklus může opakovat až po 1000 číslech. A u čtyřciferného semínka to může být až 10 000 čísel bez opakování. Kdybychom tedy použili dost velké semínko, posloupnost může mít biliony a biliony čísel bez opakování. Ale je tu jeden významný rozdíl. Když tvoříte čísla pseudonáhodně, tak se mnoho posloupností nebude moci objevit. Například když Alice generuje skutečně náhodnou posloupnost 20 posunů, je to jakby vybrala jednu z hromady všech možných posloupností posunů. Tato hromada obsahuje 26 na dvacátou stran, což je nepředstavitelně velké číslo. Kdybychom stáli dole a zasvítili nahoru, osoba na vrchu by to světlo uviděla až za 200 miliónů let. Porovnejme si to s pseudonáhodnou posloupností vytvořenou pomocí čtyřciferného semínka. To je jako výběr jednoho z 10 000 možných počátečních semínek. Alice tedy může vytvořit jen 10 000 různých posloupností, což je jen zanedbatelný zlomek všech možných posloupností. Když použijeme pseudonáhodná čísla místo náhodných, zmenšíme prostor klíčů na o mnoho menší prostor semínek. Takže aby byla pseudonáhodná posloupnost nerozlišitelná od náhodné posloupnosti, tak musí být pro počítač nepraktické vyzkoušet všechna semínka a najít shodu. To vede k tomu, že informatika rozlišuje mezi možnými věcmi a věcmi možnými v rozumném čase. Stejnou logiku používáme při zamykání kola. Víme, že každý může jednoduše vyzkoušet všechny možnosti, než najde tu správnou a zámek se otevře. Ale udělat to by trvalo spoustu dní. Takže na 8 hodin je zámek bezpečný. U pseudonáhodných generátorů se bezpečnost zvyšuje s větší délkou semínka. Kdyby i nejvýkonnějšímu počítači trvalo stovky let, než projde všechna semínka, můžeme říci, že je to prakticky bezpečné, i když ne dokonale bezpečné. Tím, že se počítače zrychlují, se musí zvyšovat i velikost semínka. Pseudonáhodnost osvobozuje Alici a Boba od povinnosti sdílet své posloupnosti posunů předem. Stačí jim sdělit celkem malé náhodné semínko, které rozšíří na náhodně vypadající posloupnost, když to potřebují. Ale co když se nikdy nesetkají a nebudou si moci semínko předat?