Gra w chaos: Różnice pomiędzy wersjami

Dodane 3 bajty ,  2 lata temu
m
[wersja przejrzana][wersja przejrzana]
(→‎Algorytm: Sformułowanie Twierdzenia, źródła/przypisy, wikizacja)
m (WP:SK+Bn)
[[Plik:Fractal fern1.jpg|thumb|180px|Liść paproci wygenerowany przy pomocy gry w chaos]]
'''Gra w chaos''' to [[algorytm]] [[komputer]]owego generowania obrazów pewnych [[fraktal]]i. Generuje on przybliżony obraz [[atraktor]]a lub [[Punkt stały|punktu stałego]] dowolnego [[IFS (geometria fraktalna)|systemu funkcji iterowanych]].
 
== Algorytm ==
Zaczynając od pewnego [[punkt (geometria)|punktu]] <math>x_0,</math> kolejne [[iteracja|iteracje]] są dane przy pomocy wzoru <math>x_{n+1} = f_i(x_n),</math> gdzie <math>f_i(x)</math> jest jedną z [[funkcja|funkcji]] iterowanych, wybieraną [[zależność zmiennych losowych|niezależnie]] i [[zmienna losowa|losowo]] dla każdej iteracji. Iteracje zbiegają się do punktu stałego systemu funkcji iterowanych. Jeżeli wartość początkowa <math>x_0</math> należy do atraktora systemu funkcji iterowanych, wówczas wszystkie punkty <math>x_n</math> również należą do tego atraktora i z [[prawdopodobieństwo|prawdopodobieństwem]] 1 tworzą w nim [[zbiór gęsty]]. Prawdziwy jest znacznie ogólniejszy rezultat.
 
''Twierdzenie'' o grze w chaos (zob. <ref>{{Cytuj |autor = Michael Barnsley, Andrew Vince |tytuł = Developments in fractal geometry |czasopismo = Bulletin of Mathematical Sciences |data = 2013-08 |data dostępu = 2020-03-25 |issn = 1664-3607 |wolumin = 3 |numer = 2 |s = 299–348 |doi = 10.1007/s13373-013-0041-3 |url = http://link.springer.com/10.1007/s13373-013-0041-3 |język = en}}</ref>): Niech <math>X</math> będzie [[Przestrzeń metryczna|przestrzenią metryczną]] [[Przestrzeń zupełna|zupełną]], zaś <math>\mathcal{F} = \{f_i\}_{i=1}^{m}</math> iterowanym układem funkcyjnym ([[IFS_IFS (geometria_fraktalnageometria fraktalna)|IFS]]) złożonym z [[Kontrakcja_Kontrakcja (matematyka)|przekształceń zwężających]] <math>f_i:\colon X\to X.</math>. Niech <math>x_{n+1} = f_{i_n}(x_n)</math> będzie orbitą startującą w dowolnym punkcie <math>x_0\in X.</math>. Wówczas [[IFS (geometria fraktalna)#Definicja formalna|atraktor]] <math>A</math> układu <math>\mathcal{F}</math> (który istnieje w myśl twierdzenia Hutchinsona) odtwarzany jest przez zbiór [[Punkt skupienia zbioru#Związane pojęcia|punktów skupienia]] <math>\omega((x_n)) = \bigcap_{k=1}^{\infty} \overline{\{x_n: n\geqslant k\}}</math> orbity <math>x_n{:}</math>:
 
* (wersja probabilistyczna) <math>A=\omega((x_n))</math> z prawdopodobieństwem 1, jeśli tylko ciąg <math>i_n, n=1,2,...\dots,</math> sterujący wyborem funkcji w n-tym kroku iteracji, jest losowany z użyciem [[Schemat Bernoulliego|schematu Bernoulliego]] na zbiorze <math>\{1,...\dots,m\};</math>;
* (wersja [[Algorytm probabilistyczny#Derandomizacja|zderandomizowana]]) <math>A=\omega((x_n)),</math>, jeśli tylko ciąg <math>i_n, n=1,2,...\dots,</math>, jest dyzjunktywny nad alfabetem <math>\{1,...\dots,m\},</math>, tzn. dowolny łańcuch skończony nad <math>\{1,...\dots,m\}</math> pojawia się w <math>i_n.</math>.
 
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.
 
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 ==
[[Plik:Sierpinski1.png|thumb|Trójkąt Sierpińskiego]]
Na początku stawia się na [[płaszczyzna|płaszczyźnie]] 3 dowolne punkty (powinny być [[Prosta|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 [[generator liczb losowych|generatora liczb losowych]], wybierać je) i stawia punkt w połowie [[odległość|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ąt Sierpińskiego|trójkąta Sierpińskiego]]. Jego wierzchołkami są trzy punkty wybrane na samym początku gry.
 
pts = (
0 + 500j,
500 + 500j,
250 + 0j,
)