Percolation. HK’sA. Morozov N.P.


МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
"Московский государственный технический университет радиотехники,
электроники и автоматики"
МГТУ МИРЭА

Факультет Кибернетики
Кафедра Высшей Математики
КУРСОВОЙ ПРОЕКТ
по дисциплине
«Языки Программирования»
Тема курсового проекта:
«Нахождение протекания в теории о перколяции с помощью алгоритма Хошена-Копельмана (алгоритма многократной маркировки кластеров)»

Студент группы КС-83-10
Морозов Н.П.
Руководитель курсового проекта (работы): доцент, к. ф.-м. н.
Пулькин И.С.
Рецензент: доцент, к. ф.-м. н.
Федоров В.Б.
Работа представлена к защите «____»_________201___ г. (подпись студента)
«Допущен к защите» «____»_________201___ г. (подпись руководителя)
Москва 2012
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
"Московский государственный технический университет радиотехники,
электроники и автоматики"
МГТУ МИРЭА

_________________________________________________________________________
(наименование факультета)
_________________________________________________________________________
(наименование кафедры)
Утверждаю
Заведующий
кафедрой______________Ю.И.Худак«____» __________201___ г.
ЗАДАНИЕ
на выполнение курсового проекта
по дисциплине «____________________________________________________________»
по теме: «___________________________________________________________________»
Студент Морозов Н.П Группа КС-83-10
Задание на курсовой
проект, (работу) выдал «___»______201__г.
Пулькин И. С.
Задание на курсовой
проект, (работу) получил «___»______201__г. Морозов Н.П.
Перколяция – интересное новшество.
В качестве реферативного введения, хотелось бы отметить, что перколяция - крайне важное явление в науке. Как в сфере компьютерных технологий, так и в точных науках, таких как физика. Недаром протекание переменного тока вычисляется именно при помощи перколяции.
В данном проекте будет описана перколяция, как явление и как теория. Также её структура. Понятие о перколяционном кластере. Будет проиллюстрирована двумерная перколяционная решётка на примере задачи о протекании тока.
Также в проекте будут описаны все алгоритмы, с помощью которых можно определить протекание. В частности, более подробно, будет описан алгоритм Хошена-Копельмана (Алгоритм Многократной Маркировки Кластеров).
В качестве подтверждения, отчёта о проделанной работе, будут представлены тексты программ, с помощью которых определялось протекание в перколяционной решётке, с помощью алгоритма Хошена-Копельмана.
К вступительной реферативной части хотелось бы также добавить, что перколяция является довольно новым понятием и нуждается в тщательном изучении, так как теория о перколяции позволяет выполнять ряд сложных задач, связанных с протеканием. Именно в этой связи нам необходимо подробнее изучить возможности условий протекания. Именно в этой связи мы и изучаем теорию о перколяции.

Содержание
Введение………………………………………………………………………….5
Основная часть…………………………………………………………………...9
1. Цель работы и средства ее достижения…………………………………..9
2. Описание алгоритмов……………………………………………………..10
3. Описание алгоритма Хошена-Копельмана………………………………13
4. Тексты программ………………………………………………………….17
5. Результаты расчетов………………………………………………………21
Заключение……………………………………………………………………….22
Список использованных источников…………………………………………...23

