Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Provjera

[es] :: Art of Programming :: Provjera

[ Pregleda: 2718 | Odgovora: 8 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

dragisha

Član broj: 2500
Poruke: 12
*.rstel.net



Profil

icon Provjera 15.12.2003. u 15:13 - pre 247 meseci
Imam osam brojeva od 0-25 za koje zelim da znam da li su, ili nisu, sekvenca dobijena od C++ rand() funkcije. Ako ne tačno, onda sa nekom (poznatom) vjerovatnoćom da jesu.

C++ kompajler je, mislim, Visual C++ 7.1 (postoji tako nešto?:)

Hvala,
dd
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Provjera15.12.2003. u 15:22 - pre 247 meseci
"dragisha" wrote:
> Imam osam brojeva od 0-25 za koje zelim da znam da li su, ili nisu,
> sekvenca dobijena od C++ rand() funkcije. Ako ne tačno, onda sa nekom
> (poznatom) vjerovatnoćom da jesu.

Egzaktno i presporo rešenje: računaš kros-korelaciju sa sekvencom koju
daje odgovarajuća rand() funkcija. Vrednost korelacije koja te
interesuje je poznata i tačno je jednaka zbiru kvadrata datih brojeva.
To naravno traži da iteriraš po celoj sekvenci brojeva i verovatno nije
praktično.

Približno i malo bolje rešenje: Modeluješ generator slučajnih brojeva
kao Markovljev proces i izračunaš verovatnoću da model generiše
sekvencu. [Da, da, znam, ovo traži malo duže objašnjenje...]

Sasvim približno rešenje: Napraviš empirijsku funkciju raspodele nad
kodomenom funkcije rand i za svoju sekvencu uradiš hi-kvadrat test.

(ubr ove su idejice samo „food for thought“, verovatno bi trebalo poraditi na detaljima i praktičnosti)

f
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Provjera15.12.2003. u 15:37 - pre 246 meseci
Mislim da sam uzeo preveliki čekić u prošloj poruci. :) Zaboravih da je
izvorni kod f-je rand() poznata stvar.

Pogledaš kakav je rand algoritam (sors biblioteke postoji čak i kada je
u pitanju M$) i ubaciš u njega prvih nekoliko članova datog niza --
onoliko dugačak koliko je dug history random generatora. Random
generatori su obično oblika

x(n+1) = f(x(n-k+1),...,x(n))

pa ćeš, ako imaš dovoljno brojeva da popuniš sve parametre u f-ji f moći
lako da proveriš da li je ili nije odgovarajuća sekvenca generisana
(poznatom!) funkcijom f. Ako nemaš dovoljno brojeva, onda možeš da
povećaš čekić nekim metodom iz prethodne poruke.

f
 
Odgovor na temu

dragisha

Član broj: 2500
Poruke: 12
*.rstel.net



Profil

icon Re: Provjera15.12.2003. u 19:56 - pre 246 meseci
Citat:
filmil:
Mislim da sam uzeo preveliki čekić u prošloj poruci. :) Zaboravih da je
izvorni kod f-je rand() poznata stvar.


Ne da su preveliki čekići... I postoje dva glavna problema. Prvi problem je što je moj uzorak sirot i nikakav - osam brojeva :)...

Citat:
Pogledaš kakav je rand algoritam (sors biblioteke postoji čak i kada je
u pitanju M$) i ubaciš u njega prvih nekoliko članova datog niza --
onoliko dugačak koliko je dug history random generatora. Random
generatori su obično oblika

x(n+1) = f(x(n-k+1),...,x(n))


...drugi problem je što ja imam brojeve od 0-25, koji su dobijeni sa _rand() % 26 :). Od čega sam dobio recimo 24, to ne zna ni njegova svjetlost Bill Gates :).

Citat:
pa ćeš, ako imaš dovoljno brojeva da popuniš sve parametre u f-ji f moći
lako da proveriš da li je ili nije odgovarajuća sekvenca generisana
(poznatom!) funkcijom f.


