Gra w chaos

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Liść paproci wygenerowany za pomocą gry w chaos

Gra w chaosalgorytm komputerowego generowania obrazów pewnych fraktali. Generuje on przybliżony obraz atraktora lub punktu stałego dowolnego systemu funkcji iterowanych.

Algorytm[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Trójkąt Sierpińskiego

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.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. Michael Barnsley, Andrew Vince, Developments in fractal geometry, „Bulletin of Mathematical Sciences”, 3 (2), 2013, s. 299–348, DOI10.1007/s13373-013-0041-3, ISSN 1664-3607 [dostęp 2020-03-25] (ang.).