Граф-схема алгоритму
Чекає вершина алгоритму
Граф-схема алгоритму (ДСА) - кінцевий зв'язний орієнтований граф G = ⟨A. V⟩. вершини якого a i ∈ A. i = 1. N ¯ \ in A, i = >> відповідають операторам, а дуги v k = (a i. a j) ∈ V. k = 1. M ¯. i. j = 1. N ¯ = \ left (a_, a_ \ right) \ in V, k =>, i, j = >> задають порядок проходження вершин (операторів) алгоритму, де N = | A | - число вершин графа, M = | V | - число дуг. У більш широкому сенсі вершин графа відповідають не тільки операторні вершини, а й умовні, початкова і кінцева вершини і т. Д. При розгляді паралельних алгоритмів вводиться поняття паралельної граф-схеми алгоритму (ПарГСА), до складу якої входять вершини розпаралелювання / синхронізації, функціональність яких зазвичай поєднується. Іноді [1] [2] [3] до складу ДСА вводяться вершини додаткових типів: об'єднання альтернативних дуг (парна вершина для умовної вершини), фіктивні операторні вершини, вершини маркування (з метою забезпечення можливості моделювання виконання алгоритму мережею Петрі), що чекають вершини.
Однак не будь-який орієнтований граф, складений з вершин зазначених вище типів, може бути ототожнений з коректним алгоритмом. Наприклад, з операторної вершини не може виходити більше однієї дуги. Тому на практиці зазвичай обмежуються розглядом підкласу граф-схем алгоритмів, які відповідають властивостям безпеки, жвавості і стійкості. [4] Алгоритми перетворення ДСА, що є підмножиною алгоритмів обробки графів загального вигляду, часто мають істотні відмінності щодо використання особливих властивостей ДСА, що дозволяє їх спрощення, зниження тимчасової або ємнісний складності. [1] [3] [5]
У складі граф-схеми алгоритму можуть бути виділені більш великі елементи, представлені підмножинами її вершин і дуг: гілки (лінійні ланцюжка або ділянки вершин) і фрагменти (початковий, паралельний, альтернативний, циклічні з перед-, постусловіем і перериванням). Еквівалентним поданням граф-схеми коректного алгоритму є дерево фрагментів, що відображає порядок вкладеності фрагментів.
- Баранов С. І. Синтез мікропрограмних автоматів (граф-схеми і автомати). Л. Енергія, 1979. 232 с.
- Лазарєв В. Г. Пійло Е. І. Синтез керуючих автоматів. М. Вища школа, 1989. 328 с.
- Автоматне управління асинхронними процесами в ЕОМ і дискретних системах. Під ред. В. І. Варшавського. М. Наука, 1986. 400 с.
- гост