Samo što, kako rekoh, NEMAM te brojeve. Imam degenerisani (sa % 26) oblik istih.

Citat:
Ako nemaš dovoljno brojeva, onda možeš da
povećaš čekić nekim metodom iz prethodne poruke.


Ti možda radiš Markovljevo ovo ili ono svaki dan, ja jedino zasigurno znam da taj nema veze sa psima (to je Pavlov, valjda...:). E sad, da ja ne potežem Norviga, potroši još malo vremena pa pojasni molim te taj veći čekić.

Poz,
dd
 
Odgovor na temu

dragisha

Član broj: 2500
Poruke: 12
*.rstel.net



Profil

icon Re: Provjera 15.12.2003. u 20:20 - pre 246 meseci
Another twist... Postoje li tabele vjerovatnoća pojavljivanja po dva ili tri ili četiri uzastopna slova u engleskim, odnosno srpskim riječima? Tj, postoje li u naš domain vlasništvu ? :)
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Provjera15.12.2003. u 20:39 - pre 246 meseci
"dragisha" wrote:
> riječima? Tj, postoje li u naš domain vlasništvu ? :)
Nisam siguran da postoje, ali možeš napraviti empirijske raspodele,
koristeći recimo tekstove sa Projekta Gutenberg za engleski ili sa
Rastka za srpski i, na primer, ovaj program dole.

f

Code:

#! /usr/bin/perl
# Unigram, bigram and trigram statistic for input text files.

%unigram = ();
%bigram = ();
%trigram = ();
$nuni = 0;
$nbi = 0;
$ntri = 0;

@lines = <STDIN>;
foreach $line (@lines ) {
$line =~ tr/[a-z]/[A-Z]/;
@words = split( /[" "]+/, $line);
foreach $word (@words) {
$word =~ s/[^A-Z]//g;
$l = length $word;
for($i = 0; $i < $l; ++$i ) {
$uni = substr($word,$i,1);
$nuni++;
if ( $unigram{$uni} == "" ) {
$unigram{$uni} = 1;
} else {
$unigram{$uni}++;
}
if ( $i < $l - 1) {
$bi = substr($word,$i,2);
$nbi++;
if ( $bigram{$bi} == "" ) {
$bigram{$bi} = 1;
} else {
$bigram{$bi}++;
}
}
if ( $i < $l - 2) {
$tri = substr($word,$i,3);
$ntri++;
if ( $trigram{$tri} == "" ) {
$trigram{$tri} = 1;
} else {
$trigram{$tri}++;
}
}
}
}
}

while( ($a, $b) = each (%trigram)) {
$condbi = substr($a,0,2);
$bifreq = $bigram{$condbi};

# Izdvoj slova iz stringa
$fll = substr($a,0,1);
$sll = substr($a,1,1);
$tll = substr($a,2,1);

# spoji prvo i trece

$ftl = $fll.$tll;
$bifreq2 = $bigram{$ftl};

$fl = ord(substr($a,0,1)) - ord("A");
$sl = ord(substr($a,1,1)) - ord("A");
$tl = ord(substr($a,2,1)) - ord("A");

print $fl*(26**2) + $sl * 26 + $tl;
print " ";
$e1 = $b/(26**3);
$e2 = $bifreq/(26**2);
$e3 = $e1/$e2;

# novo racunanje

$e5 = $bifreq2/(26**2);
$e6 = $e1/$e5;

print "$e3
";
}

 
Odgovor na temu

dragisha

Član broj: 2500
Poruke: 12
*.rstel.net



Profil

icon Re: Provjera 16.12.2003. u 06:43 - pre 246 meseci
Hoću (empirijske raspodjele), čim mi bude toliko važno da ubijem baš vola :).

Pitah i na drugoj strani i dobih prijedlog da uzmem neki randomness test. Kako shvatih, ti testovi se opsežno koriste u i protiv kriptografije. Znaš li koliko ima smisla pokušavati išta s njima na sekvencama od po 8 degenerisanih slučajnih brojeva?
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Provjera 16.12.2003. u 09:00 - pre 246 meseci
Mislim da mi je malo jasnije šta želiš da napraviš. Evo da probam kratko objašnjenje:

Nas zanima da li je sekvenca



generisana nekim određenim izvorom (koji se karakteriše raspodelom verovatnoće da generiše određeni niz). Znači ovde nije bitno to što se računa moduo 26 niti išta s tim u vezi. Istina deo informacije se nepovratno gubi ali to je osobina svih „data processing“ zavisnosti.

Pretpostaviću da generator radi po funkciji:



gde je PRIME fiksiran i poznat, a s je nepoznati „seed“ koji generiše raspodelu. Šta je ovde slučajno? Pa, kako ne možemo znati s unapred, to je verovatnoća da se pojavi recimo ako se pojavio uslovljena izborom s. Pošto je funkcija deterministička, uslovna verovatnoća je uvek takva da je njena vrednost 1 za neki par kada fiksiramo neko s. E sad, ovu raspodelu možemo lako dobiti empirijski, tako što uzmemo algoritam generatora slučajnih brojeva iz standardne C biblioteke i zapišemo u niz tabela, za različito s, koje se sekvence javljaju. Tako dobijemo empirijsku raspodelu , a nama treba da izračunamo



Ostatak posla je mehanika koja treba da svede ovaj prethodni izraz (verovatnoću da je generisan baš dati niz) na nešto što je izraženo samo u funkciji onih empirijskih raspodela.





gde (a) dolazi kao posledica primene lančanog pravila, a (b) kao posledica toga što smo modelovali generator kao Markovljev proces, tj. trenutno stanje zavisi samo od prethodnog. Ovde naravno očekujemo da susedni slučajni brojevi nisu nezavisni, što bi trebalo da bude ispunjeno. Kada je alfabet binarni a generator pseudoslučajan sa povratnom spregom (klasičan elektroničarski pseudo-random generator) takva korelacija postoji, ali za ne-binarni alfabet ne znam tačno kako izgleda, možda može negde da se pronađe.

Ostaje nam da svedemo poslednji proizvod na empirijsku raspodelu.








c: obrnuta marginalizacija
d: Bajesovo pravilo o uslovnim verovatnoćama
e: malo gimnastike sa gornjim izrazom

Na kraju se dakle dobije verovatnoća izražena u funkciji raspodela koje se mogu empirijski oceniti, i to su sve ove uslovne raspodele u poslednjem izrazu. Mnoge od ovih stvari se mogu unapred sračunati, verujem da ti to neće biti problem.

E sad, kako izmeriti da li je to „dovoljno“ random? (randome, nisam te prozvao!:)) Ja bih ponovio istu ovu računicu, samo sa empirijskom raspodelom za neki prirodni jezik i zatim napravio log-likelihood (sad se ne sećam kako se to po naški kaže, valjda log-poverenje) meru:



što je standardan način da se uporede dve verovatnoće. Tu će se ponešto od izraza srećom skratiti pa ćeš dobiti jednostavniju formulicu za računanje. Ako log pretegne u pozitivnu stranu, onda je prva verovatnoća veća (ako uzmeš da je verovatnoća da niz pripada jednoj raspodeli, npr. raspodeli iz srpskog jezika, a verovatnoća da niz pripada drugoj raspodeli, npr. slučajnoj).

Naravno, što duži uzorak to je bolje. Ne znam koliko će ovo biti dobro za kratke sekvence. Možeš probati ono što si i sam rekao, da pronađeš empirijske raspodele za tri i(li) više znakova, koliko god je moguće. Primeti da smo u teoriji mogli izračunati i direktno empirijsku raspodelu za Y, ali da to u praksi nije moguće jer je prostor mogućih vrednosti veliki . Upravo zato smo i koristili svu ovu gimnastiku - da bismo pokušali da smanjimo posao.

f
 
Odgovor na temu

[es] :: Art of Programming :: Provjera

[ Pregleda: 2718 | Odgovora: 8 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.