|
|
| Line 5: |
Line 5: |
| | == Zadanie == | | == Zadanie == |
| | | | |
| - | ''Część pierwsza'': '''liniowy kongruentny generator liczb losowych''' (1 pkt.) | + | ''Część pierwsza'': '''Obliczanie liczby Pi''' (1 pkt.) |
| | | | |
| - | Należy napisać generator liczb pseudolosowych oraz zapisać wygenerowane liczby do pliku. | + | Należy napisać '''funkcję''', która oblicza liczbę π |
| - | | + | |
| - | Stworzony generator powinien opierać się na wzorze:
| + | |
| - | | + | |
| - | <code>x[j+1] = (g*x[j] + c ) mod m.</code>
| + | |
| - | | + | |
| - | Generator taki nazywamy generatorem LCG - czyli generatorem liniowym kongruentnym. Zadanie pewnej wartości poczatkowej <code>x[0]</code> definiuje nam zatem cały ciąg, który ponadto jest ciągiem okresowym. Okres zależy od doboru parametrów i przy spelnieniu kilku warunków osiąga maksymalnie wartość <code>m</code>. Warunki te to:
| + | |
| - | | + | |
| - | * <code>c</code> i <code>m</code> nie maja wspolnych dzielników,
| + | |
| - | * <code>b = g-1</code> jest wielokrotnoscia kazdej liczby pierwszej <code>p</code>, ktora jest dzielnikiem liczby <code>m</code>,
| + | |
| - | * <code>b</code> jest wielokrotnością 4 jesli <code>n</code> tez jest wielokrotnością 4.
| + | |
| - | | + | |
| - | Dla uproszczenia należy przyjąć <code>c = 0</code>, otrzymując w ten sposób multiplikatywny liniowy generator kongruentny (MLCG).
| + | |
| - | | + | |
| - | * Wartości <code>g</code> oraz <code>m</code> powinny być łatwe do modyfikacji w programie.
| + | |
| - | | + | |
| - | Efektem działania makra powinien być plik nazwa.dat zawierający ciąg wygenerowanych liczb dla zadanych parametrów. Makro należy uruchomić trzy razy, otrzymując trzy pliki: <code>losowe1.dat, losowe2.dat, losowe3.dat</code>, dla parametrów odpowiednio:
| + | |
| - | | + | |
| - | * <code>m=97</code> i <code>g=23</code>,
| + | |
| - | * <code>m=32363</code> i <code>g=157</code>,
| + | |
| - | * <code>m=147483647</code> i <code>g=16807</code>.
| + | |
| - | | + | |
| - | ''Część druga'': '''test widmowy''' (1 pkt.) | + | |
| - | | + | |
| - | Należy przeprowadzić test widmowy aby przetestować jakość generatora. By to zrobić należy narysować na płaszczyźnie punkty o współrzędnych <code>(x[n], x[n+1])</code>. Uzyskany obraz utworzy wzór przypominający widmo generatora - stąd nazwa testu.
| + | |
| - | | + | |
| - | Jeśli punkty będą rozłożone równomiernie generator można uznać za dobry. Jeśli zdecydowanie widać pewną okresowość - punkty powtarzają się wielokrotnie - generator nie działa poprawnie. Oczywiście na rozłożenie punktów wpływa jedynie dobór parametrów <code>g</code> i <code>m</code>.
| + | |
| - | | + | |
| - | * Do tworzenia wykresów widma poleca się użycie obiektów <code>TH2D</code>.
| + | |
| - | | + | |
| - | Wynikiem powinny być trzy wykresy widma.
| + | |
| - | | + | |
| - | ''Część trzecia'': '''generacja liczb losowych oparta na transformacji rozkładu jednorodnego''' (3 pkt.)
| + | |
| - | | + | |
| - | Dowolna funkcja zmiennej losowej jest zmienną losową. Powstaje więc pytanie jaka jest gęstość zmiennej losowej Y jeżeli znana jest gęstość <code>f(x)</code>. Zakładamy że prawdopodobieństwo <code>g(y)dy</code> jest równe <code>f(x)dx</code> gdzie <code>dx</code> odpowiada wartością <code>dy</code>. Warunek jest spełniony dla odpowiednio małych <code>dx</code>. Wynika stąd, że:
| + | |
| - | | + | |
| - | <code>g(y) = dx/dy f(x)</code>
| + | |
| - | | + | |
| - | Teraz jeżeli założymy, że gęstość prawdopodobieństwa <code>f(x)</code> wynosi 1 w <code>0<=x<=1</code> i <code>f(x) = 0</code> dla <code>x<= 0 i x>1</code> to powyższe równanie możemy zapisać w postaci:
| + | |
| - | | + | |
| - | <code>g(y)dy = dx = dG(y),</code>
| + | |
| - | | + | |
| - | gdzie <code>G(y)</code> jest dystrybuantą zmiennej losowej <code>Y</code>. Co po całkowaniu daje nam
| + | |
| - | | + | |
| - | <code>x = G(y) => y = G^-1(x).</code>
| + | |
| - | | + | |
| - | Jeśli zmienna losowa <code>X</code> ma rozkład jednostajny na odcinku pomiędzy 0 i 1 oraz jeśli znana jest funkcja odwrotna <code>G^-1(x)</code> to funkcja <code>g(y)</code> opisuje gęstość prawdopodobieństwa rozkładu zmiennej losowej Y.
| + | |
| - | | + | |
| - | Używając tej metody należy wygenerować 10000 liczb z rozkładu:
| + | |
| - | | + | |
| - | [[File:Lab06_wzor.png]]
| + | |
| - | | + | |
| - | Dla <code>tau = 2</code>:
| + | |
| - | | + | |
| - | * Należy wygenerować 10000 liczb z rozkładu 0 do 1 używając generatora z części pierwszej.
| + | |
| - | * Analitycznie (na kartce) policzyć dystrybuantę tego rozkładu, a następnie funkcję odwrotną. (1 pkt.)
| + | |
| - | * Wygenerować rozkład <code>f(x)</code> - wrzucając wygenerowane wartości do histogramu - korzystając z: (1 pkt.)
| + | |
| - | ** liczb wygenerowanych wcześniej i wczytanych z plików <code>losowe1.dat, losowe2.dat, losowe3.dat</code>,
| + | |
| - | ** standardowego generatora ROOT'a <code>gRandom->Rndm(1)</code>.
| + | |
| - | * Narysować na jednym wykresie histogram (odpowiednio unormowany) oraz funkcję teoretyczną <code>f(x)</code> (obiekt <code>TF1</code>). (1 pkt.)
| + | |
| - | | + | |
| - | == Uwagi ==
| + | |
| - | * Wczytywanie danych z pliku:
| + | |
| - | ifstream ifile;
| + | |
| - | ifile.open("dane.dat");
| + | |
| - | double val;
| + | |
| - | while(ifile>>val)
| + | |
| - | {
| + | |
| - | cout<<val<<endl;
| + | |
| - | }
| + | |
| - | ifile.close();
| + | |
| - | | + | |
| - | * Zapisywanie danych do pliku:
| + | |
| - | ofstream ofile;
| + | |
| - | ofile.open("dane.dat");
| + | |
| - | for(int i=0;i<N;i++)
| + | |
| - | ofile<<val<<endl;
| + | |
| - | }
| + | |
| - | ofile.close();
| + | |
| - | | + | |
| - | == Wynik ==
| + | |
| - | Przykładowy rozkład dla parametrów:
| + | |
| - | * <code>m=97, g=23</code>
| + | |
| - | [[File:lab06_n97_g23_2.png]]
| + | |
| - | * <code>m=2147483647, g=16807</code>
| + | |
| - | [[File:lab06_n2147483647_g16807_2.png]]
| + | |
| - | | + | |
| - | Przykładowy wynik transformacji rozkładu jednorodnego:
| + | |
| - | | + | |
| - | | + | |
| - | [[File:lab06_b_2.png]]
| + | |
