Gra w chaos: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
→Algorytm: Sformułowanie Twierdzenia, źródła/przypisy, wikizacja |
|||
Linia 1:
[[Plik:Fractal fern1.jpg|thumb|180px|Liść paproci wygenerowany przy pomocy gry w chaos]]
'''Gra w chaos'''
== 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
''Twierdzenie'' o grze w chaos (zob.
* (wersja probabilistyczna) <math>A=\omega((x_n))</math> z prawdopodobieństwem 1, jeśli tylko ciąg <math>i_n, n=1,2,
* (wersja [[Algorytm probabilistyczny#Derandomizacja|zderandomizowana]]) <math>A=\omega((x_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.
Linia 29 ⟶ 30:
pts = (
0 + 500j,
500 + 250 + 0j,
)
|