автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование методов моделирования и разработка программного обеспечения для изучения фрактальных свойств системы N тел

На правах рукописи

Дехканбаев Дмитрий Саттаркулович

ИССЛЕДОВАНИЕ МЕТОДОВ МОДЕЛИРОВАНИЯ И РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ ИЗУЧЕНИЯ ФРАКТАЛЬНЫХ СВОЙСТВ СИСТЕМЫ N ТЕЛ

Специальность: 05.13.18 -«Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2004

Работа выполнена на кафедре «Вычислительные системы и сети» Государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» (ГУАП).

Научный руководитель:

доктор технических наук, профессор Игнатьев Михаил Борисович Официальные оппоненты:

доктор технических наук, профессор Александров Виктор Васильевич, кандидат физико-математических наук, ассистент Тараканов Петр Александрович

Ведущая организация: НИИММ им. Н. Г. Чеботарева

Защита состоится / ,2._ 2004г. в часов на

заседании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, г.Санкт-Петербург, ул.Б.Морская, 67, ГУЛП.

С диссертацией можно ознакомиться в библиотеке ГУАП. Автореферат разослан 2004г.

Ученый секретарь совета

доктор технических наук, профессор

Л

Л.А.Осипов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. За последние десятилетия использование вычислительной техники стало общепризнанным инструментом исследования в различных областях знаний. Современная вычислительная техника позволяет проводить численные эксперименты, заполняющие разрыв между предсказаниями теории и результатами лабораторных экспериментов.

Одним из приоритетных направлений фундаментальной науки является исследование крупномасштабной структуры Вселенной. По мнению ряда ученых-астрофизиков, распределение светящихся объектов (галактик, квазаров) в пространстве обладает свойством самоподобия, причем это свойство сохраняется при увеличении дальности наблюдений. Поэтому в качестве геометрической модели пространственного распределения наблюдаемых объектов - системы N тел - используется фрактальная геометрия. В настоящее время фрактальная размерность является общеиспользуемой характеристикой неоднородности распределения светящегося вещества в наблюдаемой области Вселенной. Этим обусловлено повышенное внимание к изучению существующих методов вычисления фрактальной размерности и разработке специальных методов, приспособленных к специфическому пространственному распределению точек, изображающих светящиеся объекты. Эта специфика, в частности, связана с ограниченной выборкой объектов на небесной сфере - наблюдения стоят дорого и данных по всему небу на сегодня еще нет. Наблюдения крупномасштабной структуры Вселенной организуются в тонких слоях, а большинство методов вычисления фрактальной размерности неприменимы при такой геометрии данных.

В настоящее время отсутствуют работы, проводящие систематическое исследование методов вычисления фрактальной размерности трехмерных точечных структур на тестовых объектах - фракталах с заданными свойствами. Появление нового метода вычисления фрактальной размерности - метода цилиндров, позволяющего вычислять фрактальную размерность в слоях, делает крайне актуальной задачу его исследования на тестовых объектах. Проведение такого исследования добавит новый «инструмент» к числу уже имеющихся методов вычисления фрактальной размерности трехмерных точечных структур, применимый при такой геометрии данных, в которой неприменимы

РОС НАЦИОНАЛЬНА!1 БИБЛИОТЕКА I

остальные методы. Эти вычисления требуют больших вычислительных мощностей. Процедура моделирования включает в себя:

получение экспериментальных данных (координат светящихся объектов в тонких слоях);

построение соответствующей фрактальной структуры; вычисление фрактальной размерности;

распространение фрактальной структуры на другие части Вселенной.

Пункты 1 и 4 решаются астрофизиками.

Цель и задачи диссертации. Целью работы является разработка и исследование методов построения фракталов с заданной размерностью, разработка программного обеспечения для изучения фрактальных свойств системы N тел и сравнение методов вычисления фрактальной размерности точечных структур на тестовых объектах с использованием параллельных вычислений.

В соответствии с поставленной целью в работе решаются следующие задачи:

1. Исследование методов построения фракталов с заданными свойствами. Использование фракталов, построенных с помощью этих методов в качестве тестовых объектов для исследования методов вычисления фрактальной размерности.

2. Анализ существующих методов вычисления фрактальной размерности, выявление их недостатков и достоинств.

3. Разработка программного обеспечения для изучения фрактальных свойств системы N тел на параллельных вычислительных системах.

4. Сравнение методов вычисления фрактальной размерности на примерах генерации регулярных и стохастических фрактальных структур.

Предмет исследования. Предметом исследования являются методы генерации трехмерных точечных структур с заданной фрактальной размерностью и методы вычисления фрактальной размерности трехмерных точечных структур.

Методы исследования. Поставленные в диссертационной работе задачи решаются на основе численных методов с использованием параллельных вычислений, теории фрактальных структур и теории вероятностей.

Научная новизна. В работе новыми являются следующие результаты:

1. Предложена модификация алгоритма построения пыли Леви, позволяющая получить регулярные структуры.

2. Предложен способ организации подвыборок трехмерных точечных структур с заданной геометрией.

3. Произведена оценка временной сложности методов генерации трехмерных точечных фрактальных структур с использованием вероятностного подхода.

4. Разработаны параллельные версии методов условной плотности и метода цилиндров.

5. Разработан метод ячеек, ускоряющий вычисление фрактальной размерности трехмерных точечных структур.

6. Произведена оценка временной сложности методов вычисления фрактальной размерности и времени выполнения программ, реализующих эти методы при помощи вероятностного и статистического подхода.

7. Проведено аналитическое и численное исследование нового метода вычисления фрактальной размерности трехмерных точечных структур - метода цилиндров.

8. Модернизирован метод цилиндров - увеличена точность вычисления фрактальной размерности.

Практическая значимость работы. Практическая значимость работы состоит в установлении области применения методов вычисления фрактальной размерности, формулировки критериев, позволяющих производить вычисления фрактальной размерности на точечном трехмерном множестве с заданной точностью, разработке рекомендаций для использования этих методов, разработке пакетов соответствующих программ.

Научная значимость работы. Научная значимость работы состоит в исследовании нового метода вычисления фрактальной размерности - метода цилиндров. Исследование нового метода на тестовых объектах и сравнение с другими методами добавляет его в ряд "инструментов" для нахождения фрактальной размерности трехмерных точечных структур. Такой подход - сравнение методов вычисления фрактальной размерности на наборе тестовых фракталов - используется впервые.

Положения, выносимые на защиту:

1. Исследование методов построения трехмерных точечных фрактальных структур и методов вычисления фрактальной размерности. Оценка временной сложности и времени выполнения исследованных методов.

2. Метод ячеек для ускорения вычисления фрактальной размерности трехмерных точечных структур и уменьшения временной сложности методов объемной и оболочечной условных плотностей. Использование параллельных вычислительных структур для уменьшения времени выполнения программ, реализующих рассмотренные методы.

3. Аналитическое и численное исследование нового метода вычисления фрактальной размерности трехмерных точечных структур -метода цилиндров. Модернизация метода цилиндров для уменьшения времени выполнения и увеличения точности.

