Przesunięcie (OpenOffice)

Poprzednio pisałem o funkcji ADR.POŚR(), która umożliwiała mi parametryzację zakresów. Jak już wspomniałem ostatnim razem, to samo umożliwia funkcja PRZESUNIĘCIE(), jednak robi to w o wiele prostszy sposób. Składnia dla tej funkcji wygląda następująco:

PRZESUNIĘCIE( Odwołanie; Wiersze; Kolumny; Wysokość; Szerokość )

Funkcja zwraca zakres (może być to obszar dwuwymiarowy lub jednowymiarowy, albo po prostu pojedyncza komórka).

• Odwołanie - to adres komórki, względem której będziemy podawać zakres. Jeśli jako odwołanie podamy zakres, wtedy:
  a) jeśli nie podamy Wysokości ani Szerokości, funkcja zwraca zakres o tym samym rozmiarze ale którego początek będzie przesunięty o zadaną ilość Wierszy i Kolumn;
  b) jeśli podamy Szerokość i Wysokość, funkcja zwróci zakres o zadanym rozmiarze obliczony względem lewego-górnego rogu zadanego zakresu
• Wiersze; Kolumny - to względny adres lewego-górnego rogu zakresu;
• Wysokość; Szerokość – to rozmiar zwracanego zakresu (Opcjonalny. Jeśli nie podamy żadnej wartości, rozmiar zakresu się nie zmieni - tj. dla pojedynczej komórki wyniesie on 1).

Ilustracja działania funkcji PRZESUNIĘCIE().
Wykonane przeze mnie za pomocą programów OpenOffice oraz GIMP.

Jak łatwo można się domyśleć, obliczony zakres musi zawierać się w arkuszu kalkulacyjnym (tj. lewy-górny róg nie może mieć współrzędnych mniejszych niż 1).

Adres pośredni (OpenOffice)

Czasem, gdy bawię się różnymi statystykami, chciałbym zmienić przykładowo zakres danych, z których obliczana jest średnia. Nie jest to jakiś wielki problem, ale gdy odpowiednich formuł jest więcej sprawa staje się trochę pracochłonna. Przydałaby się wtedy możliwość jakiejś parametryzacji przekazywanych do funkcji adresów.

Niestety z tego co mi wiadomo, OpenOffice nie przewiduje takiej możliwości – nie bezpośrednio w każdym bądź razie. Na szczęście posiada on bardzo przydatną funkcję:

ADR.POŚR( Odwołanie )

Funkcja ta posiada jeszcze jeden parametr, jest on jednak opcjonalny i jest całkowicie nieistotny.

Funkcja jest bardzo prosta w użyciu: jako odwołanie podajemy jej po prostu ciąg tekstowy który jest adresem komórki. Zwracany jest adres komórki. Przykład:

ADR.POŚR(”A1”)

Funkcja zwróci adres A1. Jeśli wpiszemy ją bezpośrednio w komórkę, to tak jakbyśmy wpisali '=A1' czyli w tym przypadku rezultat będzie zawartością komórki A1 (np. jakąś liczbą).

Generator liczb losowych: rozkład Poissona

Niedawno pisałem o rzeczywistym przykładzie rozkładu Poissona. Dzisiaj chciałbym napisać o tym, w jaki sposób generować programowo liczby losowe o takim rozkładzie.

Na matematyce nie znam się zbyt dobrze, a na kombinatoryce i prawdopodobieństwie prawie w ogóle(*) - z tego powodu nie byłem w stanie wymyślić odpowiedniego algorytmu samemu. Postanowiłem więc poszukać odpowiedniego w internecie. Ale szczerze mówiąc nawet gdybym był w stanie coś samemu wymyślić i tak szukałbym gotowego rozwiązania, ponieważ zdolność do szukania gotowych rozwiązań to jedna z cnót programisty (mówię poważnie).

