Úvod do pravěpodobnostních algoritmů

Mám novinku. NASA oznámila, že na roveru, na který máme přístup, bude hardwarový generátor náhodných čísel. Pak ještě dodali, že potřebují, aby náš algoritmus fungoval v praxi. V reálných situacích se může stát, že někdy dojde k chybě, ale pravděpodobnost této chyby musí být tak malá, že ji můžeme v praxi ignorovat. Pokud vám to příjde divné, uvědomte si, že v reálném světě není nikdy nic jisté. Vždy může dojít k chybě. Například obaly čipů obsahují malá množství radioaktivních látek. Ty se můžou rozpadnout, uvolnit alfa částici, která potom přehodí bit v paměti a třeba tím nečekaně změní číslo. Kromě toho, kosmické záření může taky způsobovat chyby. Nikdy nemůžeme úplně odstranit možnost chyby. Tak jsem se v NASA zeptal, jaká pravděpodobnost chyby je ještě přípustná? Řekli mi, že musíme zajistit, aby pravděpodobnost chyby pro daný pokus byla menší než šance, že dvakrát za sebou vyhrajeme v loterii. Šance, že vyhrajeme loterii, například 649, dvakrát za sebou, je 6 krát 10 na -14. Tak pro jistotu zaokrouhlíme dolů a chceme, aby pravděpodobnost chyby byla 10^(-15), což je dostatečně bezpečné. Neočekáváme, že nastane chyba, ani po stovkách nebo tisícícovkách pokusů, Zde je má otázka: "Může nám přístup k náhodnosti pomoci urychlit rozhodovací algoritmus, jako třeba test prvočíselnosti? A tohle není triviální otázka. Podívejme se na to z nadhledu. Máme sadu celých čísel například od 1 do 'n'. Tohle je náš "vesmír" celých čísel. Ten můžeme vždy rozdělit na 2 množiny. Na rozhodovací problémy se můžeme dívat jako na dělení na 2 množiny. Například: „Rozhodni, zda je 'n' menší než 100.“ Výstup bude ANO pro všechna čísla menší než 100, to je jedna množina, a NE pro ostatní, to je druhá množina. Teď se zaměřme na rozhodování, zda je číslo prvočíslem. Nejlépe bychom chtěli nějakou snadno spočitatelnou vlastnost, která platí pro všechna prvočísla, ale ne pro složená čísla. Pokud bychom znali jednoduchý vzor, který popisuje umístění provočísel a jen prvočísel, tak pro dané 'n' můžeme jen zkontrolovat, zda zapadá do daného vzoru. Bohužel, zatím žádný takový vzor nebyl nalezen, který by se jednoduše počítal a platil pro všechna prvočísla a žádná složená čísla, nebo pro všechna složená čísla a žádná prvočísla. Známe ale například rychlé testy pro většinu složených čísel. Jednoduchým kritériem je například test na sudost. Všechna sudá čísla jsou dělitelná dvojkou. Je to rychlé, protože sudá čísla poznáme pouze z poslední číslice. I když 'n' roste, tak to není větší problém. Stačí se podívat na poslední číslici, neboli číslici nejnižšího řádu. Můžeme tedy použít tento test sudosti, jako méně kvalitní test složených čísel. Náš algoritmus přijme číslo 'n' a pouze zkontroluje, zda je n sudé. Pokud je 'n' sudé a větší než 2, tak na 100 % víme, že to je složené číslo, protože máme důkaz. Číslo 2 je svědek složenosti čísla. Pokud ale 'n' není dělitelné 2, tak si nejsme jisti. Pokud je liché, tak to může být prvočíslo. Anebo je to jedno z mnoha celých čísel, která jsou lichá, např. 9 nebo 15. Kvůli této velké oblasti lichých složených čísel je tento test nevhodný. Pro ujasnění to nakreslím. Mějme nějaké n, které může být složené nebo prvočíselné. Pokud je prvočíselné, náš algoritmus jej identifikuje jako prvočíslené vždy, protože žádné prvočíslo větší než 2 není sudé. A nikdy neřekne, že je 'n' složené, pokud je 'n' prvočíslené. Pokud je ale 'n' složené, tak náš algoritmus řekne, že je složené zhruba v polovině případů, a prvočíselné zhruba v polovině případů. Když na výstupu našeho algoritmu bude „složené“, znamená to, že našel důkaz. Pokud ale náš algoritmus najde prvočíslo, víme, že je to s velkou pravděpodobností špatně. Doposud jsme se těmto velký chybám snažili vyhnout iteracemi. Nakresleme si postup našeho přístroje. Pro dané 'n', náš přístroj dělá sérii testů dělitelnosti, začne pro 'a=2'. A zeptá se, zda 'a' dělí 'n', a pokud ne, tak můžeme eliminovat celou tuto oblast. A pak zkusí, zda je 'n' dělitelné 3. Pokud ne, tak opět eliminuje celou tuto oblast. Pak zkusí dělitelnost 5, 7 a tak dále. Jsou to nepřekrývající se oblasti, které postupně vyplňují oblast složených čísel. Pokud zjistíme, že dané číslo dělí 'n', máme důkaz, že 'n' je složené, a číslo 'a' je náš svědek. Potom zastavíme iterace a vypíšeme 'složené číslo'. V opačném případě pokračujeme, dokud nevyčerpáme všechna možná složená čísla, čili dokud nenarazíme na odmocninu z 'n', protože víme, že každé složené číslo musí mít dělitele menšího nebo rovno odmocnině z 'n'. Což nás vede ke konečné otázce našeho algoritmu. Pokud nenajdemem žádné svědky a 'a' je větší než odmocnina z 'n', tak máme důkaz, zastavíme algoritmus a do výstupu dáme 'prvočíslo'. Uvědomte si, že z našeho algoritmu vedou dvě cesty. Obě cesty reprezentují důkaz, že 'n' je složené nebo prvočíslo. Pokud je 'n' prvočíslo, vyzkoušíme všechny možné dělitele a všechny je vyloučíme, což je náš důkaz, že 'n' je prvočíslo. Při téhle strategii ale musíme iterovat hodnotu 'a' přes všechny prvočísla, od 2 až po odmocninu z 'n', takže jak 'n' roste, roste počet prvočísel. V nejhorším případě potřebujeme spoustu iterací; pokud je 'n' prvočíslo. Algoritmus nám tedy poskytuje důkaz že 'n' je prvočíslo, což my nyní nepotřebujeme. Nikdo nám neříkal, že potřebuje důkaz. Jen si musíme být na 99.9999999 % jisti. Musíme se zamyslet nad naším testem na složená čísla, který používáme v našem algoritmu. Vzpomeňte si, že naše nejrychlejší testy postupným dělením, se soustředily na vzory v prvočíslech, například 6k test, všechna prvočísla mají formu 6k+1 nebo 6k-1, abychom se posouvali jen po prvočíslech pro úsporu času. Takovýto test můžeme změnit v test na složené čísla. Pro přirozené číslo 'n' ve tvaru 6k+1 nebo 6k-1, můžeme říct, že je asi prvočíslo, ale spousta složených čísel má taky tento tvar, nezahrnuje pouze prvočísla, zahrnuje prvočísla a nějaké složené čísla. Tyto složené čísla si můžeme představit jako díru, která je zdrojem našich chyb. Pokud obrátíme otázku a ptáme se, zda 'n' není formy 6k-1 nebo 6k+1, tak víme stoprocentně, že číslo je složené. Takže zdroj chyb je na straně prvočísel. V tomto případě je ale chyba nepřijatelná. Je příliš velká. Musíme najít novou testovací funkci, která je schopna zmenšit tento prostor a tím snížit šanci, že uděláme chybu. Musíme si zopakovat, jak můžeme snížit pravděpodobnost chyby pomocí iterací. Pod video pište své nápady na testy, které by se daly použít, a především jak by nám při tom mohl pomoci generátor náhodných čísel.