4. Результаты сравнения методов вычисления фрактальной размерности точечных структур на тестовых объектах: точность вычисления величины фрактальной размерности, область применения методов, способы настройки для увеличения точности вычисления фрактальной размерности.

5. Комплекс программ для вычисления фрактальной размерности трехмерных точечных структур методами условной плотности и цилиндров, а также создания трехмерных точечных структур с заданной фрактальной размерностью и геометрией.

Внедрение результатов работы. Результаты диссертационной работы нашли применение при решении следующих практических задач:

- создание программного комплекса для проведения учебных лабораторных работ по дисциплине «Распределенные вычисления на сетях» (ГУАП, гСанкт-Петербург).

Апробация работы. Основные положения работы докладывались и обсуждались на следующих конференциях:

- Всероссийская астрономическая конференция 2001, Санкт-Петербург;

- Пятая, шестая и седьмая научные сессии аспирантов ГУАП 20022004, Санкт-Петербург;

- Международная научная конференция Новая Геометрия Природы 2003, Казань.

Публикации по теме диссертации. По материалам диссертации опубликовано 12 печатных работ, в том числе 6 программных продуктов, зарегистрированных в фонде алгоритмов и программ ВНИИЦ.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и двух приложений. Объем работы без приложений - 130 стр., работа содержит 7 таблиц и 43 рисунка, список литературы содержит 88 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении отражены актуальность темы, цель и задачи работы, предмет и методы исследования, научная и практическая значимость работы, научная новизна и положения, выносимые на защиту.

В первой главе даются основные понятия и свойства фракталов, фрактальной размерности и методы ее нахождения. Приведены примеры применения фракталов и фрактальной размерности в различных областях. На основании этого уточняются терминология и задачи, решаемые в этой работе.

До недавнего времени геометрические модели различных природных объектов традиционно строились на основе сравнительно простых геометрических фигур: прямых, многоугольников, окружностей, многогранников, сфер. Этот классический набор, вполне достаточный для описания элементарных структур, становится плохо применимым для характеристики сложных систем: сильно развитой турбулентности, идентификации процессов (сетевого трафика) в компьютерных сетях, крупномасштабной структуры Вселенной и т.д.

Согласно Мандельброту, фрактал это целое, состоящее из частей, в каком-то смысле подобных целому. Существующие определения фрактала не конструктивны, т.к. не содержат способа построения фрактала. В противоположность этому фрактальная размерность определена конструктивно.

Существует несколько разных определений размерности геометрического объекта. Рассмотрим одну из фрактальных размерностей -размерность подобия. Размерность Б объекта появляется как показатель степени г в соотношении между К, числом равных подобъектов, и коэффициентом подобия г: = 1.

Величину Б называют размерностью подобия. Выражение для Б через N и г находится логарифмированием обеих частей:

Ь^ЛГ

Другой фрактальной размерностью является массовая размерность. Определение плотности непрерывной среды, основано на предположении о том, что значение плотности не зависит от величины объема. В случае точечных фракталов понятия плотности точек не существует, так как в каждой части структуры содержится иерархия кластеров. В этом случае говорят об условной плотности, значение которой зависит от объема. Для ее описания необходимо ввести независимую переменную - радиус области Я, в которой производится подсчет точек. Например, для самоподобной структуры число точек растет по степенному закону: , где - число точек в области радиуса К Фрактальная размерность, называемая массовой размерностью, вычисляется по формуле: д- Л^ц.

Для характеристики плотности точечных фракталов также используется функция пр(И): пр{К) = ~ , где пр(Я) -

концентрация точек в области радиуса Я, 3-В - фрактальная коразмерность. Фрактальная размерность вычисляется по формуле:

Кроме фрактальной размерности существует ряд свойств, по которым классифицируют фракталы. Фракталы бывают: детерминированные и случайные (стохастические); самоподобные и самоаффинные. Детерминированность означает, что строя фрактал заданным алгоритмом с одними и теми же начальными условиями, получается одинаковый результат. Способы построения стохастических фракталов отличаются от детерминированных случайным выбором параметров (например, выбор аффинного преобразования). Множество называется самоподобным, если оно разбивается на непересекающиеся части, каждая из которых получается из целого при помощи одного из преобразований подобия. Множество называется самоаффинным, если оно разбивается на непересекающиеся части, каждая из которых получается из целого при помощи одного из аффинных преобразований.

(2)

И*

Наиболее употребительными методами в статистической физике и астрономии вычисления фрактальной размерности точечных структур являются метод корреляционных функций, метод объемной условной плотности и оболочечной (дифференциальной) условной плотности.

Важной проблемой при изучении распределения галактик является выбор таких методов математического анализа, которые адекватны наблюдаемым структурам. Для исследования области применимости и ограничений методов анализа крупномасштабной структуры необходимо использовать искусственные распределения с априорно известными свойствами. С появлением нового метода - метода двухточечной условной лучевой концентрации (метода цилиндров), позволяющего вычислять фрактальную размерность там, где неприменимы существующие методы - в сжатых/вытянутых областях делает исследование методов вычисления фрактальных структур на тестовых объектах особенно актуальным.

Во второй главе описываются реализованные методы построения треххмерных точечных структур с заданной фрактальной размерностью. Эти структуры используются в качестве тестовых объектов для исследования методов вычисления фрактальной размерности в третьей главе. Такое сравнение проводится впервые. Предложены модификации алгоритмов построения трехмерных точечных фрактальных структур, позволяющее более полно представить возможный спектр исследуемых объектов: модификация алгоритма построения пыли Ле-ви, позволяющая получить регулярные структуры с выделенным центром и предлагается использование подвыборок с заданной геометрией в качестве тестовых объектов.

Простейшим тестовым объектом является однородное распределение точек. Оно создается при помощи генератора псевдослучайных чисел, равномерно распределенных на интервале (0,1). Фрактальная размерность в этом случае равна топологической размерности пространства.

Пыль Леви (Levy dust) создается при помощи случайного блуждания Рэлея-Леви: направление шагов изотропно, а их длина U случайна. При этом вероятность Рг шага длиной U: Pr{U>u}=u"D, где 0<D<2. Пыль Леви не изотропна, что объясняется наличием лакун.

Можно получить регулярные (не фрактальные) структуры, откладывая все шаги при построении от одной центральной точки. В результате получаются шаровые кластеры с точками, сгущёнными к центру или поверхности шара, либо раскиданные по большому объёму

разреженно (так, что нельзя с уверенностью назвать это распределением по шару).

Вселенная Фурнье напоминает Канторову пыль. Основная разница заключается в том, что конструкция Фурнье вложена в пространство, а не в интервал на прямой. Это точечный самоподобный регулярный фрактал. Вселенная Фурнье определяется тремя параметрами: К - начальный масштаб, к - коэффициент сжатия, п - число итераций. Фрактальная размепность вселенной Фтонье рассчитывается согласно фор-

,п „ НЫ 1о§(1 + Ют) \т

