Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Véletlenszámok

  [1]    [2]  

Szeretnél hozzászólni? Jelentkezz be.
[7] Tamás2004-10-23 09:28:39

Köszönöm ezt a kis leírást, nagyjából megértettem a dolgot csak azt nem hogy egy hardveres eszköz miért képes valós vélszámot előállítani? Valójában azt is egy szoftver müködteti, vagy nincs összefüggés? A másik dolog amit nem értek hogy miért kellene bonyolult algoritmusokat,függvényeket..stb. kitalálni illetve alkalmazni ha mindezt egy eszköz megteszi?! ( Bár mondjuk most lehet hogy az utólsó kérdésemre magam adom meg a választ, ha jól tudom egy jó hardveres vélszám előállító kb. 1000 dollár!!! körül mozog!)

Üdv.

Előzmény: [6] Kós Géza, 2004-10-22 13:57:25
[6] Kós Géza2004-10-22 13:57:25

Kedves Tamás,

A tisztán szoftveres megoldások egy kis kiinduló adatból gyártanak hosszú sorozatot. Mondjuk egy 64 (vagy n) bites kezdőértékből készítenek 1024 (N) hosszú bitsorozatot. Mivel kezdőértékből kevesebb van, mint N-hosszú sorozatból, a lehetséges sorozatoknak csak kis töredékét állíthatják elő. A véletlenszám-generátor tehát az összes sorozatnak egy kis részhalmazából, 2n sorozat közül választ véletlenszerűen.

A különböző hardver-zajok hozzákeverése ezen segít, és ez bizonyos esetekben szükséges is.

* * *

Sokféle véletlentesztet lehet készíteni. A [3]-beli példában az is működött, hogy ellenőriztük az eloszlást. De azt is figyelni lehet, hogy különböző minták (pl. töbször egymás után ugyanaz az érték) milyen gyakran fordulnak elő.

Jó játék az a program, ami tippel, hogy fejet vagy írást fogsz mondani. Te mindig megnyomod az I vagy az F gombot, a gép ezután megmondja, hogy mire tippelt, és eddig hányszor talált és hányszor tévedett.

A program úgy működik, hogy nyilvántartást vezet a szokásaidról, hogy az utolsó egy-két lépés után mit szoktál mondani. Például, ha te kétszer egymás után fejet mondtál, és a program mindkétszer eltalálta, akkor mit szoktál mondani gyakrabban.

* * *

Az elméleti megközelítés valami ilyesmi. Egy "véletlenteszt" egy olyan program, ami minden sorozatra mond valamit, mondjuk azt hogy A vagy azt, hogy B. A teszttől elvárjuk, hogy "gyors" legyen, mondjuk létezzen egy olyan c konstans, hogy egy N hosszú sorozathoz tartozó választ legfeljebb Nc lépésben kiszámolja.

Képzeljük el, hogy a tesztet kipróbáljuk N hosszúságú álvéletlen sorozatokon, amiket egy véletlenszám-generátorral állítunk elő, és kipróbáljuk igazi véletlen sorozatokon is. Mindkét esetben bizonyos sorozatokra A-t, a többire B-t fog mondani. Ha a két válasz eloszlása lényegesen különböző a véletlen és az álvéletlen sorozatokon, akkor a teszt lebuktatja a véletlenszám-generátort.

Az, hogy az eloszlások lényegesen különbözők, azt jelenti, hogy van olyan c2 konstans, hogy az A válasz valószínűségének különbsége legalább 1/Nc2.

Legyen mondjuk a sorozat hossza is n hatványa, N\approxnc3 és a véletlenszám-generátortól is elvárjuk, hogy az N hosszú sorozatot legfeljebb Nc4 lépésben előállítsa.

A kérdés ezek után az, hogy van-e olyan véletlenszám-generátor, ami minden tesztet átver. Bizonyos számelméleti sejtéseket feltételezve, ilyen konstrukciók léteznek. Például ha feltételezzük, hogy egy n-jegyű számot nem lehet n-hatvány idő alatt prímtényezőkre bontani, akkor ebből lehet jó (bár kicsit lassú) véletlenszám-generátort konstruálni.

Előzmény: [5] Tamás, 2004-10-22 12:57:38
[5] Tamás2004-10-22 12:57:38

Kedves Géza!

