УДК 519.17

Z. Kokosiński
Cracow University of Technology, Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Kraków, Poland

PARALLEL METAHEURISTICS IN GRAPH COLORING

 Kokosiński Z., 2012
In this survey paper applications of parallel metaheuristics to solving graph coloring problems are described. The Graph Coloring Problem (GCP), Graph Coloring Sum Problem (GCSP) and Robust Graph Coloring Problem (RGCP) are known to be NP-complete. They do not have any polynomial algorithms. Therefore, a number of approximation, iterative and hybrid algorithms was developed for their solving. Recently a number of parallel algorithms was proposed for GCP and related coloring problems, including parallel metaheuristics like Parallel Genetic Algorithm (PGA), Parallel Tabu Search (PTS), Parallel Simulated Annealing (PSA) etc. DIMACS benchmarks as well as random graphs were used for their experimental verification. The results obtained for GCSP contributed to finding better lower and upper bounds on chromatic sum and chromatic sum number for many DIMACS graph instances, outperforming results known from the literature. The reported data support a conclusion, that parallel metaheuristics can be used efficiently for approximate solving of many graph coloring problems and for finding better upper bounds of many hard-to-compute graph parameters.
Key words: graph coloring, graph coloring sum, robust graph coloring, parallel metaheuristics, parallel iterative algorithms, chromatic sum, chromatic sum number.

Наведено огляд застосувань паралельних метаевристик для вирішення проблем колоризації графів. Проблеми колоризації графів (GCP), сумарної колоризації графів (GCSP) та робастної колоризації графів (RGCP) є NP-повними і не мають поліно¬міаль¬них алгоритмів. З цієї причини для різних варіантів основної проблеми колоризації графів розроблено багато наближених алгоритмів, ітераційних і гібридних. Останнім часом для задачі колоризації графів і подібних їй проблем були розроблені паралельні алгоритми, зокрема паралельні метаевристики, зокрема паралельний алгоритм табу пошуку (PTS), паралельний генетичний алгоритм (PGA) і паралельний алгоритм іміта¬ції відпалу (PSA). В експериментальній перевірці алгоритмів використано графи зі сховищем DIMACS, а також випадкові графи. Дослідження застосування PGA для задач сумарної колоризації спричинило визначення нових верхніх і нижніх оцінок хроматичної суми і числа хроматичної суми для класу тестів з бази DIMACS, які є точні¬шими від відомих теоретичних оцінок. Отримані результати підтверджують думку, що паралельні метаевристики можуть стати потужним інструментом для наближеного розв’язування задач колоризації графів у практичних застосуваннях, а також для експериментального визначення верхньої оцінки обраних параметрів важко обчислювальних графів.
Ключові слова: колоризація графів, сумарна колоризація, робастна колори¬зація, паралельна метаевристика, паралельний ітераційний алгоритм, хроматич¬на сума, число хроматичної суми.

Кількість посилань 43.

УДК 004.032.26

Є. Бодянський, О. Винокурова
Харківський національний університет радіоелектроніки,
проблемна науково-дослідна лабораторія АСУ

АДАПТИВНИЙ W-НЕЙРОН ТА ЙОГО НАВЧАННЯ В ЗАДАЧАХ ПРОГНОЗУВАННЯ І ВИЯВЛЕННЯ РОЗЛАДНАНЬ

© Бодянський Є., Винокурова О., 2012

Розглянуто структуру адаптивного W-нейрона та його метод навчання. Запропонований алгоритм навчання має підвищену швидкість збіжності та забезпечує покращені апроксимуючі властивості за рахунок настроювання усіх параметрів вейвлет-функцій. Введена підсистема виявлення розладнань для W-нейрона, що дає змогу розв’язувати задачі діагностування в on-line режимі стохастичних процесів.
Ключові слова: W-нейрон, методи навчання, прогнозування, виявлення розладнань.

Adaptive W-neuron and its learning algorithm are considered. Proposed learning algorithm has increased convergence rate and provides improved approximative properties because of the all wavelet parameters tuning. The fault detection subsystem for W-neuron that allows to solve a stochastic process diagnosing problems in on-line mode.
Key words: W-neuron, learning algorithm, prediction, fault detection.

Література – 25

УДК 681.3

Н. Бойко
Львівська комерційна академія,
кафедра програмних засобів інформатики

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

© Бойко Н., 2012