муле (1): £) = —£— = —2;-—, где N - минимальное число шаров радиуса г, ^н^^б^одимых ^^ покрытия всех точек, а Бг - топологическая размерность пространства. Когда части фрактала Фурнье не перекрывают друг друга, величина 1/г может принимать любые значения в интервале от 3 до бесконечности, в результате чего фрактальная размерность Б принадлежит интервалу от 0 до 1п(7)/1п(3)= 1.7712.

Для построения фрактальных структур с размерностью от 0 до Бг используется бета каскад: начальный куб с линейным размером 10 разбивается на М меньших кубов с линейным размером 11=10/М 1/3. Из этих М кубов только т остаются 'активными', т.е. продолжают делиться на следующем шаге. Путем повторения этой процедуры получается фрактальное распределения маленьких кубов, которые заменяются точками на последнем шаге. Фрактальную размерность полученного

набора точек можно вычислить согласно формуле (1): £) = —

Для уменьшения регулярности фрактала, получаемого при помощи бета каскада, предлагается на последнем шаге вместо того, чтобы ставить точку в центре каждого куба, располагать ее случайным образом внутри куба. Тогда получаемая структура не будет иметь такой кубо-ориентированный характер на малых масштабах (при задании фрактальной размерности, равной топологической, получается "квадратно-гнездовое" распределение, что заметно отличается от однородного заполнения).

Сложность алгоритма создания начального распределения точек можно оценить требуемым для его проведения количеством вычислений координат точек. Большинство алгоритмов создания начального распределения точек в пространстве имеют вычислительную сложность порядка О^), где N - число точек.

При однородном заполнении точками объема, для N точек каждая из трех координат вычисляется за одно действие, следовательно, получаем 3N операций, т.е. О^).

Вычислительная сложность для Пыли Леви также порядка О^). Хотя при построении Пыли Леви для каждой точки выполняется большее количество операций, чем при построении однородного распределения, но количество операций на каждую точку является постоянным и не зависит от числа точек.

Теперь рассмотрим алгоритм создания Вселенной Фурнье: входным параметром, определяющим число операций, является п - число итераций. При этом количество копирований, в результате которых появляются точки в данном алгоритме, будет 7°. Соответственно вычислительная сложность алгоритма построения вселенной Фурнье 0(7°), при этом 7° есть число точек, т.е. N.

Вычислительная сложность бета каскада является функцией не одной, а двух переменных: к - число итераций и т - число активных кубов. При этом количество точек N в результате равно тк а вычислительная сложность 0(тк).

В третьей главе методы вычисления фрактальной размерности трехмерных точечных структур исследуются на тестовых объектах из второй главы. Впервые проводится исследование нового метода - метода цилиндров и сравнение его с методами объемной и оболочечной условной плотности. Разработаны параллельные версии исследуемых алгоритмов вычисления фрактальной размерности. Предложен метод ячеек, позволяющий уменьшить время выполнения программ за счет предварительной структуризации входных данных. Произведена оценка временной сложности алгоритмов вычисления фрактальной размерности при помощи вероятностного подхода и оценка времени выполнения программ, реализующих эти алгоритмы при помощи статистического подхода. Предложены рекомендации по использованию и настройке каждого метода для более точного вычисления фрактальной размерности. Оценена погрешность при помощи выборочной дисперсии и нормированной пуассоновской ошибки. Предложена модификация метода цилиндров для более точной оценки фрактальной размерности. Вычисленные величины фрактальной размерности трехмерных точечных структур сравниваются с полученными аналитически.

В данной главе впервые приводится сравнительный анализ методов вычисления фрактальной размерности на фракталах с различной заданной размерностью. Рассматривается применимость методов при

различных свойствах входных данных. Сформулированы рекомендации по использованию и настройке каждого метода.

Кроме сравнения величины вычисленной фрактальной размерности с аналитически предсказанным значением, проводится оценка погрешности с использованием нормированной пуассоновской ошибки и выборочной дисперсии. Также приводятся оценки времени выполнения и вычислительной сложности при помощи статистического и вероятностного подходов.

Предлагается метод ускорения вычислений при работе с точечными структурами для вычисления фрактальной размерности. Предложены параллельные версии рассматриваемых алгоритмов для выполнения на кластерной параллельной вычислительной системе.

Впервые приводится подробное исследование метода цилиндров. В данной главе этот метод применяется к тестовым фракталам и сравнивается с методами объемной и оболочечной условной плотности. Предложен способ быстрой проверки попадания точек в цилиндр. Предложен способ обработки численных данных, полученных методом цилиндров, позволяющей получить более точное значение фрактальной размерности.

В методах условной плотности вычисление фрактальной размерности производится за два действия: вычисление условной плотности как функции масштаба и аппроксимация полученных данных прямой. Фрактальная размерность вычисляется по формуле (2). Методы условной плотности отличаются видом области, в которой вычисляется условная плотность: в методе объемной условной плотности это шар с центром в выделенной точке; в методе оболочечной условной плотности это сферический слой вокруг выделенной точки. Вместо сферы в этих методах также можно использовать куб. Другим отличием является величина шага масштаба: в методе объемной условной плотности он изменяется равномерно в логарифмическом масштабе, а в методе оболочечной условной плотности - равномерно в линейном масштабе. Ввиду такого сходства, временная сложность алгоритмов, реализующих эти методы, одинакова. Время выполнения обоих методов также сходны. Непосредственное сравнение их затруднено разным шагом -логарифмическим у объемного и линейным у оболочечного метода. По причине линейного шага метод оболочечной условной плотности может ближе подойти к максимально возможному масштабу - толщине объекта. Минимальный масштаб в методе оболочек не может быть меньше величины шага масштаба, т.е. толщины оболочки.

Метод цилиндров существенно отличается от обоих методов условной плотности. Вычисление фрактальной размерности производится за два действия: вычисление вероятности распределения точек Р(а) в цилиндрах, соединяющих пары точек и аппроксимация полученных данных при помощи формулы:

где а - масштаб, 0 < а < 1, г и х- максимальный и минимальный масштабы, на которых проявляется фрактальность, а - фрактальная коразмерность, А и В - константы.

Поскольку в этом методе цилиндр строится на паре выделенных точек, он позволяется вычислять фрактальную размерность на максимальных масштабах, недостижимых для методов условной плотности в случае вытянутого фрактала. Максимальный масштаб методов условной плотности ограничен толщиной объекта.

Временная сложность методов условной плотности O(N2), метода цилиндров - O(N3). Временная сложность оценена как аналитически, без учета реализации алгоритма, так и практически - замеряя время выполнения в зависимости от длины входных данных. Полученные обоими способами результаты хорошо согласуются.

Для ускорения работы программ вычисления фрактальной размерности предлагается структурировать входные данные при помощи метода ячеек. Идея этого приема взята из сеточных методов моделирования эволюции системы N тел. После ввода исходных данных вычисляется объем параллелепипеда, описанного вокруг всех точек структуры, и строится трёхмерный массив ячеек, заполняющих весь параллелепипед. Для каждой ячейки создаётся список точек, попадающих в неё. Тогда для нахождения условной плотности не надо перебирать все N точек, достаточно проверить лишь точки, попадающие в смежные ячейки.

