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]

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

У цій роботі ми розглянемо алгоритм розв’язання однієї із найбільше практично-значущих задач на графах – задачу розкладання (розфарбовування, декомпозиції0 графу за його вершинами, а також звернемось до часової ефективності такого алгоритму. В якості способу представлення графу будемо розглядати натуральні арифметичні графи.

У роботі [2] уже було сформульовано задачу розкладання натурального арифметичного графу на мові 0-1 – програмування. З цієї причини зупинимось на описі такого алгоритму лише на мові псевдокоду.

Для цього введемо основні позначення: xi, yi – змінні задачі розкладання, Х, Y – значення відповідних цільових функцій,  – верхня оцінка для Y,  – значення лівих обмежень, ,  – параметри збіжності, Ij – індекси рядків із ненульовими коефіцієнтами для стовпця j.

Вхід: n – кількість вершин графу, m – множина твірних.

Вихід: Хоптимальний розв’язок задачі розкладання.

   

     

  

repeat for all j:  do

while  and  do ,

for all  do

  

   

end for

end while

   

until  return Х

Перейдемо до обчислення часової ефективності запропонованого алгоритму. Часом роботи алгоритму називатимемо число елементарних кроків, які він виконує. Вважатимемо, що елементарним кроком є один пункт алгоритму, але у тому випадку, коли він не містить вказівок такого роду, як «відсортувати масив за зростанням». Насамперед нас буде цікавити час роботи Т таких алгоритму в найгіршому випадку з огляду на наступне:

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

·       На практиці «погані» входи (для яких час роботи близький до максимального) можуть траплятись досить часто.

·       Середній час роботи може бути дуже близьким до часу роботи у найгіршому випадку.

При оцінці складності алгоритму будемо використовувати наступну теорему [5]:

Теорема: Якщо А(k)=amkm+…+a1k1+a0 є поліномом степеня m, тоді А(k)=O(km).

З огляду на вищезазначені припущення та використавши рівномірний ваговий критерій для отримання часу виконання алгоритму, отримаємо наступне значення оцінки часової ефективності описаного алгоритму розкладання натурального арифметичного графу за його вершинами для дискретного програмування: О(n2).

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

 

Література

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

2.   Гришанович Т.О. Формулювання задачі вершинного розфарбування арифметичного графу на мові 0-1 – програмування / Т.О. Гришанович // Міжнародна науково-практична конференція «Математика. Інформаційні технології. Освіта», 3-50.06 2013, Луцьк. С.27—29.

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

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

5.   Кормен Т. Алгоритмы. Построение и анализ / Т. Кормен, Ч. Лейзерю – М : МЦРМО,2002. – 680с.



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