(*) - Ostatnio jednak poczytałem co nieco o tym rozkładzie i to, co zrozumiałem chciałbym przedstawić kiedyś indziej.

Ten artykuł nie będzie więc zbyt twórczy, ale to nawet lepiej . Przedstawię tu tylko gotowe implementacje w Javie kilku funkcji, które znalazłem na stronie Wikipedii.

Własne funkcje w Open Office Calc

W arkuszu kalkulacyjnym OpenOffice Calc używa się często funkcji typu SUMA().

Okazuje się, że można w prosty sposób napisać sobie własne funkcje, jeśli uważamy, że wykonanie pewnych obliczeń za pomocą standardowych funkcji będzie zbyt skomplikowane.

Value Noise

Spis treści

• Losowanie wartości
  • Tablice permutacji
• Interpolacja
  • Interpolacja liniowa
  • Interpolacja cosinusami
  • Interpolacja wielomianami
  • Interpolacja sześcienna
  • Interpolacja w wielu wymiarach
• Sumowanie szumu

Value Noise(*) to najprostszy rodzaj szumu(**), który można wykorzystać jako podstawę do generowania różnego rodzaju zjawisk/obiektów (krajobrazy, tekstury, chmury, maski obrazów itp).

(*) - Nie znalazłem polskiego terminu, a nie wiem, jak to przetłumaczyć, żeby jakoś porządnie brzmiało (szum wartości? - nie za bardzo).

(**) - Chodzi o szum gładki - tj. taki, w którym wartości pomiędzy kolejnymi punktami zmieniają się w sposób ciągły.

Najprościej mówiąc - generowanie Value Noise polega na przypisaniu pewnym punktom w przestrzeni losowych wartości, a następnie na interpolacji tych wartości dla punktów znajdujących się pomiędzy nimi.

Ilustracja generowania Value Noise. Punkty rozmieszczone w regularnych odstępach x o losowych wartościach y. Wartości punktów pomiędzy nimi są obliczane za pomocą interpolacji.

Obsługa plików w Javie

Obsługa plików w Javie jest wg. mnie rozwiązana trochę dziwnie. Ale ja programowałem głównie w C++ (w innych językach również, ale bez grzebania się w plikach), więc może się czepiam.

Tak czy siak, muszę się tego nauczyć i zanim wejdzie mi to w krew, postanowiłem sobie to zapisać.

Po pierwsze, z jakiegoś jeszcze dla mnie niejasnego powodu, operacje na plikach muszą zawierać się w bloku try-catch:

try {
    //operacje na plikach
}
//można użyć bardziej specyficznego kodu
//w szczególności przechwytywać konkretne wyjątki
//to jest tylko tak orientacyjnie
catch(Exception e) {
    e.printStackTrace();
}

Następnie musimy otworzyć jakiś plik. Ogólna rada jest taka:

FileReader / FileWriter - dla plików tekstowych

FileInputStream / FileOutputStream - dla innych (binarnych, z niestandardowym kodowaniem...)

Generator liczb losowych: losowanie z przetasowaniem

Niezależnie od tego, jak dobrego generatora liczb pseudolosowych używamy, zawsze chcielibyśmy, aby te liczby były jeszcze bardziej losowe.

Czytając kiedyś książkę o sieciach neuronowych natknąłem się na modyfikację standardowego generatora, która używała dodatkowej tablicy, w której przechowywane były kolejne wyniki ze standardowego generatora i z której pobierane były „losowo” wyniki owego ulepszonego generatora.

W tekście nie wyjaśniono dlaczego tak, a nie inaczej, ale dano wskazówkę, gdzie szukać. W „The Art of Computer Programming” Donalda Knutha (cz. 2) można znaleźć algorytm, który w teorii powinien polepszać losowość praktycznie rzecz biorąc dowolnego generatora liczb pseudolosowych (nawet takiego niezbyt dobrego).

