Generatory liczb pseudolosowych cz.3

Przyszedł czas na kolejne generatory liczb pseudolosowych. Znowu pojawi się nieco kodu oraz ogólnego wyjaśnienia pt. “Why?” ( i odpowiedzią nie będzie “For money” ;) ).

Więc do kodu start..

Generatory liczb pseudolosowych cz.2

Jak już pisałem w pierwszej części serii o generatorach, tym razem opiszę generator liczb pseudolosowych o rozkładzie równomiernym.

Rozkład równomierny dla zmiennej losowej ciągłej na podanym przedziale [a,b] oznacza, że prawdopodobieństwo wystąpienia każdej z wartości w tym przedziale jest dokładnie takie samo i wynosi dokładnie 1/(b-a) – stąd widać, że a i b muszą być wartościami skończonymi, aby wynik był sensowny. Prawdopodobieństwo wystąpienia każdej wartości spoza przedziału wynosi 0. Analogicznie sytuacja ma się dla zmiennej losowej dyskretnej. Przykładem dla dyskretnej zmiennej losowej może być rzut monetą lub kostką sześcienną ( zakładając, że nie są w jakiś sposób zmodyfikowane ). Więcej teorii łatwo znaleźć na wikipedii – ten wpis nie ma na celu wykładu matematycznego.

Generatory liczb pseudolosowych cz.1

Czym są liczby pseudolosowe powinien każdy programista mniej więcej wiedzieć. Są to liczby, które mają rozkład mniej więcej losowy. Dlaczego nie są to liczby losowe tylko pseudolosowe? Otóż prawdziwie losowe liczby występują w zasadzie tylko w przyrodzie. Bo jak można nazwać liczby generowane za pomocą algorytmu całkowicie losowymi?

W praktyce daje nam to pewną wspaniałą własność, która może być zarówno być zarówno błogosławieństwem jak i przekleństwem. Dla mnie jest błogosławieństwem ponieważ aktualnie zajmuję się symulacją cyfrową, a tu “powtarzalność” eksperymentu jest bezcenna! Co oznacza owa “powtarzalnosć eksperymentu”? Jest to możliwość prześledzenia procesu, który symulujemy, kilka razy w _identycznych_ warunkach – jest to niemożliwe w rzeczywistości.

Postanowiłem napisać ten cykl artykułów o generatorach pseudolosowych ponieważ ich losowość polega na tym, że przechodzą testy, na zgodność z pewnym, założonym rozkładem prawdopodobieństwa. O testach tych być może również napiszę na koniec cyklu wpisów o samych generatorach różnych rozkładów.

Przy czytaniu przyda się znajomość rachunku prawdopodobieństwa. W następnej notce zacznę od rozkładu równomiernego, który stanowi podstawę dla innych rozkładów - jest więc swego rodzaju “królem”. Przykładowe implementacje będę podawał w języku C++, ale pojawią się również algorytmy więc przełożenie ich na inne języki nie powinno stanowić problemu (zwłaszcza, gdy ma się kod podglądowy).

QMC skończony

Po długiej przerwie ( którą wypełniłem pisaniem programu ) pojawia się kolejny wpis.

Wczoraj o godz. 23:46 skończyłem oficjalnie pisać QMC. Jeszcze jutro obrona tego i rozdział ten będę mógł zamknąć :)

QMC ciąg dalszy..

Zmobilizowałem się wreszcie i odpaliłem Anjutę. Otworzyłem moje pliczki z kodem implementującym algorytm minimalizacji funkcji logicznych ;)

Popatrzałem, zmodyfikowałem jedną klasę nieco dopisując kilka linijek. Również kilka linijek doszło do jednej z funkcji.

Na tym zakończyłem na dzisiaj, ale najważniejszy jest fakt, że wogóle się za to wziąłęm – powinno pójść z górki już :)

Konkursowa minimalizacja

No cóż.. na uczelni jest konkurs, ale tym się różni od innych, że jest obowiązkowy dla wszystkich studentów drugiego roku z EiT ;] – piękne prawda ?

Nie powiem, że piszę program konkursowy z niechęcią, ale fakt, że mógłbym ciekawsze rzeczy robić niż wynajdywać koło od nowa – dokształcać się albo realizować zlecenia. No ale mus to mus.

O co chodzi ? Należy zaimplementować w C++ algorytm minimalizacji funkcji logicznych metodą Quine’a-McCluskeya. Wszystko pięknie ładne poza kilkoma szkopułami. Nikt tego algorytmu nie przestawił w sposób informatyczny – pokazali nam tylko jak się to robi na kartce. No ale z tego da się sporo wywnioskować i napisać samemu ;) Kolejną rzeczą jest to, że ostatni krok w realizacji algorytmu jest problemem NP zupełnym….

Ale zabawy przy tym co nie miara :)

Szyfr Cezara czyli jak nie szyfrować.

Szyfr Cezara, stosowany prze Juliusza Cezara do szyfrowania swoich listów jest bardzo prosty, ale i przy tym w zasadzie nieskuteczny. Choć podobno Rosjanie jeszcze na początku XX wieku korzystali w wojsku z tego szyfru, ze względu na jego prostotę :)

Algorytm jest wręcz banalny, opiera się na przesunięciu o 3 każdej litery alfabetu. Gdy szyfrujemy przesuwamy “w prawo”, gdy deszyfrujemy “w lewo”. Zapis matematyczny:

1. E(p) = ( p + 3 ) mod k
2. D(p) = ( p- 3 ) mod k

Gdzie k jest ilością liter danego alfabetu a p aktualnie szyfrowaną literą. Zgodnie z oryginalnym szyfrem, nie szyfrujemy cyfr i innych znaków ( co oczywiście ułatwia deszyfrację ) . Oto kod szyfrowania w C++:

string cezarEncode( string text )
{
    const unsigned int CEZAR_SHIFT = 3;
    const unsigned int ALPHABET_SIZE = 26;
    string result = "";
    unsigned int length = text.length();
    for ( int i(0); i < length; ++i )
    {
        // 65 is ASCII code of A, 90 is ASCII code of Z
        if ( text[i] >= 65 && text[i] <= 90 )
            result += ( text[i] - 65 + CEZAR_SHIFT ) % ALPHABET_SIZE + 65;
        // 97 is ASCII code of a, 122 is ASCII code of z
        else if ( text[i] >= 97 && text[i] <= 122 )
            result += ( text[i] - 97 + CEZAR_SHIFT ) % ALPHABET_SIZE + 97;
        else
            result += text[i];
    }
    return result;
}

Deszyfrowanie:

string cezarDecode( string text )
{
       const unsigned int CEZAR_SHIFT = 3;
       const unsigned int ALPHABET_SIZE = 26;
       string result = "";
       unsigned int length = text.length();
       for ( int i(0); i <   length; ++i )
       {
           // 65 is ASCII code of A, 90 is ASCII code of Z
            if ( text[i] >= 65 && text[i] <= 90 )
                result += ( text[i] - 65 - CEZAR_SHIFT ) % ALPHABET_SIZE + 65;
            // 97 is ASCII code of a, 122 is ASCII code of z
            else if ( text[i] >= 97 && text[i] <= 122 )
                   result += ( text[i] - 97 - CEZAR_SHIFT ) % ALPHABET_SIZE + 97;
            else
                result += text[i];
       }

       return result;
}

I na tym koniec