Автором предложен способ уменьшения временной сложности методов условной плотности с использованием метода ячеек. В результате выбора числа ячеек k=N4/3 получаем временную сложность 0(Ы4/3) вместо 0(N2).

Для уменьшения времени выполнения программ, реализующих методы вычисления фрактальной размерности, применен MPI (Message passing interface) - стандарт на программный инструмента-

(3)

рий для обеспечения связи между ветвями параллельного приложения. Разработанные схемы параллелизма позволяют достичь эффективности вычислений Е ~ 9 9 % .

Оценка погрешности производится с помощью нормированной пуассоновской ошибки и выборочной дисперсии. Пусть дана случайная величина Х=x1 Определим случайную выборку объема п:

(х1) = (х1,х:,...,х). Тогда выборочное среднее от ^ X] =— , а выборочная дисперсия 52 — х)2 . Тогда нормированная пу-

ассоновская ошибка есть

_1_ V«

и

■И <0 а <и та

О)

2.7 2.6 2.5 2.4 2.3 2.2 2.1

1 1 1 1 I 1 "mid.dat" о

"mid.dat" -

"Kiax.dat" +

"max.dat" -

"min.dat" а

"min.dat" -

- —в-—

1 1 1 1 1 .1

-0.7

-0.6

-0.5

-0.1

-0.4 -0.3 -0.2 1д{вса1е)

Рис. 1. Результат вычисления объемной условной плотности - отмечен ромбами, крестами отмечен возможный максимум, а квадратами - минимум с учетом суммарной ошибки.

Эти две ошибки дополняют друг друга: на малых масштабах число измерений максимально: п=^ где N - число точек в структуре, поэтому пуассоновская ошибка мала, а выборочная дисперсия велика. На больших масштабах, когда число измерений минимально: п«^ они меняются местами - дисперсия выборки мала (по причине малого раз-

мера этой выборки), но зато пуассоновская ошибка велика. Рассмотрим это на примере метода объемной условной плотности. На рис. 1 приведен график условной плотности и две кривых, полученных суммированием и вычитанием величины суммарной ошибки.

В заключении формулируются основные результаты, полученные в диссертационной работе.

В приложении 1 приведен список публикаций автора по теме диссертации.

В приложении 2 приведены тексты основных программ, написанных автором по теме диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

Основные научные и практические результаты диссертационной работы состоят в следующем:

1. Предложена модификация алгоритма построения пыли Леви, позволяющая получить регулярные структуры с выделенным центром. Используя такие структуры в качестве тестовых входных данных для программ вычисления фрактальной размерности, можно проверить, как они определят не фрактальные структуры.

2. Предложен способ организации подвыборок трехмерных точечных структур с заданной геометрией. Вырезая слои из фрактальных структур можно смоделировать вид выборок в астрономических наблюдениях, что позволяет использовать их для тестирования методов вычисления фрактальной размерности для данной области исследований.

3. Произведена оценка временной сложности методов генерации трехмерных точечных фрактальных структур с использованием вероятностного подхода. Для всех рассмотренных методов она составляет О^), разница состоит лишь в определении числа N по входным параметрам метода. При создании однородного заполнения и пыли Леви N задается явно, во вселенной Фурнье N=7', где к - число шагов, в бета каскаде ^тк, где т - число кубов, остающихся на каждом шаге для последующего деления.

4. Разработаны параллельные версии методов условной плотности и метода цилиндров. Эффективность предложенного распараллеливания Е х 99% . Это позволяет исследовать более крупные структуры. Точность вычисления фрактальной размерности напрямую зависит от числа точек N исследуемой структуры.

5. Предложен метод ячеек, ускоряющий вычисление фрактальной размерности трехмерных точечных структур. Ускорение зависит от настроек ускоряемых методов и вида входных данных. Для однородного распределения точек в пространстве и "стандартных" настройках

методы условной плотности работают в раз быстрее, где к - число

ячеек. Если установить к « -/V4'3, где N - число точек во входных данных, то временная сложность уменьшится от 0(К2) до 0(Ы'"3). Для метода цилиндров данный способ ускорения подходит меньше, однако, при тех же условиях ускоряет работу в среднем в 3,5 раза.

6. Произведена оценка временной сложности методов вычисления фрактальной размерности и времени выполнения программ, реализующих эти методы при помощи вероятностного и статистического подхода. Методы условной плотности имеют временную сложность порядка 0(К2), а метод цилиндров 0(К3). Поэтому разумно применять метод цилиндров в тех случаях, когда он дает более точный результат вычисления фрактальной размерности - т.е. в случае сильно вытянутой/сжатой области, заполненной точками.

7. Проведено аналитическое и численное исследование нового метода вычисления фрактальной размерности трехмерных точечных структур - метода цилиндров. Метод по точности сравним с известными методами объемной и оболочечной условной плотности. Область применения метода шире (слои, конусы), а временная сложность больше (0(К3) против 0(К2)).

8. Модернизирован метод цилиндров - увеличена точность вычисления фрактальной размерности. Предложено исключать крайние интервалы из рассмотрения при аппроксимации численных данных, полученных методом, для вычисления фрактальной размерности. Это обусловлено выделенными точками, на которых строится цилиндр. В результате этого, плотность точек в концах цилиндра будет либо больше (в случае включенных границ), либо меньше (в случае исключенных границ цилиндра) аналитически вычисляемого значения. Это позволяет увеличить точность вычисленной величины фрактальной размерности на 10-15%.

9. Сравнение методов вычисления фрактальной размерности на примерах генерации регулярных и стохастических точечных фрактальных структур с разной геометрией позволило изучить область применения методов, сформулировать рекомендации по использова-

нию каждого метода, позволяющие выбрать подходящий и настроить его.

10. Разработано программное обеспечение, зарегистрированное в отраслевом фонде алгоритмов и программ. Программы разработаны для выполнения на кластерной вычислительной системе, что позволяет уменьшить время их выполнения. Кроме астрофизических наблюдательных данных, разработанное программное обеспечение может быть применено и к другим системам N-тел. Но это потребует дополнительной доработки.

Основные результаты диссертации опубликованы в работах:

1. Дехканбаев Д. С. Генерация 3D N-точечных фрактальных структур с заданными свойствами и примеры их статистической обработки// Всероссийская Астрономическая Конференция: Сб. докл./ ВАК, 2001. С. 59-60.

2. Дехканбаев Д. С. Разработка и исследование программно - математического обеспечения для решения задач N-тел// Пятая научная сессия аспирантов ГУАП, 2002. С. 332-339.

3. Дехканбаев Д. С. Два метода анализа трёхмерных точечных структур// Шестая научная сессия аспирантов ГУАП, 2003. С. 229-231.

4. Dehkanbaev D. S., Gromov A. L, Suson D., Baryshev Yu. V. A discussion of new method for fractal dimension calculation// Joint International Scientific. 2003. V. 5. P. 14-15.

5. Gromov A. L., Dehkanbaev D. S.,Yakutseni P. P. Geometrical interpretation of a single DNA and realated fractal// Joint International Scientific Conference. 2003. V. 4. P. 14-16.

