Про один підхід до структурного аналізу схеми алгоритму

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Про один підхід до структурного аналізу схеми алгоритму

Поліський Юрій Давидович, кандидат технічних наук, старший науковий співробітник, Заслужений винахідник України, Науково-дослідний інститут автоматизації чорної металургії, 49000, м.Дніпро

Анотація

При складанні алгоритму можлива поява у його схемі контурів різної довжини. Відповідно до вимог технології роботи об'єкта в одних випадках ці контури можуть бути необхідні, в інших випадках - небажані. При цьому потрібно знати, які оператори алгоритму входять у ті та інші контури, а також виявити відносини та зв'язки зазначених структурних елементів алгоритму. У ряді робіт запропоновані різні за складністю методи реалізації даної задачі, пов'язані як з мовою опису схеми алгоритму, так і з методикою її аналізу. Результати виконаних досліджень свідчать про можливість отримання більш ефективного рішення, яке дозволяє дещо спростити практичну реалізацію структурного аналізу схеми алгоритму. Метою дослідження є аналітичний розгляд схеми алгоритму виявлення структурних елементів алгоритму та взаємовідносин між ними. При цьому структурними елементами алгоритму є ланцюги, контури та вершини, що належать контурам. Інструментами методології дослідження є системний аналіз, теорія графів та матрична алгебра. Методологія дослідження базується на аналізі матриць суміжності графа алгоритму з виявленням структурних елементів та співвідношень між ними. На першому етапі дослідження на кожній ітерації аналізу виконується виявлення структурних елементів та коригування матриці суміжності, що ілюструється відповідною таблицею. На другому етапі дослідження розглядаються різні варіанти взаємовідносин між виявленими структурними елементами, на підставі чого робиться висновок про можливість чи неможливість працездатності алгоритму. Крім того, наведені умови перемикання режиму роботи з робочого на резервний та навпаки. Запропонований підхід дозволяє дещо спростити практичну реалізацію структурного аналізу схеми алгоритму. Результатом роботи є завершене теоретичне обґрунтування запропонованого підходу до ефективного вирішення задачі структурного аналізу алгоритму. Розглянутий підхід до структурного аналізу схеми алгоритму забезпечує отримання шуканого результату. При цьому представляється доцільним застосувати запропонований підхід в якості перспективного напрямку досліджень схем алгоритмів.

Ключові слова: алгоритм, граф, матриця суміжності, контур, ланцюг

Polissky Yuriy Davydovych, Candidate of Technical Sciences, Senior Research Fellow, Honored Inventor of Ukraine, Research Institute of Automation of Ferrous Metallurgy, 49000, Dnipro

ON ONE APPROACH TO STRUCTURAL ANALYSIS OF ALGORITHM SCHEME

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

Аналіз останніх досліджень і публікацій

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

Формулювання мети дослідження

Метою дослідження є структурний аналіз схеми алгоритму.

Виклад основного матеріалу

Нехай схема алгоритму задана орієнтованим графом D = (V, X) - рис.1, де V = {v = 1, v₂ = 2,v₃ = 3,v₄ = 4, v₅ = 5} -

вершини графа, X = {x = a,x2 = b, x3 = c,x₄ = d, x₅ = e, x₆ = f,x₇ = g, x_s = h, x₉ = k}- дуги графа.

Рис.І.Граф алгоритму

Мета роботи аналізованого алгоритму полягає у переході від початкової вершини 1 до кінцевої вершини 5.

Одні з відомих підходів [1] до структурного аналізу ґрунтуються на матричних алгоритмах, які будуються на базі послідовного зведення у відповідні ступені матриці суміжності. При цьому наявність шляху між і -й та j -й вершинами позначається у матриці 1, відсутність такого шляху 0.

У аналізованому підході матриця суміжності даного графа D = (V, X) -

рис.2 - квадратна матриця порядку n = 5, де

,

а пераціями множення та додавання є логічні операції кон'юнкції та диз'юнкції (v).

Рис.2. Матриця першого порядку

Будемо позначати вихідну матрицю через Д, не відкориговану матрицю - добуток матриць через Д*_,ПД , відкориговану матрицю через Д.

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

З матриці суміжності рис.2 отримуємо к_п = k, K₁₂ = h елементарні контури першого порядку з довжиною дуги, що дорівнює 1, які лежать на головній діагоналі матриці. Вершини графа, що належать контурам, K = k, K = h - це вершина 3 - рядок 3 і стовпець 3 для K = k і вершина 4 - рядок 4 і стовпець 4 для K₂ = h. Дуга а₁₅ = 0, тобто. ланцюг довжиною 1 від вершини 1 до вершини 5 відсутня.

Побудуємо матрицю другого порядку Д = Д _Д - рис.З.

Рис.3.Матриця другого порядку

Як видно з рис.3 всі елементи матриці - ланцюга довжини 2. При цьому на головній діагоналі з'явився елементарний контур другого порядку K₂₁ = db, а також два не елементарні контури другого порядку K₂₂ = kk, K₂₃ = hh . Вершини графа, що належать контуру K₂₁ = db, це вершина 1 - рядок 1 і стовпець 1, вершина 2 - рядок 2 і стовпець 2. Крім того а₁₅ = dg, тобто. з'явився елементарний ланцюг C = dg довжиною 2 від вершини 1 до вершини 5.

Відкоригуємо матрицю Д. Ланцюги а₁₃ = ak, а₂₄ = eh, а₃₃ = kk, а₄₄ = hh не є елементарними, тому їх значення приймаємо рівними нулю. Відкоригована матриця Д ^k показано на рис. 4.

