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 prímteszt (bemelegítő)
Bevezetés a véletlen prímtesztek területére és működési elvükbe. (Bemelegítő.). Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
Először építsük fel az új típusú véletlen
algoritmus elméleti működésének modelljét, ami fogad egy N bemenetet, és ha N prímszám, akkor az algoritmus 100%-os
biztonsággal prímet ad vissza. Soha nem fogja azt mondani,
hogy összetett. Viszont ha N összetett, van rá egy minimális „e” esély,
hogy ezt is prímnek jelöli meg. Különben 1 mínusz ez a kicsi hiba a
valószínűsége, hogy helyesen összetettnek
fogja-e minősíteni N-et. Induljunk valami egyszerűvel. Vegyük az egész számokat
egy adott határig. Válasszunk ki egy egész számot,
jelöljük N-nel. Megadjuk ezt az N-et a gépnek. Korábban a próbálkozásos algoritmus
módszernél iterációval végigvettük az összes értéket
1-től négyzetgyök N-ig, és megnéztük, hogy a szám osztója-e N-nek. Ideális esetben időspórolás miatt
csak a prímszámokat vizsgáltuk. Ha A osztója N-nek, akkor tudjuk,
hogy N összetett szám, mert bizonyítékot találtunk rá. Ha nem, akkor
nem vagyunk benne biztosak. Visszatérünk, megnöveljük A-t,
és újra tesztelünk. Ha kimerítettük az összes
lehetséges tesztet, akkor kimondhatjuk:
igen, N prímszám, nem találtunk osztót. Most pedig legyünk lusták. Mi lenne, ha csak néhány,
véletlenül kiválasztott egészet vennénk, és azokkal végeznénk el
az oszthatósági próbát? Ezt tekinthetjük véletlen tesztnek. Tudjuk azt, hogy egy
tetszőleges N szám, ha összetett,
van valahol elszórva osztója. Legalább egy osztója lesz. Egyes összetett számoknak
sok osztója van. Szóval választunk egy véletlen A számot
1 és négyzetgyök N között. Ennyi. Aztán ellenőrizzük,
hogy A osztója-e N-nek. Mint korábban is, ha A osztója N-nek, akkor biztosan tudjuk, N összetett,
bizonyítékunk van rá. Ha nem, nem jutottunk sokkal előbbre,
lehet akár prím is. A biztonság kedvéért generálhatunk
még néhány véletlen A-t, és folytathatjuk a tesztelést. 100 vagy 1000 iteráció után
megállhatunk és kimondhatjuk: „Valamilyen valószínűséggel
feltehetőleg prímszám”. Mondjuk 99,9%-os valószínűséggel. Ez hasonlít az előző feltételes
valószínűséges játékhoz. A legegyszerűbb helyzetben megpróbáltuk
megbecsülni, hogy az érme normális vagy dupla oldalú. Ebben az esetben az írás olyan,
mint az osztó megkeresése. Ez a normális érme bizonyítéka. A fej az az eset, amikor lehet, hogy új
dobást, azaz egy új iterációt kérünk. Ebben az esetben úgy 5 fej után
90%-nál biztosabbak vagyunk, úgyhogy megállhatunk azt mondván:
– Azt gondolom, az érme kétoldalas. Itt a program, ami összehasonlítja a régi,
próbálkozásos osztást használó módszert ezzel az új, véletlen
osztásos teszttel. Az eddigi leggyorsabb próbálkozásos osztás
algoritmust használtam fel, amit Dino készített. A program fejlécében
megtalálod a linket. Az elején ott a numTrials változó, ami a
véletlen találgatások számát tárolja. Kezdjük egy kis számmal,
mondjuk 3-mal. Figyeld meg, hogy kis bemenet esetén is, ha a bemenet prímszám, a véletlen osztásos algoritmus
mindig prímszámot eredményez. Ha a bemenet összetett, a véletlen osztás
tévedhet, és hibásan prímként azonosítja. Ezen javíthatunk úgy, hogy
megnöveljük a próbálkozások számát, ekkor a hiba valószínűsége
csökkenni fog. Láthatjuk, hogy most
a két kimenet nagyjából megegyezik. Ahogy a bemenet értékét növelem,
a hiba újból megnő. Ennek megfelelően növelnem kell
a próbálkozások számát. Ekkor az eredmények megint szépen
összecsengenek. Azonosnak tűnnek. Hatalmas bemeneti értékkel több ezer
véletlen teszt kell a pontossághoz. Így nem igazán javítottuk
a szükséges lépésszámot. Még mindig jobbnak tűnik
a próbálkozásos osztás algoritmusa. Ennek az az oka, hogy az osztás tesztnek
nagyon magas a hibaszázaléka, de már közelebb jutottunk.
Megtaláltuk a helyes utat. Más tesztre van szükségünk. Olyan egyenlet kell,
ami gyorsan kiszámolható, amivel bizonyíthatjuk,
hogy a szám összetett. Nem csak a bemeneti
N értéket kell fogadnia, hanem egy véletlen A egészet is, és el kell végeznie
valamilyen véletlen tesztet.