Введение
Перколяция иначе протекание (от английского Percolation)— в материаловедении — скачкообразное возникновение новых свойств в материале (электрической проводимости — для изолятора, газопроницаемости — для газонепроницаемого материала и т. д.) при его наполнении «заполнителем», обладающим данной характеристикой. В ряде случаев, заполнителем могут выступить поры и пустоты.
Перколяционную природу имеют процессы прохождения жидкостей через пористую неподвижную фазу, проникновения жидкой фазы по межзеренным границам поликристалла, образования полимерных гелей, а также ферромагнетизм и электропроводность примесных полупроводников.
Перколяция возникает при некоторой критической концентрации наполнителя или пор (пороге перколяции) в результате образования от одной стороны образца материала до противоположной непрерывной сетки (канала) из частиц (кластеров) наполнителя.
Процесс перколяции может быть наглядным образом рассмотрен на примере протекания электрического тока в двумерной квадратной решетке, состоящей из электропроводящих и непроводящих участков. К двум противоположным сторонам решетки припаяны металлические контакты, которые присоединены к источнику питания. При некотором критическом значении доли проводящих элементов, расположенных случайным образом, цепь замыкается.
Перколяция берёт своё начало из работ Флори и Стокмайера (1941 и 1943 года соответственно). Ими был рассмотрен процесс образования гелей при полимеризации.
Однако начало теории о перколяции связывают с публикацией работ Броадбента и Хаммерсли в 1957 году. Ими был рассмотрен процесс с математической точки зрения.
Перколяционный кластер.
Перколяционный кластер является фрактальным образованием, в котором в свою очередь, можно выделить иные фрактальные подструктуры. Остов кластера – токопроводящая часть кластера. Мёртвые концы – части кластера, соединённые с остовом посредством одного узла (связи). Мёртвые концы составляют большую часть кластера, однако, не участвуют в проводимости. Красные связи – одиночные связи, при разрушении которых перколяционный кластер перестает проводить ток. Скелет кластера – объединение всех кратчайших путей от данного узла до узлов на заданном расстоянии. Эластичный остов – объединение всех кратчайших путей между двумя данными узлами. Оболочка или внешний периметр, состоящий из трёх узлов кластера, которые соприкасаются с пустыми узлами и соединены с бесконечностью посредством пустых узлов. Полный периметр включает также пустоты внутри кластера.
Структура перколяционного кластера.
Было предложено несколько геометрических моделей, описывающих структуру перколяционного кластера.
Всего насчитывается до 5ти моделей.
Первой моделью такого рода была модель Скал-Шкловского-де Жена.
Модель Скал-Шкловского-де Жена.
В 1947 году Скал и Шкловский, а в 1976 независимо от них де Жен, предложили модель, опсивыющую структуру остова перколяционного кластера в пренебрежении мертвыми концами.
В этой модели предполагается, что кластер состоит из искривленных связей, соединенных узлами, образуя нерегулярную сверхрешетку.
Модель капель и связей.
Предложена в 1977 году Стенли и подробно исследована в 1982-ом Конильо.
В этой модели предполагается, что возникающий бесконечный кластер состоит из фрагментов, в которых существуют многочисленные связи (капли), эти фрагменты соединены друг с другом одиночными связями.
Модель на основе ковра Серпинского.
В 1981 году была предложена модель, которая представляет из себя противоположный крайний случай по сравнению с моделью узлов и связей. Если в модели Скал-Шкловского-де Жена полностью пренебрегалось наличием капель, то в предложенной модели полностью исключались одиночные связи. Главным преимуществом модели является то, что некоторые иерархические модели могут быть решены в ее рамках точно. Она также дает хорошие значения для критических показателей в случае малых размерностей пространства.
Модель на основе фрактала Гивена-Мандельброта.
Построение фрактала Гивена-Мандельброта начинается с отрезка. В структуре фрактала можно обнаружить летли, ветви и мертвые концы всех размеров. Таким образом, фрактал содержит те же элементы, что и перколяционный кластер. Этот факт позволяет использовать фрактал Гивена-Мандельброта в качестве одной из возможных моделей перколяционного кластера.
Иерархическая модель.
Для описания структуры остова перколяционного кластера на пороге перколяции используется иерархическая модель.
Некоторые примеры задач, помимо протекания электрического тока, которые решаются через теорию перколяции:
Сколько надо добавить медных опилок в ящик с песком, чтобы смесь начала проводить ток?
Какой процент людей должен быть восприимчив к болезни, чтобы стала возможна эпидемия?
Иллюстрация к решению задачи о протекании электрического тока в двумерной квадратной решётке:

Основная часть
Цель работы и средства ее достижения