Розкрито сучасне розуміння феномена інформаційного суспільства, подані показники, тенденції й прогнози впровадження інформаційних технологій у світі та його вплив на глобальний розвиток. У цьому контексті розглянуто соціокультурні зрушення в Україні, безпосередньо пов’язані зі впровадженням і використанням інформаційних технологій, зокрема: поширення нових форм масової комунікацій, трансформація та розвиток систем «цифрової» демократії та електронного урядування, сучасних технологій. Розкрито стан проблеми розвитку інформаційних технологій. Запропоновані відповідні прогнози та рекомендації.
Ключові слова: інформаційні технології, сховища даних, WАР-технології, ІР-телефонія, системи штучного інтелекту, комунікації, Інтернет, інформаційні системи, інформаційно-комунікаційні технології.

The article opened modern understanding of the Information Society, presented indicators, trends and forecasts implementation of information technology in the world and its impact on global development. In this context, consider the sociocultural developments in Ukraine is directly related to the implementation and use of information technologies, in particular the spread of new forms of mass communication, transformation and development systems "digital" democracy and e-governance and modern technology. Solved problem state of information technology. Appropriate forecasts and recommendations.
Key words: information technology, data storage, WAR technology, IP telephony, artificial intelligence, communications, Internet, information systems, information and communication technology.

Кількість посилань 13.

УДК 519.81+519.863+004.942

О. Верес, Ю. Верес
Національний університет “Львівська політехніка”,
кафедра інформаційних систем та мереж

розподіл обмежених ресурсів засобами СППР

© Верес О., Верес Ю., 2012

Описано методології планування потреб у ресурсах. Проаналізовано програмні комплекси систем розподілу ресурсів і обґрунтовано потребу в розробленні своєї системи підтримки прийняття рішень. Проведено тестування прототипу СППР розподілу обмежених ресурсів, яка реалізує розроблені моделі та алгоритми.
Ключові слова: метод аналітичної ієрархії, обмежений ресурс, пріоритет, прийняття рішень, система підтримки прийняття рішень.

In the article describes the methodology of planning resource needs. The analysis of software systems and resource allocation systems proved the need to develop their decision support systems. Testing of the prototype DSS allocation of scarce resources, implementing the developed models and algorithms.
Key words: analytic hierarchy method, limited resources, priority, decision-making, Decision Support System.

Кількість посилань 11.

УДК 81:004.93

В. Висоцька, Т. Шестакевич, Ю. Щербина*
Національний університет “Львівська політехніка”,
кафедра інформаційних систем та мереж,
*Львівський національний університет імені Івана Франка,
кафедра дискретного аналізу та інтелектуальних систем

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

© Висоцька В., Шестакевич Т., Щербина Ю., 2012

Описано застосування породжувальних граматик у лінгвістичному моделюванні. Подані в роботі моделі синтаксису речення застосовують для автоматизації процесів аналізу та синтезу природномовних текстів.
Ключові слова: породжувальні граматики, структурна схема речення, комп’ютерна лінгвістична система.

This paper describes the generative grammar application in linguistic modelling. Presented in work of syntax sentence models is applied to automate the processes of analysis and synthesis of texts in natural language.
Key words: Generative grammar, structured scheme sentences, computer linguistic system.

Література – 25

УДК 681.14

Ф. Гече1, В. Коцовський1, А. Батюк2
1Ужгородський національний університет,
2Національний університет “Львівська політехніка”

СПЕКТРАЛЬНІ ВЛАСТИВОСТІ БУЛЕВИХ ФУНКЦІЙ, РЕАЛІЗОВНИХ ОДНИМ НЕЙРОННИМ ЕЛЕМЕНТОМ І СУМАТОРАМИ ЗА МОДУЛЕМ 2

© Гече Ф., Коцовський В., Батюк А., 2012

Розроблено методи синтезу комбінаційних схем із одного нейронного елемента та суматорів за модулем 2. Встановлено ті основні перетворення у спектральній області булевих функцій, за допомогою яких мовою характеристичних векторів можна встановити реалізованість булевих функцій комбінаційною схемою з одного нейронного елемента та суматорів за mod 2.
Ключові слова: ядро булевої функції, матриця толерантності, комбінаційна схема, спектр булевої функції.