Рис.4. Відкоригована матриця другого порядку

Побудуємо матрицю третього порядку D3 = D²_k D₁ - рис.5.

Рис.5. Матриця третього порядку

Як видно з рис.5 всі елементи матриці - ланцюга довжини 3. При цьому на головній діагоналі з'явилися два елементарні контури третього порядку K₃₁ = acb і K₃₂ = def. Вершини графа, що належать контуру K₃₁ = acb, це вершина 1 - рядок 1 і стовпець 1, вершина 2 - рядок 2 і стовпець 2, вершина 3 - рядок 3 і стовпець 3. Вершини графа, що належать контуру K₃₂ = def, це вершина 1 - рядок 1 і стовпець вершина 2 - рядок 2 та стовпець 2, вершина 4 - рядок 4 та стовпець 4.

Крім того, a₁₅ = acg , тобто. з'явився елементарний ланцюг довжиною 3 від вершини 1 до вершини 5.

Відкоригуємо матрицю D. Ланцюги

a₁₂ = dbd, a₁₄ = deh, a₂₁ = bdb, a₂₃ = bak, a₃₂ = cbd, a₃₄ = ceh, a₄₁ = fdb не є елементарними, тому їх значення приймаємо рівними нулю. Відкоригована матриця D^к показано на рис. 6.

Рис.6. Відкоригована матриця третього порядку

Побудуємо матрицю четвертого порядку D3 = D²_k D₁ - рис.7.

Рис.7. Матриця четвертого порядку

Як видно з рис.7 всі елементи матриці - ланцюга довжини 4. При цьому на головній діагоналі з'явився елементарний контур четвертого порядку К₄₁ = acef.

Вершини графа, що належать контуру, це вершина 1 - рядок 1 та стовпець 1, вершина 2 - рядок 2 та стовпець 2, вершина 3 - рядок 3 та стовпець 3, вершина 4 - рядок 4 та стовпець 4.

Відкоригуємо матрицю D_A. Ланцюги

a_n = acbd v defd, a13 = dbac, a_u = aceh, a21 = efbd v bacbv bdef, a23 = efde v bdef, a32 = cefd v cbac, a33 = cbak, a41 = fcb v fdf, a44 = fdeh.

не є елементарними, тому їх значення приймаємо рівними нулю. Відкоригована матриця D₄ показана на рис. 8.

Рис.8. Відкоригована матриця четвертого порядку Побудуємо матрицю п'ятого порядку D3 = D²_k D₁ - рис.9.

Рис.9.Матриця п'ятого порядку

Як видно з рис.9 всі елементи матриці - ланцюга довжини 5, на головній діагоналі нові елементарні контури відсутні, а також відсутні елементарні ланцюги, що ведуть початкової до кінцевої вершини графа.

Для перевірки збіжності розглянутого методу відкоригуємо матрицю D₅. Ланцюги a₁₃ = acefa, а₂₄ = eface v baceh, a₃₂ = cefac, а₃₃ = cefak, а₄₁ = facef, a₄₄ = faceh. не є елементарними, тому їх значення приймаємо рівними нулю. Відкоригована матриця Dk показана на рис. 10.

Рис.10. Відкоригована матриця п'ятого порядку

Побудована на її основі матриця D₆ = 0, що доводить збіжність методу.

Таким чином, в результаті першого етапу аналізу виявлені елементарні контури K = k, K = h ,, К₂₁ = db , К₃₁ = acb , К₃₂ = def, К₄₁ = acef і елементарні ланцюги C = dg, C₂ = acg переходу від початкової до кінцевої вершини.

У ряді випадків робота об'єкта потребує наявності контурів у схемі алгоритму. Нехай за умов завдання потрібно виключити контур К₂₁ = db при збереженні контурів К₃₁ = acb і К₃₂ = def. Цю вимогу можна висловити системою рівнянь

З першого та другого рівнянь випливає b = 1 і d = 1 . Проте за третім рівнянням bd = 0. Отже, система рівнянь не сумісна, і за таких умов завдання алгоритм не може бути реалізований.

Нехай за умов завдання потрібно виключити контур acef при збереженні контурів К₃₁ = acb, К₃₂ = def і К₂₁ = db . Цю вимогу можна висловити системою рівнянь

З другого та третього рівнянь випливає відповідно ac = 1 і ef = 1 . Проте за першим рівнянням acef = 0. Отже, система не сумісна, і за таких умов завдання алгоритм не може бути реалізований.

Нехай за умов завдання потрібно виключити всі контури. Введемо позначення - S_p6 робочий режим. Цю вимогу можна висловити системою рівнянь

З першого рівняння d = 1. Підстановка у друге рівняння дає b = 0. Підстановка d = 1 у четверте рівняння дає ef = 0. При цьому ac можливо як ac = 0 , так і ac = 1. Отже, система сумісна, і за таких умов завдання алгоритм реалізується.

Позначимо S - резервний режим.

З першого рівняння ac = 1. Підстановка ac = 1 в третє та п'яте рівняння дає відповідно b = 0 і ef = 0. При цьому d можливо як d = 0, так і d = 1. Система рівнянь сумісна та алгоритм реалізується.

Нехай R - сигнал перемикання режиму роботи.

Тоді

Висновки

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

Література:

1.Кононюк А.Е. Дискретно-непрерывная математика. /А.Е.Кононюк -- К.: Освіта України. 2015. -- 512 с.

References:

l.Kononjuk A.E. (2015). Discretno-neprerivnaja matematika [Discrete-continuous mathematics]. K.: Osvita Ukraini [in Ukrainian]

Размещено на Allbest.ru