zinet home
home home
home ИНТЕЛЛЕКТ-ПОРТАЛ
home Стартовал прием материалов в сборник XХХIX-й научной конференции. Требования к публикациям - в разделе "Объявления".

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

РЕСУРСЫ ПОРТАЛА:

Тридцать восьмая научно-практическая конференция
(23 - 28 мая 2016 г.)


Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)


Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)


Тридцать пятая научно-практическая конференция
(24-27 ноября 2015 г.)


Тридцать четвертая научно-практическая конференция
(13-17 октября 2015 г.)


Тридцать третья научно-практическая конференция
(20-27 мая 2015 г.)


Тридцать вторая научно-практическая конференция
(2-7 апреля 2015 г.)


Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)


Тридцатая научно-практическая конференция
(19-25 января 2015 г.)


Двадцать девятая международная научно-практическая конференция
(19-25 ноября 2014 г.)


Двадцать восьмая международная научно-практическая конференция
(08-13 октября 2014 г.)


Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)


Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)


Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)


Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)


Двадцать третья научно-практическая конференция
(10-15 декабя 2013 г.)


Двадцать вторая научно-практическая конференция
(4-9 ноябя 2013 г.)


Первая международная научно-практическая конференция
(14-18 мая 2013 г.)


Двадцать первая научно-практическая конференция
(14-18 мая 2013 г.)


Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)


Девятнадцатая научно-практическая конференция
(26 февряля - 3 марта 2013 г.)


Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)


Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)


Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)


Пятнадцатая научно-практическая конференция
(01 - 07 марта 2012 г.)


Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)


Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)


Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)


Одинадцатая научно-практическая конференция
(26 апреля - 04 мая 2011 г.)


Десятая научно-практическая конференция
(15-23 марта 2011 г.)


Девятая научно-практическая конференция
(27-31 декабря 2010 г.)


Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)


Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)


Шестая научно-практическая конференция
(1-15 апреля 2010 г.)


Пятая научно-практическая конференция
(20-27 мая 2009 г.)


Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)


Третья научно-практическая конференция
(20-27 декабря 2008 г.)


Вторая научно-практическая конференция
(1-7 ноября 2008 г.)


Первая научно-практическая конференция
(10-15 мая 2008 г.)



НАШИ ПАРТНЕРЫ:

Студия веб-дизайна www.zinet.info



Студия ландшафтного дизайна Флора-МК


Уникальное предложение!



Сайт-визитка - теперь
всего за 200 грн!

подробнее>>>



ДОСЛІДЖЕННЯ ЕФЕКТИВНОСТІ АЛГОРИТМІВ, ЩО ВИКОРИСТОВУЮТЬСЯ ДЛЯ ГЕНЕРУВАННЯ ПЕРКОЛЯЦІЙНИХ КЛАСТЕРІВ

 

Роговський А.В.

Україна, м. Луцьк,

Східноєвропейський національний університет

імені Лесі Українки

 

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

 

Незважаючи на те, що в теорії перколяції отримано значну кількість строгих, математично обґрунтованих результатів, основний прогрес базується саме на комп’ютерному моделюванні. На даний час розроблено ряд високоефективних алгоритмів, які дозволили отримати поріг перколяції для множини решіток із високою точністю. Робота у сфері розробки цих алгоритмів триває і надалі. Особливий інтерес представляють алгоритми для обробки підструктур перколяційного кластеру та алгоритми, що грунтуються на паралельних обчисленнях.

Метою даної роботи є дослідження та аналіз ефективності алгоритмів, які використовуються для виявлення кластерів у перколяційних решітках. Двома важливими мірами складності алгоритмів є значення їх часової та ємнісної складності, що розглядаються як функції від розміру вхідних даних. Для того, щоб обчислити часову та ємнісну складність алгоритму, слід визначити час, який необхідний для виконання кожної команди, та об’єм пам’яті кожного регістру. Для обчислення складності алгоритму будемо використовувати логарифмічний ваговий критерій. Нехай l(i) – логарифмічна функція на цілих числах, яка задається наступними рівностями:

Логарифмічний критерій базується на припущенні, що ціна виконання команди (її вага) прямо пропорційна довжині її операнд. [1]

Перейдемо безпосередньо до опису алгоритмів. Алгоритм Лі (алгоритм хвильового трасування) використовується для генерування окремого кластеру. Ідея даного алгоритму полягає в наступному. Вибираємо на решітці деякий початковий вузол і вважаємо, що він зайнятий. Переглядаємо усі його сусідні вузли (периметр) та заповнюємо їх із ймовірністю p або залишаємо порожніми із ймовірністю (1 – р). Після перегляду усіх вузлів утворюється кластер великого розміру. Переглядаємо усі вузли, які належать його периметру, заповнюючи їх з ймовірністю р, і т.д. Цей процес продовжується до того часу, поки не залишиться неперевірених вузлів. Кластери, отримані методом Лі, підпорядковуються розподілу s2ns(p). Алгоритм використовують для вивчення властивостей одиничного кластеру. Зокрема, він може бути використаний для отримання кластерних підструктур (наприклад, кістяка). [3] Обчислювальна складність алгоритму Лі є близькою до значення O(N2), де N – розмірність перколяційної решітки.

Ще одним алгоритмом є алгоритм Хошена – Копельмана, який використовується для підрахунку розмірів кластеру. Його ще називають алгоритмом багатократного маркування кластерів. Його найбільшою перевагою є те, що він дозволяє отримати шукані характеристики решітки за один прохід. Крім того, він дозволяє зекономити машинну пам’ять, оскільки для його роботи достатньо зберігати в пам’яті тільки один ряд (шар) решітки.

В основі даного алгоритму лежить твердження про те, що приналежність вузла до того чи іншого кластеру є глобальною властивістю та може бути визначена тільки після перегляду всієї решітки. Ідея алгоритму полягає в тому, що всім зайнятим вузлам решітки приписуються різні кластерні мітки. [2]

Розглянемо роботу алгоритму на прикладі задачі вузлів на квадратній решітці. Одразу слід зауважити, що існує велика кількість варіантів цього алгоритму. Але ми розглянемо найпростіший. Моделювати решітку буде масив а розмірності L x L. Нехай вузли решітки заповнені з ймовірністю р. Будемо генерувати випадкові числа, які рівномірно розподілені на інтервалі [0, 1]. Якщо згенероване число менше або рівне р, наступному елементу масиву а присвоюємо значення 1, інакше – 0. Оскільки комп’ютерний експеримент буде проводитись багатократно, то цю послідовність можна зафіксувати. Зберігати послідовність у вигляді масиву зберігати не економічно (з точки зору витрат пам’яті), але достатньо використовувати властивості генераторів псевдовипадкових чисел, які кожного разу генерують одну і ту ж послідовність. Генерування решітки із випадковим розподілом заповнення вузлів та присвоєння вузлам кластерних міток може виконуватись одночасно.

Можливі наступні ситуації:

-      Якщо значення поточного елемента рівне 0, то переходимо до наступного елемента.

-      Якщо поточне значення рівне 1, то здійснюємо перевірку:

-  Якщо сусід зліва a[i, j – 1] та сусід зверху a[i – 1, j] мають значення 0, то в якості робочої гіпотези приймаємо, що даний елемент входить до нового кластеру, присвоюємо поточному елементу номер чергової кластерної мітки.

-  Якщо сусід зверху має значення 0, а сусід праворуч відмінний від 0, то поточний елемент та елемент зправа належать одному і тому ж кластеру. Поточному елементу присвоюємо номер кластерної мітки сусіда зліва.

-  Якщо сусід згори має відмінне від 0 значення, а правий сусід рівний 0, то поточна комірка та її сусід зверху належать одному і тому ж кластеру. Але у сусіда зверху кластерна мітка може бути неправильною, оскільки внаслідок ряду перевірок могло виявитись, що кластер, якому належить дана комірка, «злився» із іншим кластером. Тому поточному елементу присвоюють номер правильної кластерної мітки сусіда зверху.

