Граф-схема алгоритму

Граф-схема алгоритму (ГСА) — кінцевий зв'язний орієнтований граф ${\displaystyle G=\left\langle A,V\right\rangle }$, вершини якого ${\displaystyle a_{i}\in A,i={\overline {1,N}}}$ відповідають операторам, а дуги ${\displaystyle v_{k}=\left(a_{i},a_{j}\right)\in V,k={\overline {1,M}},i,j={\overline {1,N}}}$ задають порядок проходження вершин (операторів) алгоритму, де ${\displaystyle N=\ left|A\ right|}$ - число вершин графу, ${\displaystyle M=\left|V\right|}$ - число дуг. У ширшому сенсі вершинам графу відповідають не тільки операторні вершини, а й умовні, початкова та кінцева вершини і т.д. При розгляді паралельних алгоритмів вводиться поняття 'паралельної граф-схеми алгоритму' (ПарГСА), до складу якої входять вершини розпаралелювання / синхронізації, функціональність яких зазвичай поєднується. Іноді до складу ГСА вводяться вершини додаткових типів: об'єднання альтернативних дуг (парна вершина для умовної вершини), фіктивні операторні вершини, вершини маркування (з метою забезпечення можливості моделювання виконання алгоритму мережею Петрі), очікувальні вершини.

Очікувальна вершина алгоритму

Однак не будь-який орієнтований граф, складений з вершин зазначених вище типів, може бути ототожнений з коректним алгоритмом. Наприклад, з операторної вершини не може виходити більше однієї дуги. Тому на практиці зазвичай обмежуються розглядом підкласу граф-схем алгоритмів, що задовольняють умовам безпеки, живучості і стійкості Алгоритми перетворення ГСА, які є підмножиною алгоритмів обробки графів загального вигляду, часто мають суттєві відмінності через використання особливих властивостей ГСА, що дозволяє їх спрощення, зниження часової або об'ємної складності.

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

Див. також

• Граф потоку керування

Примітки

1. Ватутін Е.І., Зотов І.В. (2004). (PDF). Известия курського державного технічного університету. Курськ. № 2. С. 85-89. Архів оригіналу (PDF) за 11 вересня 2014. Процитовано 9 вересня 2014.
2. Зотов І.В., Титов В.С., Колоскова В.А. [І ін.] Організація і синтез мікропрограмних мультимікроконтролерів. Курськ: вид-во «Курськ», 1999. 368 с.
3. Ватутін Е.І., Зотов І.В., Титов В.С. [І ін.] Комбінаторно-логічні задачі синтезу розбиття паралельних алгоритмів логічного управління при проектуванні логічних мультиконтролерів. Курськ, вид-во Курського ДТУ, 2010. 200 с.
4. Закревський А. Д.  // Известия АН СРСР. Технічна кібернетика. — 1987. — № 4. — С. 106-112.
5. Ватутін Е.І., Зотов І.В., Титов В.С. (2009). (PDF). Інформаційно-вимірювальні та Керуючий системи. № 11, Т. 7 М.: «Радіотехніка». С. 49-56. Архів оригіналу (PDF) за 10 вересня 2014. Процитовано 9 вересня 2014.

Посилання

• Баранов С.І. Синтез микропрограммное автоматів (граф-схеми та автомат). Л.: Енергія, 1979. 232 с.
• Лазарев В.Г., Пійло Є.І. Синтез керуючих автоматів. М.: Вища школа, 1989. 328 с.
• Автоматне управління асинхронними процесами в ЕОМ і дискретних системах. Под ред. . М.: Наука, 1986. 400 с.
• ГОСТ 19.701-90 [ 31 березня 2022 у Wayback Machine.] (рос.)