Алгебри на операторах програм. Алгебраїчний підхід до аналізу програм.

Алгебра займається вивченням властивостей операцій. Алгебра – упорядкована пара <K, ∑>,  де К – множина, а ∑ - сигнатура операцій, які виконуються над К.

<K, ∑>=U_К

U_К замкнена відносно операції f, якщо при застосуванні f до елементів К результат цієї операції f() є К.

Якщо U_К є замкненою для всіх f є ∑, то U_К є універсальною. Алгебра може бути частково універсальною, якщо відносно одних операцій вона замкнена, а деяких – ні. Алгебра не універсальна, якщо вона є незамкненою відносно всіх операцій.

Алгебри на операторах програм: К – множина програм, ∑ - операції над операторами. Наприклад, if – визначений на операторах і на умовах. За допомогою алгебр потрібно проаналізувати результати операцій на яких побудована ця алгебра. Для того, щоб проаналізувати програму за допомогою алгебраїчного підходу, потрібно описати за допомогою алгебр всі оператори програми і проаналізувати програму з цих позицій.

Дослідження програмних комплексів за їх автоматами. Класи еквівалентних програм

А=<K, A, k₀, k_n, Г>

К – множина станів, k₀, k_n – початковий і заключний стани, Г – граф. Системі ставимо у відповідність автомат S↔А, тобто в ролі К виберемо множину елементів системи: К={S_i}, A={S_i}. В ролі дуг графа будуть виступати пари {S_i, S_j}.{S_i} – множина станів, потрібно вказати початковий і заключний стани. Для дослідження програмних комплексів потрібно скласти таблицю станів.

Таблиця станів:

 Таблиця зв’язків

Якщо є ці таблиці, тоді можна відтворити граф. Якщо є графи Г₁ і Г₂, то вони гомоморфні (ізоморфні), якщо існує φ:Г₁→Г₂, яке являється однозначним (взаємооднозначним) і при якому зберігається орієнтація дуг. Якщо графи ізоморфні, то вони однакові. Якщо між вершинами одного і того ж графа вдається встановити ізоморфне відображення, то його можна скоротити за рахунок того, що ці лінійні зв’язки можуть бути замінені однією дугою (замість сукупності двох), які будуть мати навантаження (для відображення лінійних дуг). Вважається, що вершина графа ізольована, якщо вона не має зв’язків з іншими вершинами, але може мати зв’язок сама з собою. При підрахунку рангу цей зв’язок враховується. Важливим в аналізі є: зв’язність, ізольованість, max ранг вершини. Два автомати А₁ і А₂ називаються еквівалентними, якщо між графами, що відповідають цим автоматам Г₁ і Г₂ існує гомоморфне відображення. А₁ і А₂ сильно еквівалентні, якщо графи Г₁ і Г₂ – ізоморфні з точністю до лінійних частин. Лінійна частина графу – його шляхи. Шлях – частина графу, в якій немає петель, розгалужень і циклів. Якщо автомати еквівалентні, то їх графи можна спростити. PK=UK_~, UK_~ - клас еквівалентності. Нехай маємо PK, що складається з 20 процедур. По признаку еквівалентності виділили тільки 7 класів еквівалентності, тобто в кожному класі еквівалентності кожну процедуру можна взяти за представника класу еквівалентності. Скільки класів – стільки і процедур.