Применение в теории алгоритмов

Логическое отношение алгоритмов может быть сформулировано на основе неформального описания (например, блок-схемы алгоритмов, граф-схемы). Блок-схемы используются для описания «предшествующих» алгоритмов («вычислить - х» алгоритмов). Описание состоит из последовательности шагов – операторов и инструкции. Предписывающие алгоритмы исполняются (интерпретируются) неймановской машиной и является программой: предикатный символ ® Q_i(t₁,... t_n).

В программе выбираются контрольные точки (узлы), которые ставят в соответствие предикаты, обозначающие состояние программы в i-том узле.

t_i – термы, обозначение состояния (значения) i-той переменной.

Порядок записи уравнения:

1) если i и j – это вход и выход операторной вершины (смотри рисунок S – оператор с инструкцией на выполнение преобразования). Переход из i в j – это дуга, которая определяется формулой: Qi(t₁t₂... t_n) ® Qj(l₁l₂...l_n)

где l_j = f(f₁... f_n)

2) если i и j – вход и выход условной вершины. Тогда дуге «i ® j» ставится в соответствие формула с контрольным предикатом:

Q_i & P ® Q_i, P = P(t₁... t_n)

3) начало программы Q₀ - Æ - местный предикат - высказывание

4) конец программы Q_k.

Пример: программа «умножение» х,у – целые

x – множимое; у – множитель

x значит «ввод х»; z ® «вывод z»

Контрольные формулы вводятся:

Q₃ (x,y,z) & (z > 0) ® Q₅ (x,y - 1,z + x) & (z > x)

Q₃ (x,y,z) & (z = 0) ® Q₅ (x,y - 1, x)

Пример задачи:

1 a "x"y Q₆ (x,y) & (y = 0)

- если эта формула выводится, то программа завершена.

2. Интерпретация формул для конкретных чисел данных обозначает исполнение алгоритма.

Интерпретация включает:

1) подстановка значений переменных после ввода данных.

2) интерпретация формул после подстановки значений переменных.

3) запуск итерационного процесса (Q₁=T) который выполняется с формулами пока F_i+1 не равно F_i.

Формулы можно упорядочить для ускорения итерации. Формулы можно интерпретировать параллельно – это логическое программирование – запись алгоритмов в виде формул и исполнение алгоритмов осуществляется машиной, интерпретирующей формулу.

3. Символическое тестирование – при неполностью определенных данных с целью тестирования алгоритма, в результате интерпретации при частично определенных данных будет получена формула, которая совпадает с исходным определением метода вычисления.

Задаемся множимым х = а; и множителем у = 3.

Интерпретация: подстановки

Q₀®Q₁(x = a, y = 3, z = Æ)®

®Q₂(a, 3, Æ)®Q₃(a, 3, Æ)®

®Q₅(a, y = 2, z = z + a)®

®Q₂(a, 3, a)®

®Q₅(a, y = 1, z = a + a)®

®Q₂(a, 1, a + a)®

®Q₅(a, y = Æ, z = a + a + a)

®Q₂(a, Æ, a + a + a)

®Q₄(a, Æ, a + a + a)

®Q_k(a, Æ) - конец программы.

Подтверждается:

4. Частичные вычисления при ограниченных условиях. При интерпретации сохраняется только те формулы, которые применимы при ограниченных данных. Программа адаптируется для конкретных условий работы.

5. В традиционном программирований в неймановской машине используется контрольные формулы, в которых проверяется свойства данных в конкретных точках программы. Практически во всех процедурных языках программирования используется оператор assert(формула), сохраняется признак (Æ и 1), по которым можно судить о наличии ошибки.