Целью настоящей работы является реализация алгоритмов визуализации, результатов численного моделирования явления перколяции, а также понимание условий протекания.
В данном конкретном случае, нашей задачей является изучение протекания с помощью алгоритма Хошена-Копельмана, также известного как Алгоритм многократной маркировки кластеров.
Для выполнения данной задачи, в качестве инструмента, мы будем использовать язык программирования C (Си).
Нашей первостепенной задачей является создание (моделирование/генерирование) перколяционной решётки (двумерной квадратной решётки).
Для начала следует ознакомиться со всеми имеющимися алгоритмами для нахождения условий протекания. А затем перейти к описанию нашего случая.
Описание алгоритмов.
Основной прогресс в теории перколяции был достигнут путём использования компьютерных методов.
Был разработан ряд высокоэффективных алгоритмов, которые, в частности, позволили определить порог перколяции для множества решёток с высокой точностью.
Особый интерес представляют алгоритмы для обработки подструктур перколяционного кластера и алгоритмы, основанные на параллельных вычислениях.
Алгоритм Зиффа.
Данный алгоритм считается самым эффективным для определения порога перколции, во всяком случае, для двумерных решёток. Кроме того, его реализация очень проста. Алгоритм успешно применялся для нахождения порогов перколяции с точностью до 6 значащих цифр для задачи узлов на квадратной решетке, для задачи узлов на решетке Кагоме и архимедовых решетках.
Алгоритм основывается на двух идеях.
Модель градиентной перколяции.
В градиентной перколяции вероятность заполнения узла зависит от координаты, т.е. можно говорить о градиенте концентрации на решетке. Это значит, что узлы нижнего ряда решетки заняты с вероятностью 0, злы верхнего – с вероятностью 1.
Вдоль вертикального направления, таким образом, вероятность заполнения узлов линейно растет. В верхней части решетки образуется перколционный кластер, простирающийся слева направо. Сверху кластер ограничен границей решетки, а нижняя его часть образует оболочку. Двигаясь по границе оболочки с левой стороны решетки можно достчь её правой границы. То есть оболочка образует путь через всю решетку. Средняя высота этого пути равна порогу перколяции. Для каждого данного градиента концентрации оценка для порога перколяции может быть получена как отношение занятых узлов внешнего периметра к полному числу.
Нахождение внешнего периметр.
Для этого используется хорошо известный метод обхода лабиринта: если двигаться по лабиринту, касаясь его стены левой рукой, то можно дойти до выхода из лабиринта.
Конкретная реализация идеи осуществляется следующим образом:
Применяется метод блуждания, генерирующего оболочку, при котором одновременно генерируется и идентифицируется граница кластера. Статус узла (занят или свободен), достигнутого в процессе случайного блуждания определяется путем генерации случайного числа и сравнения его с вероятностью заполнения узлов. Если в процессе блуждания данный узел ещё не достигнут, то его статус не будет определяться, случайное число не будет генерироваться для него. Такой подход способствует увеличению эффективности алгоритма. Алгоритм не требует создания списков связных узлов или маркировки кластеров. Инициализация решётки начинается с заполнения верхней половины первого столбца занятыми узлами, а нижней половины – свободными. В горизонтальном направлении налагаются периодические граничные условия. Каждый столбец очищается после того, как он был посещён.
Алгоритм Лиса.
Для генерации отдельного кластера широко применяют алгоритм Лиса. Алгоритм независимо был предложен также Хаммерсли и Александровицем.
Идея алгоритма заключается в следующем:
На решётке выбирается некоторый начальный узел, полагается что он занят.
Просматриваются все граничащие с ним узлы и заполняются с вероятностью p, или остаются пустыми с вероятностью 1-p. После просмотра всех узлов периметра образуется кластер большего размера. Просматриваются все узлы, принадлежащие его периметру, заполняя их с вероятностью p, и.т.д.
Процесс продолжается до тех пор, пока не останется непроверенных ячеек. Алгоритм применяют для изучения свойств единичного кластера, в частности, он может быть использован для получения кластерных подструктур (остова, скелета и т.п.)
Алгоритм Хошена-Копельмана.
В 1976 году Хошен и Копельман предложили алгоритм для определения порога перколяции и подсчета размеров кластеров. В настоящее время этот алгоритм находит широкое применения и называется алгоритмом Хошена-Копельмана или алгоритмом многократной маркировки кластеров.
Главным достоинством алгоритма является то, что он позволяет определить порог перколяции и распределение кластеров по размерам за один проход по решетке. Кроме того, алгоритм позволяет экономить машинную память, так как для его работы достаточно хранить в памяти только один ряд(слой) рассматриваемой решетки.
В основе алгоритма лежит соображение о том, что принадлежность узла к тому или иному кластеру является глобальным свойством и может быть определена только после просмотра всей решетки. Идея алгоритма заключается в том, что всем занятым узлам решетки приписываются различные кластерные метки.
Алгоритмы поиска в глубину и ширину.
Хотя алгоритмы поиска в глубину и ширину могут применяться для нахождения стягивающего кластера и определения порога перколяции, обычно они используются для исследования кластерных подструктур.
Алгоритм поиска в глубину.
Алгоритм поиска в глубину может использоваться для поиска путей на графе или покрывающего дерева графа.
Алгоритм может быть разделен на два шага:
Создать связанный список.
Выбрать непроверенный элемент из списка. Пометить его как проверенный. Выполнить процедуру поиска в глубину соседнего неропверенного элемента. Проверять, пока список не исчерпается.
Алгоритм поиска в ширину.
Очевидное изменение организации работы процедуры – замена стека на очередь. Применяется принцип FIFO – первым пришёл, первым ушёл. В данном алгоритме просматриваются сначала все узлы из ближайшего окружения данного узла, после чего процесс продолжается с узлами периметра.
Разница между поиском в ширину и в глубину лишь в том, что узлы помещаются не в стек, а в очередь.
Алгоритм применяется, чтобы найти кратчайший путь между двумя узлами.
Разделяется на 3 шага:
Создание связанного списка.
Помечаются два узла.
Начинается поиск в ширину элемента.
Специальные алгоритмы.
Также существует ряд специальных алгоритмов.
Используется этот ряд специальных алгоритмов для таких специфичных задач, как например, идентификация кластерных подструктур, которая требует разработки частных случаев.
Одним из примеров специальные алгоритмов служат Параллельные алгоритмы для подсчета кластера.


