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

Generisanje raspodela

[es] :: Art of Programming :: Generisanje raspodela

Strane: 1 2

[ Pregleda: 6930 | Odgovora: 27 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

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 Generisanje raspodela27.01.2004. u 16:27 - pre 206 meseci
Upravo mi je zatrebalo, pa ko velim da podelim s vama...

Napisati algoritam koji generiše slučajni vektor uniformno raspodeljen u
krugu poluprečnika 1. Hint: u pitanju je algoritam, vreme izvršavanja
mora biti predvidivo dugo.

f
 
Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
195.252.85.*

ICQ: 282954730
Sajt: www.sietf.org


+7 Profil

icon Re: Generisanje raspodela27.01.2004. u 17:50 - pre 206 meseci
Možeš li malo da pojasniš ? Verovatno ne razumem zadatak, ali čemu algoritam kada se ova raspodela računa lako iz formule slučajne promenljive neprekidnog tipa?
ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪
 
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: Generisanje raspodela27.01.2004. u 22:00 - pre 206 meseci
Citat:
kada se ova raspodela računa lako iz formule slučajne promenljive


Nisam rekao da je teško izračunati, već da mi je zatrebalo i da sam primetio da ovde odavno (ako uopšte!) nije bilo reči o generisanju raznih raspodela, pa sam samo isporučio pitanje. Ne može da šteti, a ako ne šteti, onda možda koristi.

Da pojasnim. Potreban je program koji generiše slučajni vektor (X,Y) čija je raspodela uniformna na krugu poluprečnika 1. Pritom su X i Y promenljive koje označavaju koordinate slučajno izabrane tačke u Dekartovom pravouglom koordinatnom sistemu.

f


 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.vdial.verat.net

Sajt: localhost


+4 Profil

icon Re: Generisanje raspodela28.01.2004. u 05:34 - pre 206 meseci
ili ja ne razumem postavku, ili se ovo svodi na slučajno generisanje ugla vektora (između 0 i 2pi) i inteziteta (između 0 i 1) i računanje njegovih kordinata pomoću arctg-a.

koje je od ta dva? ;)


(ovo sve naravno pod pretpostavkom da nam je već na raspolaganju Rand() funkcija koja nam vraća slučajne realne brojeve uniformno raspoređene između 0 i 1 -- ili bar dovoljno dobra aproksimacija iste ;)

 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Generisanje raspodela28.01.2004. u 06:02 - pre 206 meseci
Ali pretpostavi da nemas Rand() funkciju. Mislim da je na to mislio Filip. Filipe, ispravi me ako gresim. Ja imam nekoliko ideja ali necu da trcim pred rudu jer ne znam tacno sta se trazi u zadatku.
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.vdial.verat.net

Sajt: localhost


+4 Profil

icon Re: Generisanje raspodela28.01.2004. u 06:16 - pre 206 meseci
pa tek pod tom pretpostavkom nisam siguran da razumem postavku zadatka.

generisanje (pseudo)slučajnih (realnih) brojeva sa uniformnom raspodelom je poznat problem za koji je razrađeno već nekoliko (manje ili više) dovoljno dobrih rešenja, pa je na tu temu malo glupo raspravljati, osim ako se neko nije specifično bavio izučavanjem i istraživanjem u toj oblasti.

a ako je to poJenta cele priče, zar ne bi filip onda jednostavno rekao "hajde da raspravljamo o generisanju slučajnih brojeva", umesto što je priču zavio u problem sa vektorima (koji se lako svodi na to).

 
Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.attbi.cable.earthlink.net



+18 Profil

icon Re: Generisanje raspodela28.01.2004. u 06:52 - pre 206 meseci
Citat:
-zombie-:
ili ja ne razumem postavku, ili se ovo svodi na slučajno generisanje ugla vektora (između 0 i 2pi) i inteziteta (između 0 i 1) i računanje njegovih kordinata pomoću arctg-a.
Hm, to nece raditi - raspodela je neuniformna, ima suvise tacaka blizu 0,0.
Brute force resenje koje je mozda dovoljno dobro da se izgenerisu dve koordinate u opsegu (-1,1) i ukoliko padaju van kruga (x*x+y*y>1) da se ponovi postupak.
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.bankmeridian.com

Sajt: www.novikorisnik.net


+5 Profil

icon Re: Generisanje raspodela28.01.2004. u 07:35 - pre 206 meseci
Citat:
Reljam:
...raspodela je neuniformna, ima suvise tacaka blizu 0,0.

