XIII. Bolyai Konferencia Bodnár József Eötvös József Collegium, ELTE TTK, III. matematikus
A véletlen nyomában
Mi is az a véletlen? 1111111111, 1010101010, 1100010111 valószínűsége egyaránt 1/1024
Melyiket könnyebb megjegyezni? A Hardy-Ramanujan anekdota: miért jegyezte meg Ramanujan az 1729-et? 1729 = 13 + 123 = 93 + 103 Srinivasa Ramanujan
Univerzális Turing-gép: adatszalag + programszalag = kimenet Egy „szó” Kolmogorov-bonyolultsága a legrövidebb program hossza, mely kiírja őt. A tömörítőprogramok elve! Turing-gép
Tényleg „egyszerű” a nem véletlen? Miért nem véletlen az 1010101010101010101010101010101010101010 sorozat? for i := 1 to 20 do write(10) A sorozatot előállító program sokkal rövidebb a sorozatnál! A „szó” Kolmogorov-bonyolultsága kisebb a hosszánál: K(x) < |x| Az ilyen „szó” jól tömöríthető. Végtelen sorozat informatikus véletlensége: Kezdőszeleteinek bonyolultsága „átlagban” nagy: K(xn)/n 1 vagy K(xn) – n korlátos. Független, ½ valószínűséggel 0 vagy 1 értékű valószínűségi változók érétkeinek végtelen sorozata 1 valószínűséggel informatikusan véletlen. Azaz: ami a valószínűségszámítás alapján véletlennek gondolt sorozat a mi definíciónk szerint is véletlen!
Mit várunk a statisztika alapján? Alapvető elvárás az átlag: a 1001100010 sorozat átlaga 0,4, a várható érték 0,5. Az egyesek relatív gyakorisága jó közelítéssel a valószínűség. x egy n hosszú sorozat k darab 1-essel. Mennyi a bonyolultsága? Egy programnak elég megadni, hányadik a sorozat a k darab 1-est n tartalmazó n hosszú sorozatok (legfeljebb ( k ) darab ilyen szó) között: 1.: 00011 Megadandó: 4, 2, 5. 2.: 00101 Egy N szám megadásához kb. 3.: 00110 log N darab jegy kell. 4.: 01001 Azaz az x sorozat megadásához 5.: 01010 (alkalmas program mellett) 6.: 01100 log ( n ) + log n + log k + c k 7.: 10001 jegy elég. 8.: 10010 9.: 10100 Ez jóval kisebb lehet, mint n, 10: 11000 ha k nagyon eltér n/2-től.
Egyéb statisztikai tesztek: Legnagyobb blokkméret: Khi-négyzet próba: T =
1000001110100100111111111101001 (egyesek száma – n/2)2 + (nullák száma – n/2)2 n/2
Néhány (ál)véletlen sorozat statisztikai tesztjei: (184 – 200 bites sorozatok) Khi (%) Dobókocka Pascal Excel Ember (nem figyel)
Ember (figyel) Ember (billentyűütögetés)
88,28 47,95 25,79 88,28 76,81
30,20 Khi (%)
Dobókocka Pénzérme
0,51 38,16
Korreláció
0,130332 0,077694 -0,127210
Khi (%) Dobókocka
Korreláció
Excel
55,53 57,16 77,73
0,019886 -0,021640 -0,100440
-0,065340
Ember (nem figyel)
37,63
-0,091600
-0,348460
Ember (figyel)
76,81
-0,217970
-0,465000
Ember (billentyűütögetés)
10,48
-0,411480
Pascal
Korreláció
-0,044550 -0,003000
Khi (%) Pascal Excel Ember
99,99 15,73 88,52
Korreláció
0 0,030303 -0,104290
Álvéltetlenszámok: xn+1 := a xn + b mod m
Mindenképpen periodikus, de ha a periódus hosszú, ez nem zavaró. Spektrálpróba: a véletlenszámokat valahány dimenziós koordinátáknak tekintjük.
A Monte Carlo módszer Numerikus integrálás: Egyenletes eloszlású pontokat generálva: Területarány = az odaesés valószínűsége = relatív gyakoriság
Hányszor lesz f(xn) > yn ? Főleg gyorsan oszcilláló függvényekre hasznos:
Véletlenszámok alkalmazása: polinomazonosság ellenőrzése A soktényezős szorzat kibontása exponenciálisan sok taghoz vezetne! Megoldás: Találgassunk behelyettesítési értékeket. Kicsi az esély, hogy gyököt találunk, ha a polinom nem azonosan nulla: Egy f(x1, …, xn) nem nulla, xi a [0, … N -1] intervallumból való érték. Ekkor Nn féle behelyettesítésből legfeljebb kNn-1 esetben lesz nulla a helyettesítési érték. Véletlenszerű választással: a 0 helyettesítési érték esélye legfeljebb k/N. N := 2k választással, 100-szor ismételve az eljárást, csak 1/2100 az esélye, az egyik irányban tévedünk a polinom 0 voltát illetően. Gyakorlatilag megbízható polinomiális algoritmus!
Egy meglepő gráfelméleti alkalmazás: párosítás páros gráfokban A gráfot egy mátrixszal ábrázoljuk 1
2
3
4
A
0
XA2
0
XA4
B
XB1
0
0
0
C
0
XC2
0
XC4
D
0
0
XD3
0
Akkor és csak akkor van teljes párosítás, ha a mátrixhoz tartozó determinánspolinom nem azonosan 0! (A polinom egy nem 0 tagja egy kifejtési tag.) Létezik determinisztikus algoritmus is, de ez jól párhuzamosítható!
Kommunikációs protokollok …01…
…11…
10001110…01
10101110…01
Pl.: A két gépnek el kell döntenie (minél kevesebb információcserével), hogy azonosak-e az n hosszúságú bemeneteik. Bizonyítható (és nem is túlságosan meglepő), hogy ahhoz, hogy ezt eldöntsék, legalább n bites forgalmat kell bonyolítsanak. Randomizált protokollal ez 2 log n + konstansra csökkenthető! Az eredmény nem lesz tökéletesen biztos, de a tévedés lehetősége kicsivé tehető!
Randomizált protokoll: x és y a két n hosszú bemenet. Rögzítsünk egy N számot, majd véletlenszerűen válasszunk egy N-nél kisebb p prímet. Elküldeni: p-t és x p-vel való osztásakor keletkező r maradékot. r ≤ p ≤ N : elküldendő 2 log n bit x az n hosszú bemenet
y maradéka p-vel osztáskor r?
y az n hosszú bemenet
Tévedünk, ha p osztója x – y = d –nek. d = p1…pk prímfelbontás. 2n ≥ d ≥ 2.3. … .q ≥ 2q-1 , azaz n ≥ q, a k-adik prím. Vagyis n-ig legalább k darab prím van. A tévedés valószínűsége k/(prímek száma N-ig) ≤ (prímek száma n-ig)/(prímek száma N-ig). A prímszámtétel szerint ez kb. 1/c, ha N = cn. Azaz tetszőlegesen kicsivé tehető.
Prímtényezőkre bontás Egy szám prítényezőkre bontására nem ismert gyors (polinomiális) algoritmus, még randomizált sem. De a leggyorsabbak, legtöbbször célravezetők nem determinisztikusak. Pl.: N egy prímosztóját keressük; ha N osztója u2 – v2 = (u + v)(u - v) –nek, de nem osztója egyik tényezőnek sem, akkor lnko(N, a + b) osztója N-nek. Lnko számítása gyors (euklideszi algoritmus). Kell: u, v pár, hogy u2 ≡ v2 mod N, de u ≡ ±v mod N. Az első feltételhez: keresünk bj-t, hogy bj2-nek N-nel való osztási maradéka, cj csak R-nél kisebb prímekkel osztható (R rögzített). Eggyel több bj-t választunk, mint ahány prím van R-ig. Ekkor néhány cj szorzata négyzetszám lesz: v2 = cj = bj2 = u2
Prímtényezőkre bontás Teljesül-e a második, u ≡ ±v mod N feltétel? Legalább ½ valószínűséggel IGEN! Tegyük fel, hogy N = pq, két prím szorzata. Tudjuk, hogy u2 ≡ v2 mod N, azaz u2 ≡ v2 mod p és u2 ≡ v2 mod q azaz: mod p u ≡ +v u ≡ +v u ≡ -v u ≡ -v
mod q u ≡ +v u ≡ -v u ≡ +v u ≡ -v
mod N u ≡ ±v u ≡ ±v u ≡ ±v u ≡ ±v
• Irodalom: Hraskó András: Új matematikai mozaik Knuth, D. E.: A számítógép-programozás művészete, 2. kötet Lovász László: Algoritmusok bonyolultsága Srejgyer, A.: Monte Carlo módszerek • Internetes hivatkozások: www.fourmilab.ch/random ENT véletlenségtesztelő program
