ADŠ prednáška 24: Generovanie náhodných čísel, náhodné preusporiadanie poľa.

Zhrnutie prednášky

Prednáška uvádza tému náhody v algoritmoch a upozorňuje, že ľudská intuícia o pravdepodobnosti je slabá, a preto na drobných implementačných detailoch náhodných programov záleží. Rozoberá filozofickú a fyzikálnu otázku, či náhoda existuje; podľa dnešných poznatkov kvantovej fyziky sa zdá, že skutočná náhoda v prírode existuje. Počítače využívajú dva typy náhody: hardvérovú, založenú na šume v senzoroch (napríklad najnižší bit teploty procesora), ktorá je kvalitná, ale pomalá, a softvérovú, teda pseudonáhodné generátory, ktoré sú deterministické a určené vnútorným stavom. Ich kvalitu možno posudzovať štatistickými testami, ktoré náhodnosť nikdy nedokážu, len vyvrátiť. Ako príklad slúži rozlíšenie skutočne náhodných postupností od ručne vymyslených podľa dĺžky behov rovnakých bitov, ktoré ľudia podhodnocujú.

• - Ľudská intuícia v pravdepodobnosti a štatistike zlyháva, preto sú dôležité technické detaily náhodných algoritmov.
• - Existencia skutočnej náhody je skôr fyzikálna a filozofická otázka; kvantová mechanika naznačuje, že náhoda v prírode existuje.
• - Hardvérové zdroje náhody (šum senzorov, napríklad najnižší bit teploty procesora) sú kvalitné, ale majú obmedzený tok bitov a po sebe idúce merania môžu byť korelované.
• - Pseudonáhodné generátory sú deterministické, majú vnútorný stav a z pohľadu pozorovateľa pôsobia chaoticky.
• - Štatistické testy môžu náhodnosť postupnosti len vyvrátiť, nie dokázať.
• - Ľudia podceňujú pravdepodobnosť dlhých behov rovnakých výsledkov, čo odhalí ručne vymyslené postupnosti od skutočne náhodných.
• - Pravdepodobnosť šiestich núl za sebou je 1/64, siedmich 1/128 a ôsmich 1/256.

Zhrnutie pripravené s pomocou AI z prepisu videa.