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 грн!

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



ПРОГРАМНА РЕАЛІЗАЦІЯ ДЕЯКИХ АЛГОРИТМІВ НА ЧИСЛОВИХ ГРАФАХ

 

Гришанович Т.О.

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

Волинський національний університет імені Лесі Українки

 

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

 

Візуалізація складних концептуальних структур є однією із ключових компонент у багатьох прикладних галузях науки та техніки. І саме графи є тим апаратом, який дозволяє змоделювати такі структури та наочно представити досить складні об’єкти і зв’язки між ними Для графів існує декілька основних способів представлення у машинній пам’яті: матриці суміжності, списки суміжності, матриці інцидентості. Вибір найкращого із представлень визначається вимогами конкретної задачі. Вищеназвані способи представлення графів вимагають, як правило, значної кількості пам’яті, а, отже, громіздких обчислень та великих витрат часу. Тому досить ефективним є використання числових графів [4]. І оскільки представлення графів у вигляді числових значно відрізняється від традиційних способів їх подання, виникає потреба у розробці алгоритмів саме для числових графів.

У цій роботи описано програмну реалізацію алгоритму розкладання графів за допомогою їхніх кістяків та алгоритми відшукання гамільтонових циклів на натуральних арифметичних графах. Детальний опис алгоритму декомпозиції графа наведено у [2], алгоритмів відшукання гамільтонових циклів – у [3] і тому у даній роботі на них зупинятись не будемо. Більшу вагу доцільно звернути на методи та засоби реалізації цих алгоритмів.

Першим питанням, яке виникло у процесі програмування алгоритмів, був вибір мови програмування. На даний час існує чимало об’єктно-орієнтованих систем. Кожна з них має свої переваги і недоліки та використовується для розв’язання певного кола задач. Якщо враховувати всі вимоги до засобів розробки, а також практично доступні системи програмування комерційної якості, то вибір значно звужується і залишаються три системи програмування С++, Delphi та Visual Basic. Прийнявши до уваги суб’єктивні фактори - важкість освоєння, швидкість згенерованого програмного коду та вимоги до розроблюваного продукту – в першу чергу міркування простоти використання, можливості переносу проекту в інші середовища програмування, то вибір був здійснений на користь середовища Delphi. Delphi орієнтоване на повний процес розробки програм, що включає проектування алгоритму, генерацію та модифікацію коду програми. [1]

Ще одним питанням, що виникає при розробці алгоритмів для опрацювання графів, є візуалізація. Зображення графа на площині – це відображення вершин і ребер на множині точок площини. Зрозуміло, що один і той же граф можна зобразити багатьма способами. Поняття якісного способу зображення графа формалізується за допомогою таких понять, як образотворче узгодження, естетичність та обмеження. [5]

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

Таким чином на основі вимог та узгоджень, які ставляться до програмних засобів для роботи із графами, було розроблено програмний продукт, який розкладає натуральні арифметичні графи за їх вершинами (за алгоритмом розкладання графів за допомогою їх кістяків) та здійснює відшукання гамільтонових графів на числових графах (за алгоритмом з поверненням, Approx-TSP(G) та алгоритмом із поліноміальним часом).

Програма має багато віконний інтерфейс. Вікно «Розкладання графів» має наступний вигляд:

 

 

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

Вікно «Гамільтонові цикли» має наступний вигляд:

 

 

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

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

 

Література

1.    Басюк Т.М. Етапи проектування системи моделювання та візуалізації графів / Т. М. Басюк // Восточно-Европейский журнал передовых технологий. — 2005. — № 2/2(14). C. 65—67.

2.    Гришанович Т. О. Алгоритм розкладання графів за допомогою їхніх кістяків / Т. О. Гришанович // Теоретична електротехніка. — 2009. — №60. — С. 12—20.

3.    Гришанович Т.О. Про відшукання гамільтонових циклів на числових графах / Т. О. Гришанович // «Теоретичні та прикладні аспекти кібернетики», 21 – 25.02.2011, Київ. С.8081

4.    Донец Г.А. Об общем представлении числових графов / Г.А. Донец, И.Е. Шулинок // Теорія оптимальних рішень. — 2004. — №3. — С.18—25.

5.    Касьянов В.Н. Графы в программировании: обработка, визуализация и применение / В.Касьянов, В. Евстигнеев. — С.Пб. : БХВ-Петербург, 2003. — 1104с.



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХ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