Учебное пособие: Алгоритмічні проблеми
Схемою операторного алгоритму (СОА), або схемою операторної процедури, називається об"єкт виду:
SA = (x1, x2., xn; S ; y), (6)
де x1., xn, y – змінні, S – СП вигляду (5).
Схемою предикатногоо алгоритму (СПА), або схемою предикатної процедури, називається об"єкт виду:
SP = (x1, x2., xn; S ; q [.t.], q [.f.]), (7)
де x1., xn, – змінні, S – СП вигляду (5), а q [.t.], q [.f.]) – кінцеві мітки СП S .
Зауважимо, що пам "яттю алгоритмів (6), (7) називається об" єднання пам"ятті S і змінних x1., xn, y, і x1., xn називаються вхідними змінними, а y – вихідною змінною.
Ми визначили СП, СОА і СОП як деякі формальні, синтаксичні конструкції. Яка ж семантика (сенс) цих конструкцій? Як із них отримати справжні алгоритми (програми)?
Семантика схем задається за допомогою інтерпретацій. Інтерпретація схеми алгоритму W задається парою (D, I), де D – множина довільної природи, а I – це певне відображення, яке: а) кожному символу змінної z із пам"яті W ставить у відповідність елемент I(z) із множини D; б) кожному символу константи b із сигнатури W ставить у відповідність елемент I(b) із D; в) кожному m-арному функціональному f(m) (предикатному P(m)) символу співставляє, відповідно, всюдиозначені функцію I (f(m)): Dm ->D, або предикат I (P(m)) ->.t..f.
2. Нижче в данному розділі будемо розглядати тількі підклас схем алгоритмів KS -1 , які містять тільки два функціональні унарні символи f, g, один константний символ b і один унарний предикатний символ p. Також обмежимо клас інтерпретацій, поклавши, що в цьому класі KI-1 D завжди співпадає з множиною натуральних чисел N (D= N), а відображення I задовольняє наступним вимогам:
1) I(b) = 0;
2) I (f(x)) = I(x) + 1;
I(x) – 1, коли x>0
3) I (g(x)) = I(x) -^ 1 = 0 , коли x= 0 (8)
t., коли I(x) = 0;
4) I (p(x)) = P0 (x)) = *
f., коли I(x) > 0.
5) I(xi) є N для всіх вхідних змінних СОА і СПА виду (6), (7), і I(y) = 0 для всіх інших змінних із пам'яті вищезгаданих схем алгоритмів.
Опишемо формально функціонування алгоритму A виду (6).
Нехай M(A) = z1, z2..zn..zm – пам'ять алгоріму A, де zi = xi при 1<= i <= n, і zm = y. Через Q(A) позначимо всі мітки A. Станом пам'яті A будемо називати послідовність (a1..am) натуральних чисел, тобто елемент Nm. Станом (конфігурацією) алгоритму A будемо називати елемент <q; a1., am> із D(A) = Q & Nm.
Стан <q; a1., am> називається: а) проміжковим, якщо q – мітка передачи управління; б) кінцевим (заключним), якщо q – кінцева мітка алгоритму A.
Визначемо функцію переходів F: D(A) –> D(A) алгоритму A.
1. Коли <q; a1., am> – кінцевий стан, то
F (<q; a1., am>) = <q; a1., am>.
2. Коли <q; a1., am> – проміжковий стан, то значення F залежить від виду команди qk Ф[k] (ik, jk) в (5).
Якщо Ф[k] має вигляд:
a) zr = zt + 1, то F (<q; a1., am>) = <q*; b1., bm>, де q* = ik, br = at + 1, а bu = au для всіх таких u, що u не рівне r;
b) zr = zt -^ 1, то F (<q; a1., am>) = <q*; b1., bm>, де q* = ik, br = at -^ 1, а bu = au для всіх таких u, що u не рівне r;
c) zr = 0, то F (<q; a1., am>) = <q*; b1., bm>, де q* = ik, br = 0, а bu = au для всіх таких u, що u не рівне r;