Polega on na tym, że otrzymane z generatora liczby wrzuca się do tablicy o dowolnej wielkości (*), po czym się te liczby tasuje - z tym że oczywiście można to tasowanie przeprowadzać na bieżąco (por. losowanie z koszyka).

(*) - Na ogół dla wygody przyjmuje się wielkość około 100, we wspomnianej książce o sieciach neuronowych autor przyjął wielkość 97.

Opis algorytmu wygląda tak:

1. Wypełnij tablicę V[] o rozmiarze k kolejnymi liczbami pseudolosowymi.
2. Przypisz do zmiennej Y kolejną wylosowaną liczbę.
3. Wylosuj indeks j w tablicy V[]: j=k*Y/m; gdzie m - moduł w generatorze liczb pseudolosowych (maksymalna możliwa do wylosowania liczba + 1).
4. Wyciągnij z tablicy V[] element na pozycji j i przypisz do zmiennej Y: Y=V[j];
5. Wstaw na miejsce wyciągniętego elementu V[j] nową liczbę losową.
6. Zwróć liczbę losową ze zmiennej Y.

Generator liczb losowych: losowanie z koszyka

Zwykła funkcja losująca (random()) zwraca liczby, które są (w teorii) niezależne od tego, co wylosowało się wcześniej. Oznacza to, że czasem możemy otrzymać długie serie tych samych liczb, co często jest niepożądane. Stosuje się różne techniki, aby temu zapobiegać.

Jedną z najprostszych jest losowanie „z koszyka” - losujemy liczbę z pewnego zestawu, wyciągamy ją z tego zestawu i odkładamy na bok. Gdy zestaw zrobi się pusty, wkładamy z powrotem wszystkie liczby do zestawu i powtarzamy całą procedurę od nowa. Przypomina to trochę wyciąganie kul / kartek z numerami z koszyka / urny itp.

W praktyce nie musimy oczywiście implementować tego dokładnie w taki sposób. Przestawiona niżej funkcja losuje liczbę z tablicy z zadanymi wartościami, zmniejszając za każdym razem zakres losowania i wyrzucając wylosowaną liczbę poza ten zakres.

//Jakiś zestaw liczb, może być wpisany na sztywno
//albo generowany w programie.
int zestawLiczb[iloscLiczb];

//Zakres bieżącego losowania.
//Początkowo losujemy z całego zestawu.
int zakresLosowania=iloscLiczb;

int losujLiczbe(void)
{
  int i, x;

  //losujemy liczbę z zakresu losowania, zmniejszając zakres
  i=random(zakresLosowania);
  zakresLosowania--;
  x=zestawLiczb[i];

  //wyrzucamy wylosowaną liczbę poza nowy zakres losowania
  //zamieniając ją z (pierwszą) liczbą spoza tamtego zakresu
  zestawLiczb[i]=zestawLiczb[zakresLosowania];
  zestawLiczb[zakresLosowania]=x;
  if(zakresLosowania==0) zakresLosowania=iloscLiczb;

  //zwacamy wylosowaną liczbę
  return x;
}

Tego typu losowanie przydaje się na przykład w grach. Szczerze mówiąc na algorytm ten natrafiłem, gdy szukałem informacji na temat Tetrisa, który w taki właśnie sposób generuje nowe klocki.

W serii TGM zastosowano metodę generowania „przyjaznych” sekwencji klocków polegającą na tym, że przechowuje się w historii 4 ostatnio wylosowane klocki. Program następnie losuje klocek tak długo, aż trafi na jakiś spoza historii (losuje z trzech pozostałych).

Generator liczb losowych: rozkład dyskretny

Spis treści

• Podejście naiwne
• Opis metody
  • Budowa tablicy
  • Losowanie
• Implementacja
  • Wersja zmiennoprzecinkowa
  • Wersja całkowitoliczbowa
  • Wersja bez listy Small i Large
• Końcowe uwagi

