Artykuł naukowy.


Uniwersytet Technologiczno-Humanistyczny im. K. Pułaskiego w Radomiu.

Wydział Informatyki i Matematyki.

GENERATORY LICZB LOSOWYCH DLA INFORMATYKI

Ihor Ohirko, Mateusz Grundo, Rafał Leszczyński,

Probabilistyka inaczej rachunek prawdopodobieństwa to dział matematyki zajmujący się zdarzeniami jakie zachodzą, gdy przeprowadzamy doświadczenia losowe. A doświadczenie jest losowe, jeżeli można je wielokrotnie powtarzać w tych samych warunkach i wyniku doświadczenia nie potrafimy z góry przewidzieć. Przykładem takich doświadczeń jest rzut monetą, rzut kostką do gry, losowanie karty z talii kart, itp.

Pierwsze znane zagadnienia z rachunku prawdopodobieństwa dotyczyły gier hazardowych, w szczególności gry w kości. Mimo, że gra znana była już w starożytności, pierwsze teoretyczne zainteresowanie tą grą przejawiali dopiero matematycy francuscy z XVII w. Pierre de Fermat i Blaise Pascal. Podstawowymi pojęciami rachunku prawdopodobieństwa są: przestrzeń zdarzeń elementarnych, z jej elementami, doświadczenie oraz zdarzenie losowe, prawdopodobieństwo zajścia określonego zdarzenia.

Podstawowe zagadnienia występujące w kombinatoryce to:

1) Kombinacje z powtórzeniami – Mając dany zbiór n-elementowy kombinacją z powtórzeniami elementów zbioru nazywa się każdy zbiór k-wyrazowy.

Kombinacje z powtórzeniami są rozszerzeniem kombinacji bez powtórzeń o możliwość powtarzania się elementów.

Kombinacje z powtórzeniami

2) Kombinacje bez powtórzeń – Mając dany zbiór n-elementowy kombinacją bez powtórzeń elementów zbioru nazywa się każdy zbiór k-wyrazowy, którego wyrazy składają się z różnych elementów. Inaczej mówiąc kombinacją jest każdy podzbiór danego zbioru skończonego.

Kombinacje

3) Wariacje z powtórzeniami – Mając dany zbiór n-elementowy wariacją z powtórzeniami elementów zbioru nazywa się każdy ciąg k-wyrazowy, którego wyrazy składają się z różnych lub nieróżniących się elementów.

Wariacje z powtórzeniami

4) Wariacje bez powtórzeń – Mając dany zbiór n-elementowy wariacją bez powtórzeń elementów zbioru nazywa się każdy ciąg k-wyrazowy, którego wyrazy składają się z różnych elementów dla k≤ n.

Wariacje bez powtórzeń

5) Permutacje z powtórzeniami – Mając dany zbiór n-elementowy permutacją z powtórzeniami elementów zbioru nazywa się każdy ciąg n-wyrazowy, którego wyrazy występują odpowiednio n1, n2, …, nk razy.

6) Permutacje bez powtórzeń – Mając dany zbiór n-elementowy permutacją bez powtórzeń elementów zbioru nazywa się każdy ciąg n-wyrazowy, którego wyrazy składają się z różnych elementów zbioru n-elementowego jednocześnie wykorzystując je wszystkie.

Wykorzystanie liczb losowych.

Wiemy już, że istnieją losowe ciągi liczb. Powstaje pytanie: jak można je wykorzystać dla celów praktycznych? Liczby losowe przyda ją się wszędzie tam, gdzie efekt przypadkowy, losowy, jest lepszy niż działanie zdeterminowane przez człowieka, a więc obciążone jego subiektywną oceną sytuacji. Liczby losowe można wykorzystać w reprezentatywnych badaniach statystycznych (przy losowaniu próby z populacji generalnej lub, szerzej, planowaniu schematu losowania), a zatem w zagadnieniach statystycznej kontroli jakości produktów, wszelkich badaniach ekonomicznych, społecznych, marketingowych itp. W naukach eksperymentalnych liczb losowych możemy użyć w zagadnieniach planowania eksperymentu, chociażby dokonując podziału poletek doświadczalnych dla celów porównania różnych czynników w uprawach rolnych lub też wybierając do badań próbkę materiału z większej objętości.