6. Дехканбаев Д. С. Исследование методов моделирования и разработка программного обеспечения для изучения системы N тел// Седьмая научная сессия аспирантов ГУАП, 2004. С. 316-318.

7. Программа вычисления фрактальной размерности методом объемной условной плотности/ Дехканбаев Д.С., Барышев Ю.В., Громов А.Л.//№50200400897. Сб. Алгоритмы и программы. М.: ВНИИцентр. 2004.

8. Программа вычисления фрактальной размерности методом оболо-чечной условной плотности/ Дехканбаев Д.С., Барышев Ю.В., Громов А.Л.//№50200400898. Сб. Алгоритмы и программы. М.: ВНИИцентр. 2004.

9. Программа вычисления фрактальной размерности методом цилиндров/ Дехканбаев Д.С., Барышев Ю.В., Бухмастова Ю.Л., Громов

А.Л.//№50200400834. Сб. Алгоритмы и программы. М: ВНИИцентр. 2004.

10. Программа геометрической интерпретации ДНК/ Дехканбаев Д.С., Громов А.Л., Якуцени П.Ш/№50200400831. Сб. Алгоритмы и программы. М.: ВНИИцентр. 2004.

11. Программа построения регулярной пыли Леви с выделенным центром/ Дехканбаев Д.С., Громов А.Л., Барышев Ю.В.//№50200400833. Сб. Алгоритмы и программы. М.: ВНИИцентр. 2004.

12. Программа построения рандомизированного бета каскада/ Дехканбаев Д.С., Барышев Ю.В., Сыозон Д., Громов АЛ.//№50200400832. Сб. Алгоритмы и программы. М.: ВНИИцентр. 2004.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Тираж 100 экз. Заказ № 531

Отдел оперативной полиграфии ГОУ ВПО «СПбГУАП»

190000, Санкт-Петербург,ул.Б.Морская, 67

№2 6 0 9 4

ВВЕДЕНИЕ

ГЛАВА 1 .КЛАССИЧЕСКИЕ ФРАКТАЛЫ И МЕТОДЫ ИХ ИССЛЕДОВАНИЯ

1.1. История изучения искусственных и естественных фракталов

1.1.1. Треугольник Паскаля

1.1.2. Пыль Кантора

1.1.3. Кривые, заполняющие плоскость

1.1.4. Кривая Коха

1.1.5. Салфетка Серпинского

1.1.6. Множества Жулиа

1.2. Фракталы, некоторые свойства, примеры

1.2.1. Свойства фракталов

1.2.2. Примеры фракталов в различных науках

1.2.3. Примеры использования фракталов

1.2.4. Построение фракталов

1.3. Фрактальные размерности, определения

1.4. Численные методы определения фрактальной размерности

1.4.1. Плотность стохастических фрактальных структур

1.4.2. Двухточечная условная лучевая концентрация

1.4.3. Метод корреляционных функций

1.4.4. Сравнение методов анализа распределения галактик 48 Выводы

ГЛАВА 2. ПОСТРОЕНИЕ ТРЕХМЕРНЫХ ТОЧЕЧНЫХ СТРУКТУР С ЗАДАННЫМИ СВОЙСТВАМИ

2.1. Реализация методов построения N точечных фракталов

2.1.1. Однородное заполнение

2.1.2. Пыль Леви

2.1.3. Вселенная Фурнье

2.1.4. Бета каскад

2.2. Оценка вычислительной сложности

Выводы

ГЛАВА 3. ВЫЧИСЛЕНИЕ ФРАКТАЛЬНОЙ РАЗМЕРНОСТИ ТРЕХМЕРНЫХ

ТОЧЕЧНЫХ СТРУКТУР

Введение

3.1. Метод объемной условной плотности

3.1.1. Программная реализация метода объемной условной плотности

3.1.2. Процедура нахождения фрактальной размерности с помощью метода объ- 81 емной условной плотности

3.1.3. Квази обол очечная условная плотность

3.1.4. Применение метода условной плотности к исследованию ДНК

3.2. Метод оболочечной условной плотности 86 3.2.1. Процедура нахождения фрактальной размерности с помощью метода обо- 89 лочек

3.3. Метод цилиндров (двухточечная условная концентрация)

3.3.1. Сравнение методов условной плотности и цилиндров

3.3.2. Аналитическое исследование метода цилиндров

3.3.3. Программная реализация метода цилиндров

3.3.4. Процедура нахождения фрактальной размерности с помощью метода 99 цилиндров

3.3.5. Изменения в программе, позволяющие считать быстрее

3.4. Ускорение вычислений при работе с точечными структурами. Метод ячеек

3.5. Параллельные вычисления на кластерной вычислительной системе

3.5.1. Основные понятия параллельных вычислений

3.5.2. Используемое программное и аппаратное обеспечение

3.5.3. Распараллеливание используемых алгоритмов

3.6. Оценка погрешностей

3.7. Оценка времени выполнения

3.8. Сравнение методов вычисления фрактальной размерности на тестовых 118 фракталах

Выводы

Актуальность работы

За последние десятилетия использование вычислительной техники стало общепризнанным инструментом исследования в различных областях знаний. Современная вычислительная техника позволяет проводить численные эксперименты, заполняющие разрыв между предсказаниями теории и результатами лабораторных экспериментов.

Одним из приоритетных направлений фундаментальной науки является исследование крупномасштабной структуры Вселенной. По мнению ряда ученых-астрофизиков, распределение светящихся объектов (галактик, квазаров) в пространстве обладает свойством самоподобия, причем это свойство сохраняется при увеличении дальности наблюдений [66]. Поэтому в качестве геометрической модели пространственного распределения наблюдаемых объектов системы N тел — используется фрактальная геометрия. В настоящее время фрактальная размерность является общеиспользуемой характеристикой неоднородности распределения светящегося вещества в наблюдаемой области Вселенной. Этим обусловлено повышенное внимание к изучению существующих методов вычисления фрактальной размерности и разработке специальных методов, приспособленных к специфическому пространственному распределению точек, изображающих светящиеся объекты. Эта специфика, в частности, связана с ограниченной выборкой объектов на небесной сфере наблюдения стоят дорого и данных по всему небу на сегодня еще нет. Наблюдения крупномасштабной структуры Вселенной организуются в тонких слоях, а большинство методов вычисления фрактальной размерности неприменимы при такой геометрии данных.

В настоящее время отсутствуют работы, проводящие систематическое исследование методов вычисления фрактальной размерности трехмерных точечных структур на тестовых объектах — фракталах с заданными свойствами. Появление нового метода вычисления фрактальной размерности — метода цилиндров, позволяющего вычислять фрактальную размерность в слоях, делает крайне актуальной задачу его исследования на тестовых объектах. Проведение такого исследования добавит новый «инструмент» к числу уже имеющихся методов вычисления фрактальной размерности трехмерных точечных структур, применимый при такой геометрии данных, в которой неприменимы остальные методы. Эти вычисления требуют больших вычислительных мощностей. Процедура моделирования включает в себя:

• получение экспериментальных данных (координат светящихся объектов в тонких слоях);

• построение соответствующей фрактальной структуры;

• вычисление фрактальной размерности;

• распространение фрактальной структуры на другие части Вселенной.

Пункты 1 и 4 решаются астрофизиками.

Цель работы

Целью работы является разработка и исследование методов построения фракталов с заданной размерностью, разработка программного обеспечения для изучения фрактальных свойств системы N тел и сравнение методов вычисления фрактальной размерности точечных структур на тестовых объектах с использованием параллельных вычислений.

Задачи работы

• Исследование методов построения фракталов с заданными свойствами. Использование фракталов, построенных с помощью этих методов в качестве тестовых объектов для исследования методов вычисления фрактальной размерности;

• анализ существующих методов вычисления фрактальной размерности, выявление их недостатков и достоинств;

• разработка программного обеспечения для изучения фрактальных свойств системы N тел на параллельных вычислительных системах;

• сравнение методов вычисления фрактальной размерности на примерах генерации регулярных и стохастических фрактальных структур.

Предмет исследования

Предметом исследования являются методы генерации трехмерных точечных структур с заданной фрактальной размерностью и методы вычисления фрактальной размерности трехмерных точечных структур.

Методы исследования

Поставленные в диссертационной работе задачи решаются на основе численных методов с использованием параллельных вычислений, теории фрактальных структур и теории вероятностей.

Научная значимость работы

Научная значимость работы состоит в исследовании нового метода вычисления фрактальной размерности — метода цилиндров. Исследование нового метода на тестовых объектах и сравнение с другими методами добавляет его в ряд "инструментов"для нахождения фрактальной размерности трехмерных точечных структур. Такой подход — сравнение методов вычисления фрактальной размерности на наборе тестовых фракталов — используется впервые.

Практическая значимость работы

Практическая значимость работы состоит в установлении области применения методов вычисления фрактальной размерности, формулировки критериев, позволяющих производить вычисления фрактальной размерности на точечном трехмерном множестве с заданной точностью, разработке рекомендаций для использования этих методов, разработке пакетов соответствующих программ.

Научная новизна В работе новыми являются следующие результаты:

• предложена модификация алгоритма построения пыли Леви, позволяющая получить регулярные структуры;

• предложен способ организации подвыборок трехмерных точечных структур с заданной геометрией;

• произведена оценка временной сложности методов генерации трехмерных точечных фрактальных структур с использованием вероятностного подхода;

• разработаны параллельные версии методов условной плотности и метода цилиндров;

• разработан метод ячеек, ускоряющий вычисление фрактальной размерности трехмерных точечных структур; произведена оценка временной сложности методов вычисления фрактальной размерности и времени выполнения программ, реализующих эти методы при помощи вероятностного и статистического подхода; проведено аналитическое и численное исследование нового метода вычисления фрактальной размерности трехмерных точечных структур — метода цилиндров; модернизирован метод цилиндров — увеличена точность вычисления фрактальной размерности.

Положения, выносимые на защиту

На защиту выносятся следующие результаты:

Исследование методов построения трехмерных точечных фрактальных структур и методов вычисления фрактальной размерности. Оценка временной сложности и времени выполнения исследованных методов.

Метод ячеек для ускорения вычисления фрактальной размерности трехмерных точечных структур и уменьшения временной сложности методов объемной и оболочечной условных плотностей. Использование параллельных вычислительных структур для уменьшения времени выполнения программ, реализующих рассмотренные методы.

Аналитическое и численное исследование нового метода вычисления фрактальной размерности трехмерных точечных структур — метода цилиндров. Модернизация метода цилиндров для уменьшения времени выполнения и увеличения точности.

Результаты сравнения методов вычисления фрактальной размерности точечных структур на тестовых объектах: точность вычисления величины фрактальной размерности, область применения методов, способы настройки для увеличения точности вычисления фрактальной размерности.

• Комплекс программ для вычисления фрактальной размерности трехмерных точечных структур методами условной плотности и цилиндров, а также создания трехмерных точечных структур с заданной фрактальной размерностью и геометрией.

Апробация работы

Основные положения работы докладывались и обсуждались на следующих конференциях:

• Всероссийская астрономическая конференция 2001, Санкт- Петербург;

• Пятая, шестая и седьмая научные сессии аспирантов ГУАП 2002- 2004, Санкт-Петербург;

• Международная научная конференция Новая Геометрия Природы 2003, Казань.

Публикации

Основные результаты работы изложены в 12 публикациях.

Структура и объем работы

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и двух приложений. Объем работы без приложений — 130 стр., работа содержит 7 таблиц и 43 рисунка, список литературы содержит 88 наименований.

Основные результаты, полученные в диссертации: предложена модификация алгоритма построения пыли Леви, позволяющая получить регулярные структуры с выделенным центром. Используя такие структуры в качестве тестовых входных данных для программ вычисления фрактальной размерности, можно проверить, как они определят не фрактальные структуры; предложен способ организации подвыборок трехмерных точечных структур с заданной геометрией. Вырезая слои из фрактальных структур можно смоделировать вид выборок в астрономических наблюдениях, что позволяет использовать их для тестирования методов вычисления фрактальной размерности для данной области исследований; произведена оценка временной сложности методов генерации трехмерных точечных фрактальных структур с использованием вероятностного подхода. Для всех рассмотренных методов она составляет О(А^), разница состоит лишь в определении числа N по входным параметрам метода. При создании однородного заполнения и пыли Леви N задается явно, во вселенной Фурнье N = 7к, где к - число шагов, в бета каскаде N = тк, где га - число кубов, остающихся на каждом шаге для последующего деления; разработаны параллельные версии методов условной плотности и метода цилиндров. Эффективность предложенного распараллеливания Е & 99%. Это позволяет исследовать более крупные структуры. Точность вычисления фрактальной размерности напрямую зависит от числа точек N исследуемой структуры; разработан метод ячеек, ускоряющий вычисление фрактальной размерности трехмерных точечных структур. Ускорение зависит от настроек ускоряемых методов и вида входных данных. Для однородного распределения точек в пространстве и "стандартных"настройках методы условной плотности работают в Vа раз быстрее, где к - число ячеек. Если установить к ~ А/"4/3, где N - число точек во входных данных, то временная сложность уменьшится от 0(А2) до Для метода цилиндров данный способ ускорения подходит меньше, однако, при тех же условиях ускоряет работу в среднем в 3,5 раза; произведена оценка временной сложности методов вычисления фрактальной размерности и времени выполнения программ, реализующих эти методы при помощи вероятностного и статистического подхода. Методы условной плотности имеют временную сложность порядка 0(Ы2), а метод цилиндров 0(А3). Поэтому разумно применять метод цилиндров в тех случаях, когда он дает более точный результат вычисления фрактальной размерности — т.е. в случае сильно вытянутой/сжатой области, заполненной точками; проведено аналитическое и численное исследование нового метода вычисления фрактальной размерности трехмерных точечных структур метода цилиндров. Метод по точности сравним с известными методами объемной и оболочечной условной плотности. Область применения метода шире (слои, конусы), а временная сложность больше (0(А3) против 0( А2)); модернизирован метод цилиндров — увеличена точность вычисления фрактальной размерности. Предложено исключать крайние интервалы из рассмотрения при аппроксимации численных данных, полученных методом, для вычисления фрактальной размерности. Это обусловлено выделенными точками, на которых строится цилиндр. В результате этого, плотность точек в концах цилиндра будет либо больше (в случае включенных границ), либо меньше (в случае исключенных границ цилиндра) аналитически вычисляемого значения. Это позволяет увеличить точность вычисленной величины фрактальной размерности на 10-15%;

