Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
7. lecke: Véletlen algoritmusok- Véletlen algoritmusok (bevezetés)
- Feltételes valószínűség vizuális magyarázata
- Találd ki, melyik érme volt!
- Véletlen prímteszt (bemelegítő)
- 9. szint: Próbálkozásos osztás és véletlen osztás összehasonlítása
- Kis Fermat-tétel
- Fermat-prímteszt
- 10. szint: Fermat-prímteszt
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Véletlen algoritmusok (bevezetés)
Hogyan tehetjük gyorsabbá az algoritmikus döntést véletlen számokkal? Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
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 2-nél nagyobb
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.