Innym sposobem wykorzystania liczb losowych są wszelkie badania symulacyjne. Są to metody wykorzystujące techniki obliczeniowe, w których przedstawiamy przebieg realnego zjawiska, opisanego odpowiednimi równaniami, uwzględniając wpływające na nie czynniki losowe. Badania takie są często jedynym sposobem ilościowej analizy skomplikowanego procesu technologicznego lub zjawiska przyrodniczego. Podobnie, liczby losowe są źródłem losowości stwarzającej złudzenie realizmu we wszelkich popularnych grach komputerowych, inteligentnych automatach do gier zręcznościowych, trenażerach oraz profesjonalnych grach strategicznych, to znaczy w programach umożliwiających wirtualny udział gracza w operacjach wojennych, Generatory liczb losowych 3 ekonomicznych lub społecznych. Liczby losowe mogą ponadto służyć do budowania modeli skomplikowanych obiektów geometrycznych, na przykład fraktali losowych, wzorów powierzchni itp. Również badania symulacyjne statystyki matematycznej, tak zwane metody bootstrapowe lub sznurowadłowe, wymaga ją zastosowania liczb losowych.

Liczby losowe są także niezbędnym elementem metod Monte Carlo (por. [13], [68], [41]), czyli wykorzystania metod probabilistycznych w obliczeniach przeprowadzanych zwykle metodami deterministycznymi, na przykład w przybliżonym obliczaniu całek wielowymiarowych, rozwiązywaniu równań różniczkowych i algebraicznych, optymalizacji (często sprowadzającej się do szukania minimum funkcji), algorytmach genetycznych itd. Metody te mogą być, szczególnie dla zadań dotyczących nieregularnych obszarów i funkcji, bardziej efektywne od metod klasycznych.

Zastosowaniem liczb losowych, które w ostatnim czasie zyskało ogromnie na znaczeniu, jest kryptografia, czy też szerzej rozumiana ochrona informacji. Oprócz tradycyjnych zastosowań kryptografii w wojskowości i dyplomacji, w ostatnich latach powstały nowe pola jej zastosowań. Związane są one z nowymi masowymi sposobami przesyłania danych, w których niezbędna jest ochrona informacji, to znaczy z telefonią komórkową i rozległymi sieciami komputerowymi. Dziedziny te wymaga ją udostępnienia tanich i wydajnych źródeł liczb losowych (służących jako klucze w szyfrach strumieniowych), w dodatku liczb spełniających szczególne wymagania gwarantujące bezpieczeństwo szyfru. W dalszej części tej pracy postaramy się pokazać, jakie są praktyczne sposoby tworzenia ciągów liczb losowych niezbędnych w wymienionych (i niewymienionych) problemach praktycznych.

Liczby losowe w programowaniu

Generatory LCG

Do rozwiązania problemu generacji liczb pseudolosowych opracowano specjalne funkcje modularne zwane liniowymi generatorami kongruencyjnymi liczb pseudolosowych (ang. pseudorandom number linear congruential generator – w skrócie LCG) o następującej postaci:

Generatory LCG

Xn  – n-ta liczba pseudolosowa
Xn-1  – poprzednia liczba pseudolosowa
a  – mnożnik
c  – przyrost
m  – moduł

Ze wzoru wynika, iż kolejna liczba pseudolosowa Xn powstaje z poprzedniej Xn-1. Liczby te tworzą zatem ściśle określony ciąg kolejno następujących po sobie wartości.

Drugą cechą charakterystyczną jest to, iż liczba pseudolosowa Xn jest resztą z dzielenia przez moduł m. Skoro tak, to może przyjmować wartości od 0 do – 1. Z pierwszej i drugiej własności wynika, iż po mcyklach obliczeniowych, liczby pseudolosowe zaczynają się powtarzać:

X0 → X1 → X2 → …  → Xm-2  → Xm-1 → X0 → X1 → …

Jeśli współczynniki ac i m są źle dobrane, to cykl powtarzania może być krótszy niż m.

Rozróżniamy dwa podstawowe rodzaje generatorów LCG:

Addytywny LCG: Xn = (aXn-1 + cmod m
Multiplikatywny LCG:: Xn = aXn-1 mod m

Podstawowa różnica pomiędzy nimi jest taka, iż generator addytywny LCG może generować liczby pseudolosowe z zakresu od 0 do m – 1, a generator multiplikatywne generuje je z zakresu od 1 do m – 1. Poniżej podajemy prosty algorytm doboru współczynników dla generatora LCG.

Określamy zakres liczb pseudolosowych 0…Xmax (dla LCG multiplikatywnego jest to 1…Xmax). Moduł m jest zawsze o 1 większy od maksymalnej liczby w zakresie, czyli:

m = Xmax + 1

Przyrost c musi być względnie pierwszy z modułem m. Możemy m rozłożyć na czynniki pierwsze i dla c wybieramy czynniki nie występujące w m. Możemy również generować pseudolosowe c i sprawdzać, czy spełnia warunek:

NWD(c,m) = 1

Mnożnik dobieramy wykorzystując regułę, iż wyrażenie a – 1 jest podzielne przez każdy czynnik pierwszy modułu m. Jeśli moduł m dzieli się przez 4, to a – 1 również powinno być podzielne przez 4.

Przykład:

Zaprojektować addytywny generator LCG generujący liczby pseudolosowe w przedziale od 0 do 11.

Z warunków zadania mamy

Xmax = 11
m = Xmax + 1 = 11 + 1 = 12

Przyrost c musi być względnie pierwszy z m. Moduł m rozkładamy na iloczyn czynników pierwszych:

m = 2 × 2 × 3

Na przyrost c możemy wybrać dowolną liczbę nie posiadającą czynników 2 i 3. Na przykład może to być:

c = 7

Wyrażenie a – 1 musi być podzielne przez 4 i 3.

a – 1 = 4 × 3 = 12
a = 12 + 1 = 13

Otrzymujemy następujący wzór generatora LCG:    Xn = (13 × Xn-1 + 7) mod 12   → LCG(12,13,7)

Ponieważ wzór ten pozwala obliczyć kolejną liczbę pseudolosową Xn z liczby poprzedniej Xn-1, musimy określić wartość startową X0, od której rozpocznie się generacja liczb pseudolosowych. Wartość tę nazywamy ziarnem pseudolosowym (ang. pseudorandom seed). Ziarno wpływa na miejsce w pierścieniu liczb pseudolosowych, od którego rozpocznie się generacja następnych liczb.

Przyjmijmy X0 = 0 i policzmy wszystkie kolejne liczby pseudolosowe, które tworzy nasz generator LCG:

X1 = 13 ×   0 + 7 mod 12 =  7 mod 12 =  7
X2 = 13 ×  7 + 7 mod 12 =  98 mod 12 =  2
X3 = 13 ×  2 + 7 mod 12 =  33 mod 12 =  9
X4 = 13 ×  9 + 7 mod 12 =  124 mod 12 =  4
X5 = 13 ×  4 + 7 mod 12 =  59 mod 12 =  11
X6 = 13 ×  11 + 7 mod 12 =  150 mod 12 =  6
X7 = 13 ×  6 + 7 mod 12 =  85 mod 12 =  1
X8 = 13 ×  1 + 7 mod 12 =  20 mod 12 =  8
X9 = 13 ×  8 + 7 mod 12 =  111 mod 12 =  3
X10 = 13 ×  3 + 7 mod 12 =  46 mod 12 =  10
X11 = 13 ×  10 + 7 mod 12 =  137 mod 12 =  5
X12 = 13 ×  5 + 7 mod 12 =  72 mod 12 =  0
X13 = 13 ×  0 + 7 mod 12 =  7 mod 12 =  7  = X1 – ciąg zaczyna się powtarzać
X14 = 13 ×  7 + 7 mod 12 =   98 mod 12 =  2  = X2

Dla X0 = 0 otrzymaliśmy ciąg liczb pseudolosowych: 7 2 9 4 11 6 1 8 3 10 5 0 7 2 9 4 …

Jeśli przyjmiemy inną wartość za X0, to otrzymamy ten sam ciąg, lecz startujący od innego punktu:

Dla X0 = 1 mamy : 8 3 10 5 0 7 2 9 4 11 6 1 …
Dla X0 = 2 mamy : 9 4 11 6 1 8 3 10 5 0 7 2 …
Dla X0 = 3 mamy : 10 5 0 7 2 9 4 11 6 1 8 3 …

Następstwo kolejnych liczb pseudolosowych jest zawsze takie samo – np. po liczbie 3 zawsze wystąpi liczba 10.

Z powyższych rozważań można wyciągnąć wniosek, iż każdy generator LCG da się jednoznacznie scharakteryzować czwórką parametrów:

LCG(m,a,c,X0)
m – moduł
a – mnożnik
c – przyrost
X0 – ziarno

W praktycznych realizacjach dąży się do dużych okresów generatora LCG – wtedy liczby pseudolosowe powtarzają się dopiero po wielu miliardach przebiegów. Jako przykład niech posłuży poniższy generator LCG zaproponowany przez prof. D. Knutha:

LCG(34359738368, 3141592653, 2718281829, Xo)

m = 34359738368 = 235
a = [π × 109]
c = [e × 109],  e – podstawa logarytmów naturalnych, e = 2,7182818284590452353602874713527…

Generator liczb pseudolosowych w języku C++

Język C++ posiada wbudowany dobry generator liczb pseudolosowych, do którego dostęp mamy za pomocą dwóch funkcji:

rand() –  zwraca kolejną liczbę pseudolosową w zakresie od 0 do RAND_MAX. Funkcja rand() i stała RAND_MAX zdefiniowane są w pliku nagłówkowym cstdlib. Plik ten należy dołączyć do każdego programu wykorzystującego tę funkcję. Stała RAND_MAX ma wartość 32767 (lecz w innych implementacjach C++ może być większa – zawsze to sprawdzaj!).
srand(X0) –  umożliwia zainicjowanie ziarna generatora pseudolosowego. Jeśli nie zainicjujemy X0, to funkcja rand() będzie generowała zawsze ten sam ciąg liczb pseudolosowych. Ziarno inicjujemy zwykle wartością zwracaną przez funkcję time(), ponieważ wartość ta przy każdym uruchomieniu programu będzie inna i w efekcie otrzymamy inny ciąg liczb pseudolosowych. Funkcja time() wymaga dołączenia pliku nagłówkowego time.h.

Generator pseudolosowy języka C++ pozwala nam uzyskiwać wartości pseudolosowe w zakresie od 0 do 32767. Poniższy program generuje 20 pierwszych liczb pseudolosowych:

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

int main()
{
    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() << endl;

    return 0;
}

Zwróć uwagę, iż przy każdym uruchomieniu programu są to te same liczby:

   41
18467
6334
26500
19169
15724
11478
29358
26962
24464

Spowodowane jest to tym, iż ziarno generatora zawsze startuje od takiej samej wartości. Aby to zmienić, musimy je na początku programu zainicjować wartością, która będzie przy każdym uruchomieniu inna. Tutaj wykorzystujemy funkcję time(), która zwraca wartość bieżącego czasu. Istotne dla nas jest jedynie to, iż wartość ta różni się przy każdym uruchomieniu programu, gdyż czas nieubłaganie płynie do przodu. Wynik funkcji time() jest ziarnem generatora i przekazujemy go jako parametr do funkcji srand(), która ustawi to ziarno.

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    srand(time(NULL));

    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() << endl;

    return 0;
}

Teraz każde uruchomienie daje inny ciąg liczb pseudolosowych. Generator pseudolosowy należy inicjować nowym ziarnem tylko raz, na samym początku programu.

Literatura:

„Probabilistyka, Rachunek prawdopodobieństwa, statystyka matematyczna, procesy stochastyczne” – Edmund Pluciński,Agnieszka Plucińska; Wydawnictwo: WNT;

http://pasja-informatyki.pl/&#8221; – Mirosław Zelent i Damian Stelmach;

„Generatory liczb losowych: algorytmy, testowanie, zastosowanie” – Zbigniew Kotulski, Warszawa 2001

„Rachunek prawdopodobieństwa i statystyka matematyczna w zadaniach, część I, II,”-W. Krysicki i współautorzy,  Wydawnictwo Naukowe PWN, Warszawa 2004.

PROWADZĄCY: prof. Ihor Ohirko

STUDENCI III SEM.: Mateusz Grundo, Rafał Leszczyński.

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Połączenie z %s