Граф-схеми Калужніна

Граф-схеми Калу́жніна — це спосіб задання класів алгоритмів, що фіксують у своєму визначенні структурні властивості алгоритмів, абстрагуючись від семантичних властивостей, що визначають індивідуальність даного алгоритму. У 1959 році Л. А. Калужнін запропонував алгебру граф-схем як інструмент для математизації програмування. Його робота «Об алгоритмизации математических задач», 1959 року стала, яка стала класичною та відправною точкою для створення систем алгоритмічних алгебр. Граф-схеми алгоритмів, запропоновані Калужніним, заклали основу графічних дескриптологічних засобів, націлених на розробку й проектування інформаційних систем. Сьогодні цей апарат отримав друге дихання у зв'язку із процесами тотальної візуалізації програмування, він невпинно розповсюджується на всі етапи життєвого циклу систем.

Формальний опис граф-схеми

Під граф-схемою Γ розуміється математичний об'єкт, що описується наступним чином. Подано деякий скінченний набір об'єктів: U = {U1, U2 … Un}, що називаються операторами, і деякий другий скінченний набір елементів: Φ = {Φ1, Φ2 … Φn}, що називається розпізнавачами. Граф-схема Γ або U-Φ-граф-схема — це скінченний, зв'язний та направлений лінійний комплекс, тобто скінченне число точок (вузлів), деякі з яких з'єднані направленими відрізками (стрілками), і такий, що виходячи з якоїсь точки, можна досягти будь-яку іншу, слідуючи по відрізкам, що задовольняє певним умовам:

1. Один вузол комплексу відмічений та називається входом (Β); вхід — єдиний вузол, в якому не закінчується жодна стрілка; з входу виходить тільки одна стрілка.
2. Комплекс має один відмічений вузол, що називається виходом (Ḅ); з виходу не виходить жодна стрілка.
3. Кожному вузлу, що відрізняється від входу та виходу, однозначно відповідає або деякий оператор Ui — такий вузол називається U-вузлом, або розпізнавач — Φj, такий вузол називається Φ-вузлом. При цьому не вимагається, щоб кожний оператор Ui та кожний розпізнавач Φj співставлявся деякому вузлу; з іншого боку, деякі оператори або розпізнавачі можуть бути співставлені деяким різним вузлам. При цьому: а) якщо α — U-вузол, то з нього точно виходить одна стрілка;

б) якщо α — Φ-вузол, то з нього точно виходять дві стрілки, відмічені знаками плюс і мінус відповідно.

Теоретико-множинна інтерпретація

При заданих наборах U = {U1, U2 … Un} та Φ = {Φ1, Φ2 … Φn} кожній U-Φ-граф-схемі можна однозначним чином співставити «алгоритм» для обчислення деякої функції, якщо інтерпретувати оператори Ui як відображення деякої множини в себе, а розпізнавачі — як операції, що розпізнають деякі властивості елементів і що здійснюють застосування тих чи інших відображень до елементу, в залежності від того чи має той елемент дану властивість. Нехай U = {U1, U2 … Un} та Φ = {Φ1, Φ2 … Φn} — задані набори операторів та розпізнавачів. Під інтерпретацією наборів розуміється наступне: дано деяку множину М; кожному оператору Ui є U співставлено відображення Аі множини М в себе (співставлення не завжди є взаємнооднозначним; допускається, що різни операторам Ui можуть відповідати однакові відображення); кожному розпізнавачу Φj є Φ відповідає деяка властивість Fj елементів множини М. При цьому, під властивістю розуміється розбиття множини М на дві частини, що не пересікаються: одна з множин  або  може бути пустим. Співставлення розпізнавача Φj властивості Fj не обов'язково взаємнооднозначне.

Інтерпретація наборів U та Φ визначається заданням множини М і відповідностей  → ; Φj → Fj. Така інтерпретація позначається таким чином: {M; U → A; Φ → F}.

Нехай дано деяку інтерпретацію {M; U → A; Φ → F}, тоді деяку U-Φ-граф-схему можна розглядати як однозначне припис для виконання деякої дії, в результаті якої деякі елементи з М перейдуть в нові елементи з М. Ця дія виконується таким чином.

Нехай елемент  поступає на вхід схеми; після цього він пробігає схему, слідуючи за стрілками, і відозмінюючись всякий раз, коли він проходить через U-вузол. Цей пробіг проходить за наступними правилами: а) Нехай деякий елемент  вже перейшов в деякий елемент  та поступив, слідуючи стрілці, в деякий вузол, який співставлено оператору ; тоді по єдиній стрілці, що виходить з, продовжує свій шлях елемент.

б) Нехай деякий елемент  поступає в деякий вузол, відмічений розпізнавачем, тоді той самий елемент покидає вузол по стрілці, відміченій плюсом або мінусом, в залежності від того, має  чи ні властивість.

в) Якщо на деякому етапі видозмінений елемент  поступає на вихід, то вважається, що  результат застосування U-Φ-алгоритму, визначеного U-Φ-граф-схемою Γ при інтерпретації {M; U → A; Φ → F} і позначається записом.

При заданій інтерпретації граф-схема однозначним чином описує функцію, визначену в М, зі значенням в М.

При заданій інтерпретації можливо, що алгоритми, які описуються різними граф-схемами будуть при будь-яких можливих  приводити до однакового результату, тобто різні граф-схеми можуть здійснювати одну й ту саму функцію. Такі граф-схеми називаються еквівалентними.

Конструктивні, марковські інтерпретації граф-схем

U-Φ-алгоритми можна розглядати як «умовні»; вони виконувані тільки тому, що при заданій інтерпретації виконувані відображення, а властивості  дійсно можуть бути розпізнані. Для фактичного здійснення алгоритму інтерпретацію слід обирати таким чином, щоб елементарні операції  були настільки прості, що у можливості їх здійснення ніяких сумнівів не виникало. Більш того, якщо алгоритм призначений для виконання на деякому автоматичному пристрої, то логічно припустити, що елементарні операції можуть бути виконані на стандартних простих ячейках машини.

Нехай  {  } та  {  } — набори, що визначають граф-схему.  — властивість слів містити принаймні одне входження слова Х, а  — операція підстановки слова Y замість першого входження Х. Також можна писати [X] замість  і [X  Y] замість.

Інтерпретація {M; U → A; Φ → F} називається марківською, якщо:

1) М — множина всіх можливих слів в деякому алфавіті;

2) всі  всі суть властивості ;

3) всі  всі суть властивості ;

Всякий алгоритм, який описується граф-схемою при деякій марківській інтерпретації називають марківським алгоритмом.

Н.а. є частинним випадком марківських алгоритмів. А саме, нехай, наприклад: схема н.а. Тоді предпис Маркова щодо дій цього алгоритму рівносильний U-Φ-алгоритму, що здійснються згідно граф-схемі з інтерпретацією.

Легко бачити, що н.а. завжди буде відповідати граф-схемам подібного частинного вигляду. З іншого боку, всякий марківський алгоритм є еквівалентним до деякого алгоритму, що описується граф-схемою. Таким чином нормальні граф-схеми можна розглядати як деякі канонічні форми при марківських інтерпретаціях.

Література

1. Л. А. Калужнин «Об алгоритмизации математических задач».