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

Файл:Waiting.vertex.png

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

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

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

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

Див. також

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

Примітки

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

Посилання

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

[rm-1] а ^б Ватутін Е.І., Зотов І.В. (2004). Побудова матриці відносин в задачах оптимального розбиття паралельних керуючих алгоритмів (PDF). Известия курського державного технічного університету. Курськ. № 2. С. 85-89. Архів оригіналу (PDF) за 11 вересня 2014. Процитовано 9 вересня 2014.

[2] Зотов І.В., Титов В.С., Колоскова В.А. [І ін.] Організація і синтез мікропрограмних мультимікроконтролерів. Курськ: вид-во «Курськ», 1999. 368 с. ISBN 5-7277-0253-4

[mono-3] а ^б Ватутін Е.І., Зотов І.В., Титов В.С. [І ін.] Комбінаторно-логічні задачі синтезу розбиття паралельних алгоритмів логічного управління при проектуванні логічних мультиконтролерів. Курськ, вид-во Курського ДТУ, 2010. 200 с. ISBN 978-5-7681-0523-5

[4] Закревський А. Д. // Известия АН СРСР. Технічна кібернетика. — 1987. — № 4. — С. 106-112.

[5] Ватутін Е.І., Зотов І.В., Титов В.С. (2009). виявлення ізоморфних входжень R-виразів при побудові множини перетинів паралельних алгоритмів логічного Управління (PDF). Інформаційно-вимірювальні та Керуючий системи. № 11, Т. 7 М.: «Радіотехніка». С. 49-56. Архів оригіналу (PDF) за 10 вересня 2014. Процитовано 9 вересня 2014.

[1]

[2]

[3]

[4]

[5]

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

Див. також

Примітки

Посилання

Навігаційне меню

Пошук