Граф-схеми алгоритмів (ГСА)

При програмній реалізації в якості мови специфікацій автоматів часто використовуються граф-схеми алгоритмів (ГСА). Для задач розглянутого класу вони можуть містити в операторних вершинах присвоєння вихідним змінним або булевих формул, або констант 0 та 1. В першому випадку ГСА досить важко читаються, а в другому – можливі два різновиди: вершина містить або всі вихідні змінні, або тільки вихідні змінні, що змінюються. У випадку якщо кожна вершина містить всі змінні, то ті з них, які приймають значення, рівні нулю, можуть не вказуватися за замовчуванням. Це повинно враховуватися в описі ГСА, що часто не виконується в призводить до неоднозначності в розумінні їх роботи. Умовні вершини можуть бути із двома виходами в з багатьма виходами. У першому випадку ці вершини можуть містити або окремі змінні, або окремі булева формули, а в другому – вони позначаються системами булевих формул. Найбільш просто читаються ГСА з умовними вершинами, що містять тільки одиночні змінні. ГСА відрізняються також і числом операторів. Якщо при апаратній реалізації «введення» передбачається в кожній умовній вершині із вхідними змінними, а «вивід» – у кожній операторній вершині з вихідними змінними, то при програмній реалізації потрібно, щоб ГСА містила лише по одному зазначеному оператору. Якщо при апаратній реалізації в ГСА припустимі повернення назад, то при програмній реалізації, при виконанні обчислювачем більш ніж одного алгоритму, повинна існувати лише один зовнішній зворотний зв'язок.

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

Крім недостатньої стандартизації ГСА володіють також і рядом інших недоліків, серед яких необхідно відзначити:

– складність тестування по всіх шляхах, без підрахунку і наступної перевірки кожного з яких неможливо верифікувати ГСА;

– складність «читання» і внесення змін у ГСА у випадку, якщо в операторних вершинах не вказуються значення всіх вихідних змінних;

– наявність внутрішніх змінних;

– використання тільки бітових внутрішніх змінних, що роблять ГСА досить громіздкими навіть для порівняно простих алгоритмів;

– реалізація функціональних елементів затримки в складі ГСА, що робить цю модель не автоматною, а часовою.