We give new algorithms for the synthesis of the combinational circuits including one threshold device and binary adders. We show how we can use the characteristic vectors for checking the realizability of the Boolean function on such circuits.
Key words: the Boolean function kernel, tolerance matrix, combinational circuit, the spectrum of Boolean function.

Література – 5

УДК 621.64.029

О. Гринів, Н. Притула, М. Притула
Центр математичного моделювання ІППММ ім. Я.С. Підстригача НАН України,
ТОВ “Математичний центр”

МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ОПТИМІЗАЦІЯ СУМІСНОЇ РОБОТИ ГАЗОСХОВИЩ

© Гринів О., Притула Н, Притула М., 2012

Розглянута проблема оптимізації сумісної роботи газосховищ у складі газотранспортної системи України. Поставлені задачі і запропоновано алгоритми їх розв’язування. Отримані попередні оцінки потенціалу оптимізації роботи газосховищ та факторів впливу на величину таких оцінок.
Ключові слова: фільтрація, математична модель, оптимізація, газосховище, режим роботи, технологічна схема.

In this paper, we consider the problem of optimization of compatible work of gas storages as a part of the gas transport system of Ukraine. We have carried out statements and have offered the algorithms of their solving. We have also received the previous estimates of potential of optimization of work of gas storages and factors of influence on size of such estimates.
Key words: filtration, mathematical model, optimization, gas storage, operating mode, technological scheme.

Кількість посилань 6.

УДК 004.4’232

Я. Драґан1, В. Овсяк2, О. Овсяк3
1Національний університет “Львівська політехніка”,
кафедра програмного забезпечення
2Українська академія друкарства,
3Київський національний університет культури і мистецтв, Львівська філія

МЕТОДОЛОГІЯ СИНТЕЗУ МОДЕЛЕЙ АЛГОРИТМІЧНОЇ СКЛАДОВОЇ АВТОМАТІВ

© Драґан Я., Овсяк В., Овсяк О., 2012

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

There is describe by the stages of synthesis, optimization and study mathematical models of machine algorithmic component by the methods of algorithm algebra, decomposition and mathematical induction..
Key words: method, methodology, model, information technology, decomposition, sequentization, elimination, parallelization, function uniterm, uniterm.

Кількість посилань 11.

УДК 01.05.02; 05.13.06; 05.13.21

А. Ковальчук, Д. Пелешко, *Ю. Борзов
Національний університет “Львівська політехніка”,
кафедра ІТВС,
*Львівський державний університет безпеки життєдіяльності,

ВИКОРИСТАННЯ ПОБІТОВИХ ОПЕРАЦІЙ І ДОДАТКОВОГО ЗАШУМЛЕННЯ В АЛГОРИТМІ RSA ПРИ ШИФРУВАННІ–ДЕШИФРУВАННІ ЗОБРАЖЕНЬ

© Ковальчук А., Пелешко Д., Борзов Ю , 2012

Література – 5

УДК 681.84.087.4

О. Кузьмін1, А. Ковальчук2, Р. Ступень3
Національний університет “Львівська політехніка”,
1кафедра менеджменту і міжнародного підприємництва,
2кафедра інформаційних технологій видавничої справи,
3кафедра менеджменту персоналу та адміністрування

РОЗДІЛЕННЯ ТЕРИТОРІЇ НА ЕКОНОМІЧНІ СКЛАДОВІ В УМОВАХ НЕВИЗНАЧЕНОСТІ

 Кузьмін О., Ковальчук А., Ступень Р., 2012

Запропоновано модель розподілу території на економічні зони з використанням методів теорії нечітких множин.
Кючові слова: економічна зона, територія, нечітка множина, модель.

Model of separation of territory on economic zones with by use of methods of the theory of fuzzy sets is offered.
Key words: economic zone, area, fuzzy sets, model.

Кількість посилань 1.

УДК 004.7

О. Леонтьєва*, К. Обельовська
*TeleConsult-Austria GmbH, Schwarzbauerweg, 3, A-8043, Graz, Austria
Національний університет “Львівська політехніка”,
кафедра автоматизованих систем управління

ПОРІВНЯННЯ ПРОПУСКНИХ ЗДАТНОСТЕЙ СХЕМ ДОСТУПУ DCF ТА EDCA БЕЗПРОВІДНИХ ЛОКАЛЬНИХ МЕРЕЖ

© Леонтьєва О., Обельовська К., 2012