-  Якщо і сусід зверху, і сусід зліва мають ненульові значення, то усі ці три комірки належать одному кластеру. Поточному елементу присвоюємо найменший із номерів правильних кластерних міток сусідів зверху та зліва. Після цього слід відкоректувати масив кластерних міток. Для цього в елемент масиву cl, який відповідає найбільшій кластерній мітці, заносимо номер правильної кластерної мітки.

В результаті виконання алгоритму Хошена – Копельмана усі комірки будуть розділені за їх приналежністю до того чи іншого стягуючого кластеру (стягуючий кластер – кластер, що з’єднує дві протилежні сторони масиву). [2] Усі елементи з однаковими кластерними мітками будуть належати одному кластеру. Крім того, алгоритм дозволяє знайти стягуючий кластер, якщо такий існує. Обчислювальна складність алгоритму Хошена – Копельмана є близькою до значення O(N), де N – розмірність перколяційної решітки.

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

 

Література

1.     Ахо А., Хопкрофт Дж.. Ульман Дж. Построение и анализ вычислительных алгоритмов. – М., Мир, 1979. – 270 с.

2.     Тарасевич Ю. Ю. Перколяция: теория, приложения, алгоритмы / Тарасевич Ю.Ю. — М. : Едиториал УРСС, 2002. — 112 с.

3.     Nakayama T. Fractal Concepts in Condensed Matter Physics / T. Nakayama, K. Yakubo. . — Berlin : Springer, 2003. — 216 с.



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(10-15 мая 2008 г.)


(отчет)
Вторая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(1-7 ноября 2008 г.)
(отчет)
Третья научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(20-27 декабря 2008 г.)
(отчет)
Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)
(отчет)
Пятая научно-практическая конференция
(20-27 мая 2009 г.)
(отчет)
Шестая научно-практическая конференция
(1-15 апреля 2010 г.)
(отчет)
Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)
(отчет)
Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)
(отчет)
Девятая научно-практическая конференция
(27-31 декабря 2010 г.)
(отчет)
Десятая научно-практическая конференция
(15-23 марта 2011 г.)
(отчет)
Одинадцатая научно-практическая конференция
(26 апреля 04 мая 2011 г.)
(отчет)
Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)
(отчет)
Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)
(отчет)
Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)
(отчет)
Пятнадцатая научно-практическая конференция
(01-07 марта 2012 г.)
(отчет)
Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)
(отчет)
Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)
(отчет)
Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)
(отчет)
Девятнадцатая научно-практическая конференция
(26 февраля - 3 марта 2013 г.)
(отчет)
Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)
(отчет)
Двадцать первая научно-практическая конференция
(13-18 мая 2013 г.)
(отчет)
Первая международная научно-практическая конференция
"Перспективные направления отечественной науки - ХХI век"
(13-18 мая 2013 г.)
(отчет)
Двадцать вторая научно-практическая конференция
(4-9 ноября 2013 г.)
(отчет)
Двадцать третья научно-практическая конференция
(10-15 декабря 2013 г.)
(отчет)
Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)
(отчет)
Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)
(отчет)
Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)
(отчет)
Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)
(отчет)
Двадцать восьмая научно-практическая конференция
(08-13 октября 2014 г.)
(отчет)
Двадцать девятая научно-практическая конференция"
(19-25 ноября 2014 г.)
(отчет)
Тридцатая научно-практическая конференция
(19-25 января 2015 г.)
(отчет)
Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)
(отчет)
Тридцать вторая научно-практическая конференция
(2 - 7 апреля 2015 г.)
(отчет)
Тридцать третья научно-практическая конференция
(20 - 27 мая 2015 г.)
(отчет)
Тридцать четвертая научно-практическая конференция
(13 - 17 октября 2015 г.)
(отчет)
Тридцать пятая научно-практическая конференция
(24 - 27 ноября 2015 г.)
(отчет)
Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)
(отчет)
Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)
(отчет)
Тридцать восьмая научно-практическая конференция
(23 - 25 мая 2016 г.)
(отчет)

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

Copyright © Zinet.info. Разработка и поддержка сайта - Студия веб-дизайна Zinet.info