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

Файл:Waiting.vertex.png

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

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

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

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

Див. також

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

Примітки

Шаблон:Reflist

Посилання

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

↑ ^1,0 ^1,1 Шаблон:Cite web
↑ Зотов І.В., Титов В.С., Колоскова В.А. [І ін.] Організація і синтез мікропрограмних мультимікроконтролерів. Курськ: вид-во «Курськ», 1999. 368 с. ISBN 5-7277-0253-4
↑ ^3,0 ^3,1 Ватутін Е.І., Зотов І.В., Титов В.С. [І ін.] Комбінаторно-логічні задачі синтезу розбиття паралельних алгоритмів логічного управління при проектуванні логічних мультиконтролерів. Курськ, вид-во Курського ДТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
↑ Шаблон:Стаття
↑ Шаблон:Cite web

[rm-1] 1,0 ^1,1 Шаблон:Cite web

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

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

[4] Шаблон:Стаття

[5] Шаблон:Cite web

[1]

[2]

[3]

[4]

[5]

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

Див. також

Примітки

Посилання

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

Пошук