Проведено порівняльний аналіз пропускної здатності двох схем доступу безпровідних мереж DCF та EDCA в умовах насиченої завантаженості.
Ключові слова: безпровідні мережі, DCF, EDCA, пропускна здатність.

This paper is devoted to the comparison analysis of wireless networks access schemes DCF and EDCA in case of saturation condition.
Key words: wireless networks, DCF, EDCA, throughput.

Література – 4

УДК 004.9

О. Матвійків, Б. Дмитришин
Національний університет “Львівська політехніка”,
кафедра САПР

ПАСИВНИЙ Т-МІКРОМІКСЕР З БАР’ЄРАМИ ДЛЯ ЛАМІНАРНОГО ПОТОКУ

© Матвійків О., Дмитришин Б., 20132

Змішування в пасивних мікроміксерах залежить від їх геометрії. Отже, багато пасивних мікроміксерів ефективні тільки при великих числах Рейнольдса і вимагають складної структури каналів. Наведено можливості вдосконалення структури Т-мікроміксера для змішування двох рідин з введенням бар'єрів у мікроканалі. У дослідженні ми змінюємо 3 параметри: висоту бар'єра, зсув бар'єра від центру каналу та форму бар'єра. Модель демонструє високу ефективність змішування навіть при малих числах Рейнольдса Re = 0,1. Модифікований Т-мікроміксер можна легко інтегрувати в різноманітні лабораторії на чипах (ЛНЧ) або мікросистеми повного аналізу (МПА).
Ключові слова: мікропотоки, лабораторія на чипі, мікросистеми повного аналізу, числа Рейнольдса, змішування, Т-мікроміксер, ламінарний потік.

Mixing in the passive micromixers depends on their geometry. Thus many passive micromixers are effective only at high Reynolds numbers and require a complex structure of channels. The article presents the possibility of improving the structure of T-micromixer for mixing two fluids with barriers. In our investigation we change 3 parameters: barrier height, barrier offset from the centre of the channel and barrier shape. The model shows high efficiency of mixing even at low Reynolds numbers Re = 0,1. Modified T-micromixer can be easily integrated into various labs-on-chip (LOC) or micro-total-analysis systems (µTAS).
Key words: Microfluidics, lab-on-chip (LOC), micro-total-analysis systems (µTAS), Reynolds number, mixing, T-shape micromixer, laminar flow.

Література – 3

УДК 004.932.2

Г. Мельник
Тернопільський національний економічний університет,
кафедра комп’ютерної інженерії

МЕТОД ЗНАХОДЖЕННЯ ВІДПОВІДНИХ ТОЧОК НА КОНТУРАХ МІКРООБ’ЄКТІВ БІОМЕДИЧНОЇ ПРИРОДИ

© Мельник Г., 2012

Характерною властивістю цифрових біомедичних зображень є наявність повторюваних елементів з нечіткою геометричною структурою. Наближення форми клітин до форми круга або еліпса вимагає вдосконалення алгоритмів зіставлення областей. Для визначення найкращого афінного перетворення між областями використано симетричну різницю множин точок областей. Застосуванням дискретних центральних моментів області підвищено точність визначення відповідних точок на контурах при визначенні афінних перетворень між областями мікрооб’єктів.
Ключові слова: біомедичні зображення, структурний аналіз, зіставлення областей, центральні моменти, контур, відповідні точки.

The characteristic feature of digital biomedical images is presense of repeated elements with fuzzy geometry. Cell shape is approximately equals to shape of circle or ellipse. It demands an improved algorithms for region matching. The symmetric difference of regions point sets used to determine the best affine transformation between the regions. Application of region discrete central moments increases the accuracy of contours corresponding points during calculation of affine transformations between the regions of microobjects.
Key words: biomedical image, structural analysis, region matching, central moments, contour, correspondence points.

Література – 16

УДК 004.4’232

В. Овсяк, М. Козелко
Українська академія друкарства

МОДЕЛЬ КОНВЕРТАЦІЇ АБСТРАКТНИХ УНІТЕРМІВ ДО ТИПОВИХ ГРАФІЧНИХ УНІТЕРМІВ-АВТОМАТІВ

© Овсяк В., Козелко М., 2012

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

Means algebra of algorithms described created a model of the system default image unitermiv designed to convert abstract uniterm.
Key words: system, model uniterm graphic, abstract graphic uniterm, algorithm.

Література – 11