Лекція 6 Операторні алгоритмічні системи Загальні зауваження

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

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

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

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

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

У той же час допущення формування команд алгоритму в процесі її реалізації приведе до істотного скорочення й спрощення запису алгоритму. У зв'язку із цим наступною вимогою, пред’явленою до поняття алгоритму, є допущення формування команд алгоритму в процесі його виконання.

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

Елементарні акти, аналогічні логічним операціям, у явному або неявному виді вводяться й при визначенні поняття виконання алгоритму в абстрактній теорії алгоритмів.

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

У машині Т'юрінга логічною операцією можна вважати рух стрічки вправо або вліво залежно від стану машини й прочитаного символу.

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

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

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