Jeśli ktoś grał przykładowo w Diablo (lub inne gry), to być może spotkał się z tabelkami opisującymi z jakim prawdopodobieństwem wypadnie dany przedmiot. Ja sam bawiłem się kiedyś pisaniem gierek (nawet napisałem taką jedną gierkę RPG (totalnie biedna) - ale to inna historia) i spotkałem się z tym właśnie problemem - w jaki sposób skutecznie losować jakąś liczbę(*) z zadanym prawdopodobieństwem?

(*) - Wszystko w informatyce można sprowadzić do liczb. W tym przypadku - indeks w tablicy z przedmiotami.

Podejście naiwne jest takie, żeby wypisać w tabeli względne częstości każdej rzeczy, następnie wylosować jakąś liczbę (z zakresu od 0 do suma_częstości-1) i odejmować każde z tych prawdopodobieństw aż liczba zrobi się mniejsza od 0. Wtedy dana rzecz zostaje wylosowana.

Można tę metodę zaimplementować niejako w drugą stronę: tabelę z częstościami przekształcić w taki sposób, aby dla każdej rzeczy zsumować jej częstość z częstościami wszystkich poprzednich rzeczy. Następnie wylosować jakąś liczbę i porównywać po kolei z sumowanymi częstościami - jeśli liczba zrobi się większa lub równa danej sumie, losujemy poprzednią rzecz.

Podejście naiwne

[spis treści]

int n; //dana ilość rzeczy
int prob[n]; //dana tablica ze względnymi częstościami
int losuj[n]; //tworzona tablica z sumowanymi częstościami

//inicjacja tablicy losującej
void inicjuj()
{
  int i;
  
  for(i=1; i<n; ++i) losuj[i]=prob[i-1]+prob[i];
}

//funkcja losująca
int losuj_pozycje()
{
  int i, p;
  
  p=random(losuj[n-1]);
  for(i=0; losuj[i]<p; ++i);
  return i;
}

Podejście naiwne jest bardzo łatwe do zrealizowania, ale jest też wolne - ma złożoność liniową. Dla dużej ilości pozycji i dla dużej ilości losowań spowolnienie wykonywania programu może być zauważalne.

Niedawno jednak natrafiłem na algorytm, który po zbudowaniu (dosyć szybkim) tabeli losującej pozwala na losowanie danej pozycji ze złożonością O(1) - innymi słowy jest tak szybkie, jak zwykłe losowanie. Jako ciekawostkę powiem, że na ten algorytm natrafiłem w artykule dotyczącym ... genetyki. Jak widać informatyka nie znajduje zastosowania tylko w grach .

Algorytm ten nazywa się „Metoda Aliasów Vosego” i należy do rodziny metod aliasów pozwalających szybko losować wg. dyskretnego rozkładu prawdopodobieństwa (inaczej mówiąc - wg. zadanego dla każdego elementu prawdopodobieństwa).

Generator liczb losowych: losowanie sukcesu z zadanym prawdopodobieństwem

Czasem w programie czy grze musimy wybrać jakąś akcję z pewnym prawdopodobieństwem. W grach planszowych (lub innych nie-komputerowych) stosuje się często tzw. kostki procentowe(*). Ogólnie takie losowanie można przyrównać do rzutu oszukaną monetą - gdzie prawdopodobieństwo sukcesu jest różne od 50%.

(*) - Najczęściej stosuje się kombinację dwóch kostek 10-ściennych. Prawdziwe kostki 100-ścienne są nieporęczne.

W programie jednak prawdopodobieństwo nie musi być zadane procentami - może być to liczba rzeczywista z zakresu [0; 1], albo liczba całkowita określająca względną częstość (w przypadku procentów - prawdopodobieństwo w procentach względem 100%).

Napisanie odpowiedniego kodu nie powinno przedstawiać żadnych trudności przeciętnemu programiście. Trzeba tylko pamiętać o użyciu odpowiedniego operatora porównującego:

int max; //maksymalna częstość (100 dla procentów)
int p; //zadane prawdopodobieństwo (jako względna częstość)
if(random(max)<p) return 1;
else return 0;

lub, jeśli prawdopodobieństwa są liczbami rzeczywistymi z zakresu [0; 1]

float p; //zadane prawdopodobieństwo
if(random()<p) return 1; //random zwraca tu liczbę z zakresu [0; 1)
else return 0;

Jak widać, użyłem operatora '<'. To ważne - gdyby użyć operatora '<=' (lub skonstruować inny, równoważny temu kod), taka funkcja zwracałaby sukces z trochę większym niż zadane prawdopodobieństwem. Tego rodzaju błąd (pomyłka o 1) ma chyba nawet swoją nazwę - kiedyś widziałem, niestety nie pamiętam już teraz, jak coś takiego mogło się nazywać. Jeśli ktoś ma kłopoty, jakiego porównania użyć, to mogę doradzić, aby poeksperymentował z małymi liczbami - ja tak zawsze robię, jeśli mam jakieś wątpliwości.

Generator liczb losowych: rozkład Gaussa

Nie będę tu opisywał co to takiego generator liczb losowych. Zamierzam jedynie pokazać pewne jego praktyczne modyfikacje. W tym artykule chciałbym pokazać, jak generować liczbę losową o rozkładzie przypominającym rozkład Gaussa.

Idea nie jest skomplikowana. Jeśli ktoś kiedykolwiek bawił się w rzucanie kostkami (chociażby na lekcjach matematyki - pamiętam, że kiedyś w podstawówce robiliśmy coś takiego) to mógł zauważyć, że sumy oczek nie wypadają z jednakowym prawdopodobieństwem.

Słowo uzupełnienia. Okazuje się, że fakt, iż sumy oczek trzech lub więcej kostek przypominają rozkład normalny to nie przypadek. Z Wikipedii: "Jeśli jakaś wielkość jest sumą lub średnią bardzo wielu drobnych losowych czynników, to niezależnie od rozkładu każdego z tych czynników, jej rozkład będzie zbliżony do normalnego, stąd można go bardzo często zaobserwować w danych."

Spis treści w OpenOffice Writer

Niby wiem, jak to zrobić, ale cały czas muszę sprawdzać w internecie, dlatego postanowiłem to sobie tu zapisać.

MathML

Uwaga - ten artykuł stanowić ma swego rodzaju "ściągawkę" - dlatego będzie co jakiś czas uzupełniany.

Prędzej czy później każdego spotka problem, w jaki sposób napisać wzór matematyczny w jakimś dokumencie (*). Nowoczesne pakiety biurowe (ja używam OpenOffice) mają edytory formuł. Ale do publikacji na stronach trzeba używać czegoś innego. Można wstawić obrazek stworzony różnymi technikami (np. jako screenshot z takiego edytora). Zauważyłem, że niektórzy tworzą takie obrazki LaTeXem. Może i jest to łatwe, ale jak dla mnie za dużo zabawy + wgrywania masy drobnych obrazków (nie mówiąc o tym, że zdążyłem już sporo zapomnieć). Ale na szczęście jest coś takiego jak MathML. Jest to - w dużym skrócie mówiąc - taki HTML do pisania formuł matematycznych.

(*) - No dobra, nie każdego .

MathML istnieje w dwóch odmianach - Presentation Markup i Content Markup. Obydwa są wymienne i można je nawet kombinować. Różnica jest taka, że przy pomocy Presentation Markup mamy większą kontrolę nad wyglądem formuły, a dzięki Content Markup mamy większą kontrolę nad "działaniem" formuły. Ja zamierzam korzystać z Presentation Markup i tę odmianę MathML chcę w dużym uproszczeniu tu opisać. Jeśli ktoś jest zainteresowany tematem bardziej, niech odwiedzi stronę W3C.org - MathML.