Операторні алгоритмічні системи

Загальні поняття

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

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

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

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

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

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

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

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

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

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

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

Операторні алгоритми Ван Хао

Операторний алгоритм Ван Хао задається послідовністю наказів спеціального вигляду. Кожен наказ має певний номер і містить вказівки: яку операцію слід виконати над заданим об'єктом і наказ з яким номером слід далі виконати над результатом даної операції. Загальний вигляд такого наказу (1):

$i:{\begin{array}{|c|c|c|}\hline \omega &\alpha &\beta \\\hline \end{array}}\,,$

де i — номер наказу; ω — елементарна операція над об'єктом; α, β — номери деяких наказів.

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

Виконати наказ (1) над числом х в операторному алгоритмі — значить знайти число ω(х) і далі перейти до виконання над ω(х) наказу з номером α.

Якщо ж ω(х) не визначено, то перейти до виконання над числом х наказу з номером β.

Наприклад, виконавши над числом 24 наказ

$i:{\begin{array}{|c|c|c|}\hline 6&7&13\\\hline \end{array}}\,,$

отримаємо число 4 і вказівку виконувати далі над 4 наказом з номером 7. Виконавши цей наказ над числом 23, отримаємо знову число 23 і вказівку виконувати над 23 наказ з номером 13.

Останнім станом машини Тюрінга в операторних алгоритмах відповідає наказ виду:

$i:{\begin{array}{|c|}\hline {\mbox{C}}\mathrm {T} {\mbox{O}}\Pi \\\hline \end{array}}\,,$

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

У загальному випадку результат виконання наказу (1) над числом х будемо зображати парою (z, γ), де z — отримане число, γ — номер наказу, який повинен виконуватися далі над z.

Програмою операторного алгоритму називається послідовність наказів виду:

$i:{\begin{array}{|c|c|c|}\hline \omega _{i}&\alpha _{i}&\beta _{i}\\\hline \end{array}}$
$...$
$i+s:{\begin{array}{|c|c|c|}\hline \omega _{i+s}&\alpha _{i+s}&\beta _{i+s}\\\hline \end{array}}$
$...$
$i+n:{\begin{array}{|c|}\hline {\mbox{C}}\mathrm {T} {\mbox{O}}\Pi \\\hline \end{array}}$

де ω(x),…, ω_i+s(x) — задані одномісні часткові функції, що визначають елементарні операції над об'єктом х; α_i, β_i,…, α_i+s, β_i+s… — якісь натуральні числа з послідовності i, i+1,…, i+n.

Переробити х згідно даного операторного алгоритму — це означає виконати над х послідовність наступних дій.

i — крок. Знаходимо ω_i(x). Якщо ω_i(x) визначено, то результатом буде пара чисел [ω_i(x), α_i]. Якщо ω(x) не визначено, то результатом i-го кроку буде пара (х, β_i).

i+1 — крок, якщо результат попереднього кроку х, β_i, де β_i= i+1. Знаходимо ω_i+1(x). Якщо вона визначена, то результатом буде пара [ω_i+1(x), α_i+1], якщо не визначена, то результатом буде пара (х, β_i+1) і т. д.

i+n-1 — крок. Якщо як результат на цьому кроці вийде пара, яка вказує на останній оператор (z, i+n), то процес обривається і число z є результатом переробки числа х згідно заданому алгоритму (z = ω_i+n-1(х)).

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

Якщо функція всюди визначена, то символ β не впливає на процес обчислень і тому зазвичай не вказується. У цьому випадку наказ має вигляд i: [ω,α]: Кажуть, що операторний алгоритм А з програмою (х) обчислює часткову функцію f(x), якщо алгоритм А переробляє кожне натуральне число х в f(x). Зокрема, якщо f(x) НЕ визначено, то процес переробки х згідно з програмою (2) повинен бути нескінченним.

Природа функцій, обчислюваних за допомогою операторних алгоритмів Ван Хао, залежить від того, які функції ω1 входять у записі наказів. Має місце наступна теорема, що визначає природу функцій ωi.

Теорема (3). Для того щоб часткова функція f(x) була обчислюваною за допомогою операторного алгоритму, програма якого містить лише частково рекурсивні функції ω_i(х) з рекурсивною областю визначеності, необхідно і достатньо, щоб f(х) була частково рекурсивною.

Необхідність умов очевидна, і ми обмежимося лише доказом їх достатності.

Насамперед, введемо поняття однієї важливої для доказу функції. Цю функцію будемо позначати через ех(х, у) або скорочено ех_ху і називати експонентою числа р_x в числі у. При у≠0 вважаємо ех_ху рівним показнику найвищого ступеня простого числа р_х, на яку ділиться у. Для у=0 вважаємо за визначенням ех_х0= 0 для всіх значень х.

Наприклад,

$ex_{3}8=3,ex_{1}8=0,ex_{0}0=0$.

Ясно, що алгоритм з програмою

