• Задать вопрос менеджеру

Twitter новости

Обучение письменному иноязычному общению на основе ИКТ http://t.co/IK2NAjncrk

Online-опрос

Антиплагиат онлайнДипломант
Яндекс.Метрика

Нахождение протекания в теории о перколяции с помощью алгоритма Хошена-Копельмана (алгоритма многократной маркировки кластеров)

Предмет:Информатика
Тип:Курсовая
Объем, листов:22
Word
Получить полную версию работы
Релевантные слова:узловатость, сосед, сверх, метка, работа, узластый, кластер, поиск, Одигитрия, слева, помощь
Процент оригинальности:
67 %
Цена:200 руб.
Содержание:

Введение. 5

Основная часть. 9

1. Цель работы и средства ее достижения. 9

2. Описание алгоритмов. 10

3. Описание алгоритма Хошена-Копельмана. 13

4. Тексты программ. 17

5. Результаты расчетов. 21

Заключение. 22

Список использованных источников. 23

Вступление:

Перколяция иначе протекание (от английского Percolation)— в материаловедении — скачкообразное возникновение новых свойств в материале (электрической проводимости — для изолятора, газопроницаемости — для газонепроницаемого материала и т. д. ) при его наполнении «заполнителем», обладающим данной характеристикой. В ряде случаев, заполнителем могут выступить поры и пустоты.

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

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

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

Перколяция берёт своё начало из работ Флори и Стокмайера (1941 и 1943 года соответственно). Ими был рассмотрен процесс образования гелей при полимеризации.

Однако начало теории о перколяции связывают с публикацией работ Броадбента и Хаммерсли в 1957 году. Ими был рассмотрен процесс с математической точки зрения.

Перколяционный кластер.

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

Структура перколяционного кластера.

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

Всего насчитывается до 5ти моделей.

Первой моделью такого рода была модель Скал-Шкловского-де Жена.

1. Модель Скал-Шкловского-де Жена.

В 1947 году Скал и Шкловский, а в 1976 независимо от них де Жен, предложили модель, опсивыющую структуру остова перколяционного кластера в пренебрежении мертвыми концами.

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

2. Модель капель и связей.

Предложена в 1977 году Стенли и подробно исследована в 1982-ом Конильо.

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

3. Модель на основе ковра Серпинского.

В 1981 году была предложена модель, которая представляет из себя противоположный крайний случай по сравнению с моделью узлов и связей. Если в модели Скал-Шкловского-де Жена полностью пренебрегалось наличием капель, то в предложенной модели полностью исключались одиночные связи. Главным преимуществом модели является то, что некоторые иерархические модели могут быть решены в ее рамках точно. Она также дает хорошие значения для критических показателей в случае малых размерностей пространства.

4. Модель на основе фрактала Гивена-Мандельброта.

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

5. Иерархическая модель.

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

Некоторые примеры задач, помимо протекания электрического тока, которые решаются через теорию перколяции:

? Сколько надо добавить медных опилок в ящик с песком, чтобы смесь начала проводить ток?

? Какой процент людей должен быть восприимчив к болезни, чтобы стала возможна эпидемия?

Заключение:

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

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

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

Алгоритм Хошена-Копельмана или Алгоритм Многократной Маркировки Кластеров доказал, что визуализация данной теории довольно проста, но обработка данных довольно трудоёмкий процесс, даже для компьютера. Из этого можно сделать вывод, что необходима оптимизация, как алгоритмов, так и всех процессов связанных с перколяцией.

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

Стоит добавить, что перколяцию можно также визуализировать с помощью систем и функций 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с.

Бесплатные работы:

Готовые работы:

Рекомендованные документы: