Gra w chaos
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Fractal_fern1.jpg/180px-Fractal_fern1.jpg)
Gra w chaos – algorytm komputerowego generowania obrazów pewnych fraktali. Generuje on przybliżony obraz atraktora lub punktu stałego dowolnego systemu funkcji iterowanych.
Algorytm
Zaczynając od pewnego punktu kolejne iteracje są dane przy pomocy wzoru gdzie jest jedną z funkcji iterowanych wybieraną niezależnie i losowo dla każdej iteracji. Iteracje zbiegają się do punktu stałego systemu funkcji iterowanych. Jeżeli wartość początkowa należy do atraktora systemu funkcji iterowanych, wówczas wszystkie punkty również należą do tego atraktora i z prawdopodobieństwem 1 tworzą w nim zbiór gęsty. Prawdziwy jest znacznie ogólniejszy rezultat.
Twierdzenie o grze w chaos (zob.[1]): Niech będzie przestrzenią metryczną zupełną, zaś iterowanym układem funkcyjnym (IFS) złożonym z przekształceń zwężających Niech będzie orbitą startującą w dowolnym punkcie Wówczas atraktor układu (który istnieje w myśl twierdzenia Hutchinsona) odtwarzany jest przez zbiór punktów skupienia orbity
- (wersja probabilistyczna) z prawdopodobieństwem 1, jeśli tylko ciąg sterujący wyborem funkcji w n-tym kroku iteracji, jest losowany z użyciem schematu Bernoulliego na zbiorze
- (wersja zderandomizowana) jeśli tylko ciąg jest dyzjunktywny nad alfabetem tzn. dowolny łańcuch skończony nad pojawia się w
W przypadku układów kontrakcji wariant probabilistyczny twierdzenia o grze w chaos (używający schematu Bernoulliego) wynika z wariantu dyzjunktywnego. Dzieje się tak, gdyż schemat Bernoulliego generuje ciągi dyzjunktywne prawie na pewno.
Przykład dla trójkąta Sierpińskiego
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sierpinski1.png/220px-Sierpinski1.png)
Na początku stawia się na płaszczyźnie 3 dowolne punkty (powinny być niewspółliniowe, gdyż inaczej fraktal zdegeneruje się do odcinka), po czym wybiera sobie kolejny punkt płaszczyzny, zwany punktem gry (game point). Następnie wybiera się dowolny z trzech punktów obranych na samym początku (można je oznaczyć 1, 2 i 3, po czym korzystając z generatora liczb losowych, wybierać je) i stawia punkt w połowie odległości między czwartym punktem a tym wybranym. Powtarza się ten krok, za każdym razem oznaczając punkt leżący dokładnie w połowie odległości między ostatnio postawionym a jednym z trzech pierwszych.
Efektem algorytmu – zakładając, że punkty były losowane z mniej więcej takim samym prawdopodobieństwem – jest pewien wariant trójkąta Sierpińskiego. Jego wierzchołkami są trzy punkty wybrane na samym początku gry.