Kakva je raspodela ako se korenuje dobijena vrednost intenziteta vektora?

 
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: Generisanje raspodela28.01.2004. u 08:51 - pre 206 meseci
Citat:
(ovo sve naravno pod pretpostavkom da nam je već na raspolaganju Rand() funkcija koja nam vraća slučajne realne brojeve uniformno raspoređene


Pretpostavi najpre da ti je data funkcija Rand() koja vraća pseudoslučajne brojeve sa uniformnom raspodelom na [0,1].

A kad to središ, pretpostavi da ti je data samo funkcija GausRand() koja vraća slučajnu promenljivu koja je raspodeljena prema standardnoj normalnoj raspodeli .

f




[Ovu poruku je menjao filmil dana 28.01.2004. u 11:05 GMT]
 
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: Generisanje raspodela28.01.2004. u 08:55 - pre 206 meseci
Citat:
Brute force resenje koje je mozda dovoljno dobro da se izgenerisu
dve koordinate u opsegu (-1,1)


Upravo sam zato rekao da se traži algoritam, što znači da mora
imati predvidljivo vreme izvršavanja. U ovom slučaju je vreme
izvršavanja slučajna promenljiva sa geometrijskom raspodelom ako se
generisanje broja uzme za jediničnu operaciju, jer se eksperiment
ponavlja sve do prvog uspeha.

f
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Generisanje raspodela28.01.2004. u 09:41 - pre 206 meseci
Citat:
Reljam:
Citat:
-zombie-:
ili ja ne razumem postavku, ili se ovo svodi na slučajno generisanje ugla vektora (između 0 i 2pi) i inteziteta (između 0 i 1) i računanje njegovih kordinata pomoću arctg-a.
Hm, to nece raditi - raspodela je neuniformna, ima suvise tacaka blizu 0,0.

Reljam, mislim da si malo vise razmiljao prakticno nego sto treba jer si u D3D vodama pa si onda gledao da taj vektor pretstavis sa x i y gde su x i y celi brojevi jer pretstavljaju pixele. Ali filmil to nigde nije pomenuo pa onda x i y isto mogu a budu float a onda ima maltene isto tacaka oko (0,0) kao i oko (0.1,0.1) jer broj tacaka zavisi od broja znacajnih cifara.
Ako imamo funkciju Rand() onda bih i ja uradio kao zombie. Filmile?

[Ovu poruku je menjao srki dana 28.01.2004. u 23:48 GMT]
 
Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.attbi.cable.earthlink.net



+18 Profil

icon Re: Generisanje raspodela28.01.2004. u 09:42 - pre 206 meseci
Pa i ima predvidivu duzinu izvrsavanja - naci ce uspesnu tacku u 3.14 / 4 slucaja, sto je 0.785. Prvi uspeh ce biti posle 1.27 pokusaja, sto je dovoljno dobro. Vrlo je verovatno da ce neki pametniji algoritam duze da se izvrsava od ovoga - jednostavnost ima svojih vrlina :).
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Generisanje raspodela28.01.2004. u 09:50 - pre 206 meseci
Ali problem sa tim je sto to nije uniformna raspodela vektora. U stvari mozda i jeste ali problem je u tome kako je definisan vektor. Da li preko duzine i ugla ili preko dve tacke.
 
Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.attbi.cable.earthlink.net



+18 Profil

icon Re: Generisanje raspodela28.01.2004. u 09:58 - pre 206 meseci
Raspodela je uniformna koliko i generator koji se koristi, a svejedno je kako se vektor definise - uvek mozes da prebacis iz jednog sistema u drugi.

A da odgovorim na tvoju poruku od malopre: ako koristis zombijev metod (ugao=rand, r=rand), bez obzira da li su brojevi fp ili int, imaces vise tacka oko 0. Ako bi nacrtao te tacke, dobio bi koncentricne krugove i radijalne linije. Broj jednih i drugih zavisi od broja bitova u slucajnom broju.

Ako koristis moju metodu (x=rand(-1,1), y=rand(-1,1), provera), dobices resetku cija gustina zavisi od broja bitova u slucajnom broju ali ce raspodela biti uniformna. Zbog toga i mislim da je to bolje resenje.
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Generisanje raspodela28.01.2004. u 10:12 - pre 206 meseci
Citat:

Upravo sam zato rekao da se tra�i /algoritam/, �to zna�i da mora
imati predvidljivo vreme izvr�avanja. U ovom slu�aju je vreme
izvr�avanja slu�ajna promenljiva sa geometrijskom raspodelom ako se
generisanje broja uzme za jedini�nu operaciju, jer se eksperiment
ponavlja sve do prvog uspeha.


Hmm, možda može da se nađe neko "mapiranje" ostatka kvadrata na krug, to
jest da se umesto ponovnog generisanja izvrši neka funkcija nad koordinatama
koje ispadaju tako da upadnu, naravno uniformno?