$0:{\begin{array}{|c|}\hline {\mbox{C}}\mathrm {T} {\mbox{O}}\Pi \\\hline \end{array}};1:{\begin{array}{|c|c|c|}\hline +\alpha &1&\\\hline \end{array}}$

обчислює ніде не визначену функцію f(x).

Нехай частково рекурсивна функція f(x) має непорожній графік. Тоді цей графік можна представити у вигляді сукупності пар

<α(t),β(t)>, (t=0,1,…),

де α і β — відповідні примітивно рекурсивні функції. Позначимо через υ(x) вираз 2^х і введемо часткову функцію ω(x), вважаючи

$\omega (x)={\begin{cases}3^{x},ex_{0}x\neq \alpha (ex_{1}x)\\-,ex_{0}x=\alpha (ex_{1}x)\end{cases}}$

Функція ω(x) частково рекурсивних з рекурсивною областю визначеності. Легко переконатися, що операторний алгоритм, що має програму

$0:{\begin{array}{|c|}\hline {\mbox{C}}\mathrm {T} {\mbox{O}}\Pi \\\hline \end{array}};{\mbox{ }}1:{\begin{array}{|c|c|}\hline \upsilon &2\\\hline \end{array}};{\mbox{ }}2:{\begin{array}{|c|c|c|}\hline \omega &2&3\\\hline \end{array}};{\mbox{ }}3:{\begin{array}{|c|c|}\hline ex_{1}&4\\\hline \end{array}};{\mbox{ }}4:{\begin{array}{|c|c|}\hline \beta &0\\\hline \end{array}}$

обчислює якраз функцію f(x). Справді, виконавши над довільним числом х наказ 1, отримаємо пару (2^х, 2). Якщо x≠α(0), то, виконавши над 2^х наказ 2, отримаємо пару (2^x3¹, 2) . Якщо x≠α(1), то, виконавши над 2^x3¹ наказ 2, отримаємо пару (2^x3², 2) і т. д. Процес продовжується до тих пір, доки, нарешті, вийде пара (2^x3ⁿ, 2), для якої х=α(n). Так як ω(2^x3ⁿ) не визначено, то над числом 2^x3ⁿ тепер треба виконати наказ 3, в результаті якого отримаємо пару (n,4). Виконавши над n наказ 4, отримаємо пару (β(n),0). Так як х=α(n), то β(n)=f(х), і, отже, алгоритм переробляє х в f(x), що й було потрібно.

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

Теорема Мінського (4). Для кожної частково рекурсивної функцій f(х) існує операторний алгоритм, програма якого складається з наказів виду

${\begin{array}{|c|}\hline {\mbox{C}}\mathrm {T} {\mbox{O}}\Pi \\\hline \end{array}}{\mbox{ }}{\begin{array}{|c|c|c|}\hline \times c&a&\\\hline \end{array}}{\mbox{ }}{\begin{array}{|c|c|c|}\hline :d&\alpha &\beta \\\hline \end{array}}$

для будь-якого х, переробний 2^x в 2^f(x).

Іншими словами, будь-яка частково рекурсивна функція f(х) обчислювана за допомогою відповідного алгоритму, програма якого складається з наказів наведеного виду, за умови, що значення аргументу і функції кодуються числами 2, 2^f(x).

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

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

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

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

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

$\downarrow ^{2}{\mbox{ }}Ap^{1}{\mbox{ }}B\downarrow q^{1}\uparrow ^{2}{\mbox{ }}C$, або $p\uparrow ^{1}{\mbox{ }}A\downarrow ^{2}{\mbox{ }}B\downarrow ^{1}{\mbox{ }}Cq\uparrow ^{2}$

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

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

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

1. Арифметичні оператори служать для запису різних арифметичних дій і позначаються початковими буквами латинського алфавіту. Наприклад, оператор А обчислює величину а = а_jk-са_ik, оператор В — величину с = а_ij. Вибір букв для позначення операцій довільний.

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

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

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

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

5. Оператори формування служать для формування початкових значень деяких операторів алгоритму. Вони переносять деякі заздалегідь запасені накази в певні місця алгоритму. Оператори формування можна використовувати замість операторів переадресації. Це особливо зручно, коли число переадресацій може бути різним, а початкове значення параметра — завжди одне і те ж. Наприклад, якщо початкове значення параметра i=l, то оператор формування може бути записаний у вигляді {l → i}. Розглянемо приклад запису операторного алгоритму Ляпунова для підсумовування п'яти чисел: а₁ , a₂ , а₃ , a₄ , a₅.

Нехай с — параметр, що є сумою а_і, і=1,…n, оператор A_i обчислює величину с_і = c_і-1 + а_і. Обчислення суми починаємо з i=1. Алгоритм має вигляд: [1 → i] {0 → c_i-1}^↑' A_i F(i) p (i=6)^↑'

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

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

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

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

Джерела

• Алферова З. В. «Теория алгоритмов»