Véletlen algoritmusok (bevezetés)

Van egy új infóm. A NASA közölte, hogy a marsjárón lesz egy véletlenszám generátor eszköz, amit használhatunk. Újból felhívták a figyelmünket arra, hogy az algoritmusnak a gyakorlati igényeknek kell megfelelnie. Az, hogy valami a gyakorlati igényeknek feleljen meg, azt jelenti, hogy mindig előfordulhat hiba, de a hiba valószínűsége olyan alacsony, hogy a gyakorlatban figyelmen kívül hagyjuk, és ha ez őrültségnek hangzik, vedd figyelembe, hogy a való életben soha semmi nem biztos, mindig van hibalehetőség. Például a sült krumplis zacskóban kis mennyiségű radioaktív szennyeződés található, és amikor az lebomlik, alfa részecskéket bocsájt ki, amik át tudják állítani a memóriabiteket, így váratlanul megváltoztathatják egy szám értékét. Még érdekesebb, hogy a kozmikus sugárzás is okozhat szoftver hibát. A hibalehetőséget sohasem küszöbölhetjük ki teljesen. Megkérdeztem a NASA-t, pontosan mekkora az elfogadható hibahatár. Azt felelték: – Biztosítani kell, hogy egy adott kísérlet esetén a hiba valószínűsége kisebb legyen, mint hogy kétszer egymás után telitalálatod legyen a lottón. Annak a valószínűsége, hogy kétszer egymás után eltalálj 6 számot 49-ből, 5,1122 E-15. Kerekítsük ezt, és vegyük a hiba valószínűségét tíz a mínusz tizenötödikennek. Biztonságosnak tűnik, nem valószínű, hogy hibába futunk több száz vagy ezer futás során. Most a kérdés az, hozzáférésünk a véletlen számokhoz segít-e a döntési algoritmus, nevezetesen a prímteszt felgyorsításában? Ez egy mélyreható kérdés, úgyhogy álljunk meg, és vizsgáljuk meg a teljes képet. Ha adott az [1,N] intervallumban az egész számok egy halmaza, tekintsük ezt a rendelkezésre álló egész számok összességének. Minden halmazt fel tudunk osztani két részre. Egy döntési feladatot mindig tekinthetünk két halmazra való felosztásként. Példaként vegyünk egy N-t, ahol N<100, itt igazat kapunk minden 100-nál kisebb N esetén. Ez lesz az egyik halmaz, és hamisat kapunk a többi számra, ez lesz a másik halmaz. Most fókuszáljunk arra, hogyan ismerjük fel a prímeket a döntés során. Ideális esetben egy egyszerűen kiszámítható feltétel kellene, aminek minden prímszám megfelel, de egy összetett szám sem. Ha ismernénk valamilyen egyszerű mintát, ami leírja a prímszámok helyét, de csak a prímszámokét, akkor bármely adott N-re egyszerűen meg tudnánk mondani, hogy N beleillik-e a mintába. Az a baj, hogy egyenlőre még egyetlen teljes érvényű és egyszerűen kiszámítható mintát se találtak, ami minden prímszámra igaz, és minden összetett számra hamis, vagy minden prímszámra hamis, és minden összetett számra igaz lenne. Viszont ismerünk néhány gyors tesztet, ami a legtöbb összetett számra érvényes. Például egy egyszerűen kiszámítható feltétel lehetne a párosság vizsgálata. Minden páros szám osztható 2-vel. Ez gyors, mert az utolsó számjegy alapján meg tudjuk mondani, ha a szám páros, és az N növekedésével ez nem válik egyre nehezebbé, mindig csak az utolsó számjegyet nézzük, amit legalacsonyabb helyiértékű bitből is megállapíthatunk. Namármost a párosság vizsgálatot tekinthetjük egy kis hatékonyságú összetettség vizsgálatnak. Lehet egy olyan algoritmusunk, ami beolvassa az N egész számot, és nem tesz mást, csak megvizsgálja, hogy az páros-e. Ha páros, és nagyobb, mint 2, akkor 100%-os biztonsággal állíthatjuk, hogy összetett, bizonyítékunk van rá. A 2 az összetettség bizonyítéka. Ha nem, akkor nem vagyunk benne biztosak. Ha páratlan, akkor lehet prím, mivel minden prímszám páratlan, vagy lehet azon nagyszámú összetetteknek egyike, amik páratlanok, mint a 9, vagy a 15. A páratlan összetett számok nagy száma teszi ezt a tesztet elfogadhatatlanná. Hogy mindez világos legyen, rajzoljunk! Ha adott N, N vagy prímszám, vagy összetett. Ha N prím, az algoritmusunk 100%-osan prímet fog mondani, mivel nincs 2-nél nagyobb páros prímszám. Soha nem fog összetettet mondani, ha prímszám a bemenet. De ha N összetett, körülbelül az esetek 50%-ában mondja az algoritmus, hogy az összetett, és 50%-ban mond prímet. Ez azt jelenti, hogy amikor az algoritmus összetettet mond, akkor bizonyítékot talált az összetettségre. De ha az algoritmus prímet mond, akkor tudjuk, hogy a hiba esélye elfogadhatatlanul nagy. A stratégiánk ezt az elfogadhatatlanul nagy hibát eddig az iterációval kezelte. Rajzoljuk fel a gép működését. Adott N, a gép elvégez egy sor oszthatósági tesztet. A = 2 a kiindulópont. Felteszi a kérdést, A osztója N-nek? Ha nem osztója N-nek, akkor ezt az egész területet kizárhatjuk. Utána jön a következő kérdést: N osztható 3-mal? Ha nem, akkor ezt az egész részt kizárhatjuk. N osztható 5-tel, 7-tel stb. Figyeld meg, hogy ezek diszjunkt halmazok, amik fokozatosan feltöltik a lehetséges összetett számokat. Ha menet közben bármikor igent mondunk, akkor bizonyítékunk van arra, hogy N összetett. Az A lesz a bizonyíték, bármi legyen is az értéke az adott pillanatban. Megállunk, az algoritmus kimenete az, hogy N összetett. Ellenkező esetben addig folytatjuk, amíg el nem fogynak a lehetséges összetett számok. Amíg el nem érjük N négyzetgyökét, mivel tudjuk, hogy minden összetett N szám prímtényezői kisebbek vagy egyenlőek N négyzetgyökével. Ez elvezet az algoritmusunk által felvetett utolsó kérdéshez. Ha nem találunk bizonyítékot, és A nagyobb N négyzetgyökénél, akkor van egy új bizonyítékunk, megállunk, és a kimenet prímszám lesz. Figyeld meg, hogy két kimeneti útvonal van az algoritmusban. Mindkét kimenet bizonyítottan állítja, hogy N prímszám vagy összetett. Ha N prím, kipróbáljuk az összes lehetséges osztót, és mindegyiket kizárjuk, és ez annak bizonyítéka, hogy N prímszám. Ezzel a stratégiával az a baj, hogy az A értékének minimum az összes prímszámot végig kell vennie 2-től négyzetgyök N-ig. Ahogy nő N értéke, úgy nő a prímek száma, ami megnöveli az iterációk számát a legrosszabb esetben, amikor az algoritmus bemenete prímszám. Ha megvizsgáljuk az összképet, látjuk, hogy ha N prím, azt bizonyítani tudjuk. De most már tudjuk, hogy nem pont erre van szükségünk. Senki nem mondta, hogy bizonyítani kell. Csak az kell, hogy 99,9999 – itt tizenöt 9 jön – %-osan biztosak legyünk benne. Szóval el kellene gondolkodnunk az algoritmus összetettség vizsgálatán. Egy gyorsabb próbálkozásos osztáson alapuló prímteszt a 6K-s prím mintázatot használja, ami azon alapul, hogy minden prímszám felírható 6K ± 1 alakban, ami segít abban, hogy csak prímeket vizsgáljunk, és kihagyjunk egy csomó összetett számot, így spórolva meg az időt. Egy ilyen próba átalakítható összetettség tesztté. Azaz ha adott egy N egész szám, ami 6K ± 1 alakú, akkor kimondhatjuk, hogy valószínűleg prímszám, de számos ilyen alakú összetett szám is van. Nemcsak a prímek ilyenek, az összes prím és egyes összetett számok is ilyenek. Ezeket az összetett számokat tekinthetjük hibaforrásnak. Ha ezt megfordítjuk, és azt vizsgáljuk, hogy ha N nem írható fel 6K ± 1 alakban, akkor 100%-os biztonsággal állíthatjuk, hogy N összetett, úgyhogy a hibaforrás a prímtesztnél van, de ez ebben az esetben elfogadhatatlan, ez egy nem elhanyagolható hiba. Túl nagy a valószínűsége. Más összetettség vizsgálatot kell kitalálni, olyat, ami képes leszűkíteni ezt a teret, és a hibalehetőséget elhanyagolhatóvá csökkenteni. Ez azt jelenti, hogy át kell tekinteni, hogyan tudjuk iterációval csökkenteni a hibát. Tegyétek fel az ötleteteket a Kérdésekben, milyen vizsgálatokat végezhetnénk, és ami még fontosabb, hogyan tudna segíteni egy véletlenszám generátor.