A, ako i ne može da se nađe takva funkcija, možda možeš da dobiješ dovoljno dobar kompromis tako što ponavljaš generisanje maksimalno n puta (umesto beskonačno), a ako ni posle n-tog puta ne dobiješ tačku koja upada u krug, uradiš neko neuniformno mapiranje. Programersko rešenje.


[Ovu poruku je menjao jablan dana 28.01.2004. u 12:20 GMT]
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Generisanje raspodela28.01.2004. u 10:18 - pre 206 meseci
Citat:
Reljam:
Raspodela je uniformna koliko i generator koji se koristi, a svejedno je kako se vektor definise - uvek mozes da prebacis iz jednog sistema u drugi.

Nije svejedno. Ako definises vektor kao sto si ti definisao tako ces imati manje vektora ciji je vrh udaljen 0,5 ili manje od koordinatnog pocetka nego vektora ciji je vrh udaljen 0,5 i vise od koordinatnog pocetka. Znaci bitno je kako se bira vektor.
 
Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.attbi.cable.earthlink.net



+18 Profil

icon Re: Generisanje raspodela28.01.2004. u 17:14 - pre 206 meseci
Srki, nisam te najbolje shvatio, da li mozes da razjasnis to sto si rekao? Stvarno mi se cini da bi na ovaj nacin raspodela bila uniformna, ali mozda gresim, zato molim te kazi na sta mislis.
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.vdial.verat.net

Sajt: localhost


+4 Profil

icon Re: Generisanje raspodela28.01.2004. u 20:12 - pre 206 meseci
hehe.. ipak ispade zanimljiv problemčić ;)

relja me je dobro ispravio, mada.. ja sam oko rešenja očigledno razmišljao više kao matematičar nego kao programer (što mi se nije odaavno desilo -- ja sam ipak primarno programer ;), pa sam zato dao ono rešenje. ono naime jeste matematički tačno. tj može se dokazati da u krugu postoji jednak broj tačaka čije je rastojanje do centra kruga manje od polovine poluprečnika, sa onima čije je rastojanje veće od te vrednosti.. :-P

(ako vas zanima ovaj paradox, pogledajte skorašnju raspravu u forumu matematika, valjda pod nazivom "još (malo) verovatnoće" ;)


no, ako razmislim kao praktičan programer znam da mi nemamo dovoljno dobru aproximaciju neprekidnog skupa realnih brojeva, pa ovakve pretpostavke otpadaju.

zato mi sad pade na pamet ovakvo rešenje: x dodelimo vrednost slučajno izabranog broja iz skupa [0, 1], a y vrednost kvadratnog korena slučajno izabranog broja iz skupa [0, 1-x2]. nisam sto posto siguran u ovo, tako da ću kasnije razmisliti još malo, da to i dokažem (ili opovrgnem), ali imam osećaj da rešenje nije loše.. ;)


(a možda bolja varijacija na ovo poslednje, da i x dodelimo vrednost kvadratnog korena broja slučajno izabranog iz skupa [0, 1]?)
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
..-chandran.sbs.auckland.ac.nz



+3 Profil

icon Re: Generisanje raspodela28.01.2004. u 21:48 - pre 206 meseci
Problem je sto funkcija Rand() ne vraca uniformnu raspodelu nad diskretnim skupom nego racuna tako kao da je skup od 0 do 1 neprekidan jer bi inace vracala mnogo vise brojeva oko 0,0. Zato ne znam tacno na kakvu se unoformu raspodelu misli. Da li nad diskretnim skupom realnih brojeva ili neprekidnim?
 
Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
195.252.85.*

ICQ: 282954730
Sajt: www.sietf.org


+7 Profil

icon Re: Generisanje raspodela29.01.2004. u 00:37 - pre 206 meseci
Zar se onda ovo ne svodi na generisanje slučajnog broja između i , jer ovo možemo formulisati kao nalaženje realnog broja koji je u stvari tangens ugla izmedju vektora i x-ose
Citat:
Da li nad diskretnim skupom realnih brojeva ili neprekidnim

Koliko ja znam, kompjuterski je nemoguće napraviti model skupa neprekidnih realnih brojeva, tako da bismo morali da se zadovoljimo nekim diskretnim skupom.

Citat:
može se dokazati da u krugu postoji jednak broj tačaka čije je rastojanje do centra kruga manje od polovine poluprečnika, sa onima čije je rastojanje veće od te vrednosti

Pa da. I jednih i drugih ima beskonačno mnogo. :) Ne znam zašto od polovine poluprečnika. Može i od 1/10 :)
ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪
 
Odgovor na temu

[es] :: Art of Programming :: Generisanje raspodela

Strane: 1 2

[ Pregleda: 6930 | Odgovora: 27 ] > FB > Twit

Postavi temu Odgovori

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