• сравнение методов вычисления фрактальной размерности на примерах генерации регулярных и стохастических точечных фрактальных структур с разной геометрией позволило изучить область применения методов, сформулировать рекомендации по использованию каждого метода, позволяющие выбрать подходящий и настроить его;

• разработано программное обеспечение, зарегистрированное в отраслевом фонде алгоритмов и программ (пункты 7-12 приложения 1). Программы разработаны для выполнения на кластерной вычислительной системе, что позволяет уменьшить время их выполнения. Кроме астрофизических наблюдательных данных, разработанное программное обеспечение может быть применено и к другим системам К-тел. Но это потребует дополнительной доработки.

Автор благодарен М. Б. Игнатьеву, А. Л. Громову, Ю. В. Барышеву, Ю. Л. Бухмастовой и А. И. Лавровой за поддержку в работе и полезные обсуждения, Ю. Е. Шейнину и Д. Сьюзону за предоставленные вычислительные мощности.

Заключение

1. Александров В.В., Горский Н.Д. Представление и обработка изображений. Рекурсивный подход. J1. 1985.

2. Александров В.В. Развивающиеся системы. СПб. 2000.

3. Ахо А. В., Хопкрофт Дж., Ульман Дж. Д. Структуры данных и алгоритмы. М.: Изд. дом «Вильяме», 2001.

4. Барышев Ю. В. Современное состояние наблюдательной космологии// Итоги Науки и Техники. Серия Классическая теория поля и теория гравитации. Т. 4: Гравитация и космология. 1992. С. 89-135.

5. Барышев Ю. В. Иерархическая структура Метагалактики// Изв. CAO. Т. 14. 1981. С. 24 -43.

6. Барышев Ю. В., Бухмастова Ю.Л. Метод условной лучевой концентрации для оценки фрактальной размерности распределения галактик. Письма в астрономический журнал. 2004. Т. 30. №6. С.1—7.

7. Божокин С. В., Паршин Д. А. Фракталы и мультифракталы. СПб.: Изд-во СПбГУ, 2000.

8. Бухмастова Ю. Л., Барышев Ю. В. Метод определения фрактальной размерности// Всероссийская Астрономическая Конференция. Сб. 2001. С. 23.

9. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир. 1985.

10. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. М. Изд-во БХВ, 2002.11. Глейк Дж. Хаос. 2001.

11. Городецкий А. Я., Заборовский В. С. Информатика. Фрактальные процессы в компьютерных сетях. СПб.: Изд-во СПбГТУ, 2000.

12. Дьюдни А. К. Множество Мандельброта и родственные ему множества Жюлиа// В мире науки. 1988. № 1. С. 88—93.

13. Евсеев И. MPI для начинающих: Учеб. пособие/ http://www.csa.ru:81/ il/mpitutor/. 2003.

14. Игнатьев M. Б. Голономные автоматические системы. Изд-во АН СССР, M-J1., 1963.

15. Игнатьев М. Б. Лингво-комбинаторное моделирование плохо формализованных систем// Информационно-управлящие системы. 2003. №6. С. 34-37.

16. Карпов Б., Баранова Т. С++ специальный правочник. СПб.: Питер, 2001.

17. Кожевникова Г. П. Структуры данных и проектирование эффективной вычислительной среды. Львов: Изд-во ЛГУ, 1986.

18. Коржов В. Linux и параллелизм// Открытые системы/http://www.citforum.ru/operatingsystems/linux/linuxparall/. 2003.

19. Корн Г. и Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1974.

20. Корнеев В. В. Параллельные вычислительные системы. М.: Нолидж, 1999.

21. Кроновер Р. М. Фракталы и хаос в динамических системах. М.: Постмаркет, 2000.

22. Кузюрин H. Н. Сложность комбинаторных алгоритмов: Курс лекций. 2003.

23. Лацис А. О. Как построить и использовать суперкомпьютер. М.: Бестселлер, 2003.

24. Левин Б. Р. Теоретические основы статистической радиотехники. Т.1. М., 1974

25. Мандельброт Б. Фрактальная геометрия природы/ М.; Ижевск, Ин-т компьютерных исследований. 2002.

26. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. СПб.: БХВ, 2002.

27. Пиблс Дж. Структура вселенной в больших масштабах М.: Мир, 1983. Страуструп Б. Язык программирования С++. М.: Бином, СПб.: Невский Диалект, 2000. Федер Е. Фракталы М.: Мир, 1991.

28. Фракталы в физике// Тр. VI международного симпозиума по фракталам в физике, Италия, Триест, 9—12 июля, 1985г./ МЦТФ; Под ред. Л. Петронеро и Э. Тозатти, М.: Мир, 1988.

29. Шинкаренко В. И. Об оценке эффективности алгоритмов с учетом архитектуры ЭВМ. Ком-пютерное моделирование. Тезисы докладов межгосударственной научнопрактической конференции. Днепродзержинск: Изд-во ДГТУ, 2000.

30. Шредер М. Фракталы, хаос, степенные законы. Ижевск: РХД, 2001.

31. Эрлих А. Технический анализ товарных и фондовых рынков, М.: Инфра-М. 1996.

32. Alexandrov V.V., Gorsky N.D. Cognition through visual perception. World scientific, 1991.

33. Barnsley M. F. Fractals everywhere. 1990.

34. Baryshev Yu. V. On the fractal nature of the large scale structure of the universe. Astron.Astrophys.Transactions. 1994. V. 5. P. 15—23.

35. Baryshev Yu. V. An upper limit on hidden mass of fractals of galaxies// Сообщения CAO. Вып. 64. 1990. С. 86-88.

36. Baryshev Yu. V. Stability of supermassive stars in the field gravitation theory// Problems of high energy physics and field theory. M.: Nauka, 1991. XIII. P. 61 66.

37. Baryshev Yu. V. Pulsation of supermassive star in the tensor field gravitation theory// Variability of Blazars/ Cambridge Univ. Press. 1992. P. 52—54.

38. Baryshev Yu. V. Conceptual problems of fractal cosmology. Astron.Astrophys.Transactions. 2000. V. 19. P. 417-435.

39. Baryshev Yu. V., Raikov A. A., Tron A. A. Gravitational lensing inside fractal structure// Gravitational lenses in the Universe. Liege, 1993. P. 365—368.

40. Baryshev Yu. V., Labini F. S., Montuori M., Pietronero L. Facts and ideas in modern cosmology. Vistas in Astronomy. 1994. V. 38. P. 419-500.