Valójában nekem inkább egy kérdésem lenne a véletlenszámokkal kapcsolatban! Látom hogy Te otthon vagy ebben a témában ezért főként Neked címzem a kérdést. Azt azért elmondom hogy nem vagyok egy matek zseni,csak hobbi szinten foglakozom ezzel. Ha pl.:dobókockával,pénzérmével...stb. "játszadozom" akkor ott ugyebár tökéletesen érvényesül a véletlenszerűség törvénye, a kérdésem az lenne hogy számítógéppel elő lehet-e állítani valós véletlenszámokat?(Halottam olyan elméleteket miszerint a szoftveres generálás csak álvéletlenszámokat készít, de hardveres úton viszont megoldható!Ez igaz?)Egyáltatán hogyan tudom azt megállapítani egy számsorozatról hogy az valóban teljesen véletlenszerűen keletkezett és nem csak álvélszámok?

Ha tudsz nekem segíteni azt előre is megköszönöm! Üdv,Tamás.

[4] Hajba Károly2004-10-12 22:09:26

Kedves Géza!

Először ránézésre tippeltem, hogy a II. sor a véletlen, majd kiszámoltam az eloszlásokat. Az I. sor túl szabályosnak tűnik, így tartom a tippem: a II. a pénzdobásos valódi véletlensor.

Üdv: HK

Előzmény: [3] Kós Géza, 2004-10-12 19:23:01
[3] Kós Géza2004-10-12 19:23:01

A témának igen szerteágazó elmélete és alkalmazása van a kriptográfia különböző területein; véletlen titkosító kulcsok generálása és ezek feltörhetősége, egyirányú függvények, digitális aláírás ...

* * *

Kezdjük az elején.

A véletlenszám-generálás azt jelenti, hogy készítünk egy (tetszőleges hosszúságú) sorozatot, ami nagyon hasonlít a valódi véletlen sorozatokra.

Egy véletlenszám-generátor valahogy így főzi a véletlen számokat:

Vesz egy kondért, amiben véletlen számok (bitek) vannak. Ez jöhet külső zajokból (idő, utolsó gombnyomás időpontja és hossza mikroszekundumban stb.) A kondéron kever egyet, aztán merít belőle egy számot. Megint kever, megint merít. Esetleg újabb zajokat kever hozzá.

Két lényeges leegyszerűsítés szokott előfordulni.

a) Menet közben nem kever hozzá semmit. Ebben az esetben a kezdőállapot meghatározza a teljes sorozatot.

b) Még a kezdőállapot is mindig ugyanaz. (Programok tesztelésekor ez nem haszontalan dolog...)

* * *

Mondok egy egyszerű, sőt inkább buta példát. Fej vagy írás sorozatot szeretnénk készíteni, és erre a következő programot használjuk.

1. Vegyünk egy s valós számot 0 és 1 között.

2. Merítés: Ha s>\frac12, akkor írjuk ki azt, hogy "fej"; ellenkező esetben "írás".

3. Keverés: Írjuk s helyére a 3s szám tört részét.

4. Folytassuk a 2. ponttól.

Miután megírtuk a programot, kísérletképpen két, 50 hosszúságú sorozatot készítünk. Az egyiknél egy pénzdarabot dobunk fel 50-szor, a másiknál a programot használjuk. A két sorozatot odaadjuk valakinek, akinek tippelnie kell, hogy melyik a véletlen.

Én most készítettem két ilyen sorozatot. Az egyiket pénzdobálással, a másikat a fenti programmal. Vajon melyik lehet a véletlen és miért?

IIFIFFIIFFFFIFFIIIFFFFIFIFIIIIIFIIFIIIFIFIIIFIFIFF

FIIFFFFFFIIFFFFFFIFIFFFIFFFIIFFIIIIFIFFFIIFFFFIFIF

[2] Suhanc2004-10-12 17:21:14

Kedves Györke!

Ehhez a témához egyátalán nem értek, de amíg valaki érdemben hozzá nem szól, leírok egy régebben alkalmazott megoldást, amit xyz..(nem tudom hol)...olvastam:

A régi játékprogramokban a program az akuális időből készített véletlenszámot. Például úgy, hogy vette az óra+perc+másodperc összeg, mondjuk 7-es maradékát. Ez elég egységes eloszlást hozott létre... bár, ha jól tudom, ma ezt már egyetlen játékprogramban, sőt másutt sem alkalmazzák...;D

Előzmény: [1] Farkas Györke, 2004-10-12 13:20:56
[1] Farkas Györke2004-10-12 13:20:56

No, akkor nyitok egy új témát a véletlenszám-generálásnak. Tudja valaki, hogy hogyan állít elő a CD-lejátszó tetszőleges lejátszási sorrendet és a számológép "véletlen" számokat? Hogyan lehet matematikailag véletlent létrehozni?

  [1]    [2]