Визуализация в научных исследованиях. Ечкина Е.Ю - 22 стр.

Е. Ю. Ечкина, С. Б. Базаров, И. Н. Иновенков «Визуализация в научных исследованиях»


                                    x   1 2 0   x1  0 
                               T1   1             x   0 ,
                                      x
                                    2      0 1 2  2  
                                   x   1 2 0   x1  1 2 
                               T   1               ,
                                   x 2    0 1 2   x2   0 
                                    x   1 2 0   x1   1 4 
                               T1   1            x       
                                      x
                                    2      0 1 2   2   3 4
Рассмотрим теперь два других метода построения ковра Серпинского:
детерминированный и рандомизированный.
В детерминированном алгоритме рассматривают следующую последовательность
множеств:
E0 - компактное множество (произвольное),
E 1  T1 ( E0 )  T2 ( E0 )  T3 ( E0 )

En  T1 ( En 1 )  T2 ( En 1 )  T3 ( En1 )

Если в качестве E0 выбрать замкнутую треугольную область S 0 , то множества En
построенные указанным способом, будут те же, что и при удалении центральных
треугольных частей.
В рандомизированном алгоритме в качестве начального множества выбирают одну
точку:
x0 - начальная точка (произвольная)
x1  T1 ( x0 ) or T2 ( x 0 ) or T3 ( x 0 )

x n  T1 ( x n-1 ) or T2 ( x n-1 ) or T3 ( x n-1 )

На каждом шаге            вместо того, чтобы применять сразу три преобразования
T1 ( S ), T2 ( S ), T3 ( S ) , мы используем только одно, выбранное случайным образом.
Следовательно, на каждом шаге получаем ровно одну точку. Оказывается, что после
некоторого переходного этапа точки, полученные в результате выполнения
рандомизированного алгоритма, в точности заполняют ковер Серпинского.
Замечательным свойством алгоритма, основанного на теории IFS, является то, что их
результат (аттрактор) совершенно не зависит от выбора начального множества E0 или
начальной точки x 0 . В случае детерминированного алгоритма это означает, что в
качестве E0 можно взять любое компактное множество на плоскости: предельное
множество будет по-прежнему совпадать с ковром Серпинского. В случае
рандомизированного алгоритма, вне зависимости от выбора начальной точки x 0 ,
после некоторых итераций точки начинают заполнять ковер Серпинского.
В общем случае, для того, чтобы построить систему итерированных функций (IFS)
введем в рассмотрение совокупность сжимающих отображений, т. е. таких
отображений, что
 d (T ( x ), T ( y )  sd ( x, y ), 0  s  1,       x, y  X   отображений, т. е.
Кафедра АНИ факультета ВМК МГУ имени М. В. Ломоносова http://ani.cs.msu.su            22