Операторні алгоритми а. А. Ляпунова

Алгоритмічна система радянського вченого А. А. Ляпунова, запропонована їм в 1953 р., є однієї з перших, враховуючі всі вимоги, висунуті до конкретних алгоритмів. Вона виникла у зв'язку з реалізацією алгоритмів різних задач на ЕОМ.

Для опису будови, алгоритмів Ляпунов використає спеціальний математичний апарат — так називані «логічні схеми алгоритмів», у яких заголовними логічними буквами позначаються окремі акти алгоритму, що переробляють інформацію. Їх називають операторами. Малими буквами позначаються логічні умови, що перевіряються, при цьому використовується символіка, прийнята в математичній логіці. Наприклад, символом р(х<у) позначають логічну умову, виконану в тому випадку, коли нерівність, що стоїть в дужках, істинно. У противному випадку ця умова хибна.

Послідовне виконання декількох операторів позначається як добуток, причому співмножник, що стоїть праворуч, діє після співмножника, що стоїть ліворуч.

Логічними схемами алгоритму називаються вирази, складені з операторів і логічних умов, що випливають одна за іншою. Від кожної логічної умови починається стрілка, що кінчається в якого-небудь із операторів. Наприклад, з операторів А, В, С и логічних умов р и q можна скласти наступні логічні схеми:

Знак ↑_i позначає початок стрілки, знак — її кінець. Однаковими номерами позначаються початок і кінець однієї й тієї ж стрілки. Стрілки можуть починатися й у будь-якого нелогічного оператора.

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

Для запису алгоритмів використаються наступні основні типи операторів: 1) арифметичні оператори; 2) оператори перевірки логічних умов; 3) оператори переадресації; 4) оператори переносу; 5) оператори формування.

1. Арифметичні оператори служать для запису різних арифметичних дій і позначаються початковими буквами латинського алфавіту.

Наприклад, оператор А обчислює величину а = a_jk — ca_ik , оператор В — величину с = а_ij: а_ii. Вибір букв для позначення операцій довільний.

2. Оператори перевірки логічних умов служать для визначення порядку роботи алгоритму й позначаються малими буквами латинського алфавіту р, q й ін.

3. Оператори переадресації служать для зміни адрес у наказах; для зміни різних параметрів, від яких залежать оператори програми; для відновлення значень параметрів й адрес, які були змінені в процесі роботи алгоритму (програми).

Оператори переадресації позначаються буквою F із вказівкою в дужках змінюваної адреси або параметра. Так, оператор, що змінює параметр i на одиницю, буде позначатися F(i). Оператор, що збільшує параметр i на п одиниць, буде позначатися Fⁿ(i). Оператор, що зменшує параметр i на п одиниць, буде позначатися F^-n(i).

4. Оператор переносу служить для «переносу» одного параметра на «місце» іншого, або, інакше кажучи, для заміни одного параметра іншим. Оператори переносу позначаються [а→b], де а означає, чим заміняється (що переноситься), b — що заміняється (замість чого переноситься).

5. Оператори формування служать для формування початкових значень деяких операторів алгоритму. Вони переносять деякі заздалегідь запасені накази в певні місця алгоритму.

Оператори формування можна використати замість операторів переадресації. Це особливо зручно, коли число переадресацій може бути різним, а початкове значення параметра — завжди те саме. Наприклад, якщо початкове значення параметра i дорівнює l, то оператор формування може бути записаний у вигляді {l→i}.

Розглянемо приклад запису операторного алгоритму Ляпунова для підсумовування п'яти чисел: а₁, а₂, а₃, a₄, а₅.

Нехай с — параметр, що представляє собою , оператор A_i

обчислює величину c_i = c_i-1+ а_i. Обчислення суми починаємо з i=1. Алгоритм має вигляд:

[1→i] {0→c_i-1}^↓1 Ai (i) р (i = 6) ^↑1 останов

Операторні алгоритми Ляпунова для рішення певної задачі допускають деякі еквівалентні перетворення. Програма, побудована по кожному з еквівалентних між собою алгоритмів, служить для рішення однієї й тієї ж задачі.

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

Перетворення схем можна розглядати із двох точок зору. Перший шлях - досліджувати формальні тотожні перетворення схем алгоритмів, пропонується радянським математиком Ю. И. Яновым і буде розглянутий далі.

Другий шлях - досліджувати змістовні перетворення схем алгоритмів, що враховують індивідуальні особливості розв'язуваної задачі.