Алгоритм Хошена-Копельмана
или
Алгоритм Многократной Маркровки Кластеров
Термин перколяция означает протекания. И данная теория изучает образование связанных объектов в неупорядоченных средах, как это было описано ранее.
Более подробно мы поговорим об Алгоритме Хошена-Копельмана (Алгоритме Многократной Маркировки Кластеров).
Данный алгоритм был предложен Кошеном и Копельманом в 1976 году для определения порога перколяции и подсчета размеров кластеров.
Назван он был Алгоритмом Многократной Маркировки Кластеров самими авторами.
Поговорим о способе закраски перколяционной решётки. Он может быть как случайным, так называемая случайная перколяция, так и по правилу, так называемая коррелируемая перколяция.
Протекание происходит в том случае, когда «Вещества со способностью к протеканию» проходят от одного конца, до другого конца перколяционной решётки.
Преимущества, цели алгоритма Хошена-Копельмана:
Позволяет определить порог перколяции.
Распределяет кластеры по размеру за один проход по решётке.
Экономит машинную память.
Следует отметить, что существует множество вариантов алгоритма.

Пример работы алгоритма Хошена-Копельмана:

Рис. 2.1 Рис.2.2
На рисунке 2.1 изображён пример заполненной перколяционной решётки, где
0 – обозначает изолятор, а 1 – обозначает элемент протекания.
На рисунке 2.2 распределены размеры кластеров после прохождения перколяционной решётки (один раз).
Исходя из этого можно добавить, что обработка больших объёмов данных является очень ресурсоёмкой задачей. Именно поэтому нам необходима оптимизация данного алгоритма.
Примером ускорения работы алгоритма может быть например применение параллельных вычислений.
Рассмотрим Алгоритм Хошена-Копельмана чуть подробнее.
А именно начнём просматривать последовательно все элементы нашего массива, нашей решётки, начиная с элемента а[1,1]. Нулевой столбец будем пропускать.
Возможны следующие ситуации.
Если значение текущего элемента массива равно 0,то переходим к следующему элементу.
Если текущее значение равно 1, то осуществляем следующую проверку:
- Если сосед слева а[I,j – 1] и сосед сверху a[I – 1,j] имеют значения 0, то в качестве рабочей гипотезы принимаем, что данный элемент входит в новый кластер, присваиваем текущему элементу номер очередной кластерной метки. Конечно, вполне может оказаться, что новый, как нам кажется, кластер является просто веткой какого-то другого кластера. Выяснить это мы сможем только просмотрев весь массив целиком.
- Если сосед сверху имеет значение 0, а сосед слева не равен нулю, то текущая ячейка и ее сосед слева принадлежат одному и тому же кластеру. Текущему элементу присваиваем номер кластерной метки соседа слева.
- Если сосед сверху имеет значение, отличное от нуля, а сосед слева нулевое значение, то текущая ячейка и ее сосед сверху принадлежат одному и тому же кластеру. Однако, у соседа сверху кластерная метка может быть неправильной, так как в результате последующих проверок могло выясниться, что кластер, к которому принадлежит эта ячейка, слился с другим кластером. Поэтому текущему элементу следует присвоить номер правильной кластерной метки соседа сверху.
- Если и сосед сверху и сосед слева имеют ненулевые значения, то все три ячейки принадлежат одному кластеру. Текущему элементу присваиваем наименьший из номеров правильных кластерных меток соседа сверху и соседа сверху. Корректируем массив кластерных меток. Дяля этого в элемент массива d , ссоотвествующий большей из кластерных меток заносим норме правильной кластерной метки.
Рассмотрим еще один вариант алгоритма, позволяющий. одновременно получить распределение кластеров по размерам. Для подсчета распределения кластеров по размерам потребуется вспомогательный массив N.
Если текущий узел не имеет соседних занятых узлов, то предположительно он относится к новому кластеру и ему приписывается очередной номер кластерной метки k.
Заносим в массив N размер нового кластера N(k) := 1. Поскольку генерация решетки и присвоение кластерной метки происходит одновременно, то при анализе соседних узлов, естественно, рассматривается только та часть решетки, которая уже сгенерирована к текущему моменту.
Если текущий узел имеет только один соседний занятый узел, то эти два узла принадлежат к одному и тому же кластеру. Текущему узлу присваиваем номер правильной кластерной метки соседнего узла, увеличиваем размер кластера на еденицу.
Если текущий узел имеет соседние занятые узлы, то текущий узел объединяет соседние кластеры в один. Главное находкой авторов алгоритма является идея о том что не следует проводить переприсваивание кластерных меток уже просмотренным узлам .Определяем минимальную правильную кластерную метку соседних узлов и присваемваем ее текущем узлу. Подсчитываем полное число узлов в новом объединенном кластере N(k) := 1 + sum N(k).
Суммирование проводится по всем соседним занятым узлам с положительными кластерными метками. Теперь различные узлы, принадлежащие одному и тому же кластеру, помечены различными кластерными метками. Чтобы отметить их принадлежность к одному кластеру необходимо изменить их кластерные метки. Для этого элементы массива N, соответствующие неправильно помеченным кластерам, заносится – k – номер правильной кластерной метки со знаком минус.
Таким образом, когда вся решетка будет сформирована, пустые узлы будут помечены нулями, а занятые узлы – положительными целыми числами. Кроме того, будет сформирован массив кластерных меток, состоящий из положительных и отрицательных целых чисел. Узлам, сразу помеченным правильными кластерными метками, соотвествуют положительные целые числа – размер кластера, а узлам, которые в процессе анализа изменили свои первоначальные метки ,- отрицательные.
Полученное при моделировании значение порога перколяции для решетки конечного размера должно быть экстраполировано на бесконечность. Для этого можно воспользоваться скейлинговыми соотношениями.
Тексты программ.
При выполнении данного проекта были использованы две программы, написанные на языке C (Си).
int m,n;
int* dom;
public:
domain(int mx, int my);
~domain();
int get_size(int i){if (i > 0) return m;
else return n;}
int get(int i, int j){return *(dom + (m + 1)*j + i);}
void put(int i, int j, int num){*(dom + (m + 1)*j + i) = num;}
void outputs();
};
// constructor
domain::domain(int mx, int my)
{
m = mx;
n = my;
dom = new int [(mx + 1)*(my + 1)];
}
domain::~domain()
{
delete [] dom;
}
void domain::outputs()
{
int i, j;
cout << " m = " << m << " n = " << n << " \n";
for (i=0; i <= m; i++ ){
for (j=0; j <= n; j++ ) cout << get(i, j) << ' ';
cout << "\n";
}
}
____________________________________________________________________________________________________________________
____________________________________________________________________________________________________________________
#include "percolation.h"
#include <iostream>
using namespace std;
int main()
{
domain a(32,32);
int i, j, k, m, n;
m = a.get_size(1);
n = a.get_size(0);
for (i = 0; i <= m; i++){
for (j = 0; j <= n; j++){
k = (2*j - i + 1000)%5;
if (k==1) a.put(i,j,1);
else a.put(i,j,0);
}
}
a.outputs();
return 0;
}
_____________________________________________________________________________
Изложенные выше программы отвечают за генерацию и визуальное оформление перколяционных решётки. А точнее массивов, образующих перколяционную решётку.
#include "stdafx.h"
#include <conio.h>
#include "percolation.h"
#include <iostream>
using namespace std;
int main()
{
int raz;
int ik,jk,t;
cout<<"vvedite razmer reshetki "; //для удобства задавать квадратную матрицу
cin>>raz;
cout<<"\n";
int raz1;
raz1 = (int)(raz*raz/2)+1; //mas- это массив кластерных меток
int *mas = new int[raz1];
for(t=0;t<raz1;t++)
mas[t]=t+1;
domain a(raz,raz);
int i, j, k, m, n;
m = a.get_size(1);
n = a.get_size(0);

for (i = 1; i <= m; i++){ //задание матрицы
for (j = 1; j <= n; j++){
k = (n-j+1 - i + 1000)%5;
if ((k==1)||(k==2)) a.put(i,j,1);
else a.put(i,j,0);
}
}
a.put(raz,raz,1); //этот блок создал для алгоритма. т.к. нам нужна нулевая строка и нулевой столбец
for (i=0; i<(raz+1); i++){
a.put(0,i,0);
a.put(i,0,0);
}
a.outputs();
cout<<"\n";
int clm=0;
//реализация алгоритма
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
if(a.get(i,j) == 1){
if ((a.get(i,j-1)==0)&&(a.get(i-1,j)==0)){
a.put(i,j,mas[clm]);
clm++;
}
else if ((a.get(i,j-1)!=0)&&(a.get(i-1,j)==0))
a.put(i,j, a.get(i,j-1));
else if ((a.get(i,j-1)==0)&&(a.get(i-1,j)!=0))
a.put(i,j, a.get(i-1,j));
else {
if ((a.get(i,j-1)) < (a.get(i-1,j)))
a.put(i,j, a.get(i,j-1));
else
a.put(i,j, a.get(i-1,j));
}
}
}
}
//вывод матрицы кластерных меток
for (i = 0; i <= m; i++){
for (j = 0; j <= n; j++){
cout<<a.get(i,j)<<" ";
}
cout<<"\n";
}
//правка кластерных меток
int s, l;
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
if (a.get(i,j)!=0){
if ((a.get(i-1,j)!=0) && ((a.get(i-1,j)>a.get(i,j))||(a.get(i,j-1)>a.get(i,j)))){
if (a.get(i-1,j)>a.get(i,j-1)){
s=a.get(i-1,j);
for (ik = 0; ik <= m; ik++){
for (jk = 0; jk <= n; jk++){
if (a.get(ik,jk)==s)
a.put(ik,jk,a.get(i,j));
}
}
}
else if (a.get(i,j-1)>a.get(i-1,j)){
s=a.get(i,j-1);
for (ik = 0; ik <= m; ik++){
for (jk = 0; jk <= n; jk++){
if (a.get(ik,jk)==s)
a.put(ik,jk,a.get(i,j));
}
}
}
}
}
}
}
cout<<"\n";
//вывод конечного результата без нулевой строки и столбца
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
cout<<a.get(i,j)<<" ";
}
cout<<"\n";
}
//проверка протекания
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
if (( (a.get(1,i)) == (a.get(m,j) ) && (a.get(1,i)!=0))){
cout<<"est' perkolyaciya !";
getch();
return 0 ;
}
}
}
getch();
return 0;
}
_________________________________________________________________________
Последняя же программа отвечает именно за выполнение алгоритма Хошена-Копельмана с выводом конечного результата и проверки протекания.
Результаты расчётов.
В ходе нахождения было выяснено, каким образом рассчитывать наличие перколяции с помощью алгоритма Хошена-Копельмана. Был использован наиболее удобный способ алгоритма Многократной Маркировки Кластеров.
Программа 3 работает и делает разметку кластеров, согласно алгоритму.
Программы 1 и 2 вызывают массивы, создающие перколяционную решётку, что позволяет программе 3 успешно выполнять свои функции.
Результат выполнения программы (визуальное оформление) представляет собой вид, аналогичный рисункам 2.1 и 2.2.
Заключение.
В заключении хотелось бы отметить, что перколяция – это очень важное для науки и крайнее интересное, с точки зрения познания, явление.
Главное преимущество данной теории состоит в том, что она крайне проста в визуализации, что встречается довольно редко. Как правило, интересные теории сложны в визуализации и интерпретации, что делает их более сложными к пониманию.
Понимание теории о перколяции делает возможным решение ряда задач, связанных с протеканием, что вне всякого сомнения, приносит огромную пользу во всех сферах научной деятельности, а не только в сфере точных наук.
Алгоритм Хошена-Копельмана или Алгоритм Многократной Маркировки Кластеров доказал, что визуализация данной теории довольно проста, но обработка данных довольно трудоёмкий процесс, даже для компьютера. Из этого можно сделать вывод, что необходима оптимизация, как алгоритмов, так и всех процессов связанных с перколяцией.
Также можно отметить ,что наличие нескольких алгоритмов нахождения протекания позволяет сравнивать результаты исследований и может способствовать нахождению более оптимальных вариантов решений.
Стоит добавить, что перколяцию можно также визуализировать с помощью систем и функций MATLAB, что возможно гораздо проще, нежели на языке C.
Спасибо за внимание.
Список Использованных Источников:
1. Гулд Х., Тобочник Я. — Компьютерное моделирование в физике. Т. 2. М.: Мир, 1990. — 400с.
2. Мартынов Н. Н. — MATLAB 7. Элементарное введение. М.: Кудиц-образ, 2005 — 416с.
3. Павловская Т. А. — С/С++. Программирование на языке высокого уровня.
СПб.: Питер, 2006. — 461с.
4. Тарасевич Ю. Ю. — Перколяция: теория, приложения, алгоритмы.
М.: УРСС, 2002. — 112с.
5. Шилдт Г. — С++: базовый курс. М.: ИД Вильямс, 2010. — 624с.
6. Эфрос А. Л. — Физика и геометрия беспорядка. М.: Наука, 1982. — 176с.
7. Малютин В.М., Склярова Е.А. – Компьютерное моделирование физических явлений Изд.ТПУ Томск 2004 – 86с.

Приложенные файлы

  • docx 18152624
    Размер файла: 203 kB Загрузок: 0

Добавить комментарий