41. Baryshev Yu.V., Labini F. S., Montuori M., Pietronero L. Teerikorpi P. On the fractal structure of galaxy distribution and its implications for cosmology// Fractals. 1998. V. 6. P. 231—243.

42. Baryshev Yu., Teerikorpi P., Discovery of Cosmic Fractals. World Scientific Publ. Co., 2002.

43. Brooks C. L., Karplus M., and Pettit В. M. Proteins: A theoretical perspective of dynamics, structure and thermodynamics. N. Y.: John Wiley, 1988.

44. Castagnoli C., Provenzale A. A fractal cascading model for the large scale galaxy distribution// Vistas in Astronomy. 1990. V. 33. P. 323—335.

45. Castagnoli C., Provenzale A. From small-scale fractality to large-scale homoge-neity: a family of cascading models for the distribution of galaxies// Astronomy &; Astrophisycs. 1991- V. 246. P. 634-643.

46. Chen F. F. Introduction to plasma physics. N. Y.: Plenum Press, 1998.

47. Chiang L. Y., Coles P. Phase information and the evolution of cosmological density perturbations// Mon.Not.Roy.Astron.Soc. 2000. V. 311. P. 809-824.

48. Davis, M. Is the universe homogeneous on large scales? //Critical Dialogues in Cosmology/ Ed. N. Turok. World Scientific. Singapore, 1997. P. 13-23.

49. Frederickson P., Kaplan J. L., Yorke S. D., Yorke J. A. The Liapunov dimension of strange attractors// Journal of Different Equations. V. 49. 1983. P. 185—207.

50. Gabrielli A., Labini F. S., Joyce M. and Pietronero L. Statistical physics for cosmic structures. 2003. P. 103-105.

51. Garcia A. Numerical Methods for Physics. Prentice-Hail. 1994.

52. Gefen Y., Mandelbrot В. В., Aharony A. Critical phenomena on fractal lattices// Phys. Rev. Lett. 1980. V. 45. P. 855-858.

53. Gordon J. M., Goldman A. M., Maps J., Costello D., Tiberio R., Whitehead B. Superconducting-normal phase boundary of a fractal network in a magnetic field// Phys. Rev. Lett. 1986. V. 56. P. 2280 2283.

54. Gould H. and Tobochnik J. An Introduction to Computer Simulation Methods. Addison Wesley, 1988. Parts 1 and 2.

55. Gromov A. L., Dehkanbaev D. S., Yakutseni P. P. Geometrical interpretation of a single DNA and realated fractal// Joint International Scientific Conference. 2003. V. 4. P. 14—16.

56. Guzzo L., Large-scale structure from galaxy and cluster surveys, astro-ph/0207285, 2002.

57. Нао В., Lee H. C., Zhang S. Fractals related to long DNA sequences and complete genome// Chaos Solitons & Fractals. 2000. V. 11. P. 825-836.

58. Hutchinson J. E., Fractals and Self Similarity// Indiana University Mathematics Journal. 1981. V. 30. JV®5. P. 713-747.

59. Hawkes J. Hausdorff measure, entropy and the independence of small sets.// Pr. Of the London Mathematical Society. (3). 1978. №28. P. 700—724.

60. Labini S. F., Amendola L. Power spectrum of self-similar distribution// Astrophys. J. 1995. V. 468. P. L1-L4.

61. Labini S. F., Gabrielli A., Pietronero, L. Statistical Physics for Cosmic Structures. N. Y.: Springer-Verlag, 2003.

62. Labini S. F., Montuori M., Pietronero, L., Scale-invariance of galaxy distribution// Phys. Rep. 1998. V. 293. P. 61 226.

63. Mandelbrot B. B. The fractal geometry of nature. N. Y. 1983.

64. Mandelbrot B. B. Fractal lacunarity and scenarios for the near-isotropic distribution of galaxies. N. Y. 2001.

65. Mandelbrot B. B. Fractals: Form, Chance, and Dimension. Freeman. San Francisco, 1977.

66. Martinez V. J., Saar E. Statistics of the Galaxy Distribution, USA, CRC Press LLC, 2002. N.W.

67. Martinez V. J., Is the Universe Fractal?// Science, 1999. V. 284. P. 445-446.

68. Martinez V. J., Saar E., Statistics of the galaxy distribution. Chapman & Hall/CRC. N.Y. 2002.

69. Martinez V. J., Saar E., Clustering statistics in cosmology, astro-ph/0209208. 2002.

70. Mitchison G. J. and Wilcox M., Rule governing cell division in anabaena// Nature, 1972. V. 239. P. 110-111.

71. Peebles, P.J.E. Principles of physical cosmology/ Princeton Univ. Press Princeton, 1993.

72. Peebles, P.J.E. The Large-Scale Structure of the Universe/ Princeton Univ. Press Prinston. New Jersey, 1980.

73. Peitgen H.-O., Jurgens H., Saupe D. Chaos and fractals New frontiers of science. USA, N. Y.: Springer-Verlag, 1993.

74. Pietronero L., Montuori M., Labini F. S. On the fractal structure of the visible universe// Critical Dialogues in Cosmology/ Ed. N. Turok; World Scientific. Singapore, 1997. P. 24—49.

75. Pietronero, L. The fractal structure of the Universe: correlations of galaxies and clusters and the average mass density// Physica A. 1987. V. 144. P. 257—284.

76. Prusinkiewicz P., Graphical application of L-systems// Proceeding of Graphics Interface '86. Kaufmann, 1986. P. 247-253.

77. Prusinkiewicz P., Hanan J., Lindenmaer Systems, Fractals and Plants: of Lecture Notes on Biomathematics. N. Y.: Springer-Verlag, 1989. V. 79.

78. Recursive machines and computing technology. Sweden, Stokholm: Information processing 74, computer hardware and architecture, IFIP Congress 74, August 5—10, 1974. P. 65—70. Glushkov V.M., Ignatiev M.B., Myasnikov V.A., and others.

79. The radial space distribution of KLUN galaxies up to 200 Mpc: incompleteness or evidence for the behaviour predicted by fractal dimension 2?// Astron.Astrophys, 1998. V. 334. P. 395—403. Teerikorpi P., Hanski M., Theureau G., and others.

80. Turtle графика// Nick Software/ http://nsft.narod.ru/Fractals/turtle.htm. 2001.

81. Stevens R. J., Lehar A. F., Preston F. H. Manipulation and Presentation of Multidimensional Image Data Using the Peano Scan/ / IEEE Transactions on Pattern Analysis and Machine Intelligence 1983. 5. P. 520-526.

82. Velho L., de Miranda J. Gomes Digital Halftoning with Space-Filling Curves, Computer Graphics 1991. 25. 4. P. 81-90.

83. Witten I. H., Neal M. Using Peano curves for bilevel display of continuous tone images// IEEE// Computer Graphics and Applications. May 1982. P. 47—52.

84. Wu K., Lahav O., Rees M., The large-scale smoothness of the Universe// Nature. 1999. V. 397. P. 225 235.