3.1. Методичні вказівки до самостійного вивчення теми

Структурну схему понять, що визначають алгоритмічні системи, зображено на рис. 3.1

3.1.1. Визначення алгоритмічної системи

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

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

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

Доведено можливість та правомірність переходу з однієї алгоритмічної системи до іншої у процесі побудови та реалізації алгоритму розв’язання задачі (тобто виконання еквівалентних перетворень алгоритму).

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

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

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

3.1.2. Рекурсивні функції

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

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

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

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

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

1) функції, тотожньо рівні 0: f(x) = 0; для всіх х;

2) функції, тотожньо рівні аргументу: f(x) = x;

3) функції безпосереднього слідування: f(x) = x + 1.

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

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

Наприклад, нехай є

f(x) = 0;

g(x) = x + 1;

h(x) = g(f(x)).

Тоді:

h(0) = g(0) = 0 + 1 = 1;

h(x) = g(0) = 0 + 1 = 1.

Тобто отримали функцію, яка тотожньо дорівнює 1.

Якщо h(x) = g(g(x)), то h(x) = g(x + 1) = x + 1 + 1 = 2 і т.д.

Операція примітивної рекурсії дозволяє побудувати функцію, залежну від n + 1 аргумента, якщо відомі дві функції — одна від n аргументів, друга — від n + 2 аргументів.

Наприклад, побудуємо двомісну функцію додавання f(x, y) = x + y, якщо є одномісна g(x) = x; та тримісна h(x, y, z) = z +1. (Кількість аргументів можна збільшувати як завгодно.)

Завдяки операції примітивної рекурсії здійснимо побудову функції. Нехай

f(x, 0) = g(x);

f(x, y + 1) = h(x, y, f(x, y)); f(x, 0) = g(x) = x;

f(x, 1) = h(x, 0, f(x, 0)) = h(x, 0, x) = x + 1;

f(x, 2) = h(x, 1, f(x, 1)) = h(x, 1, x + 1) = x + 2;

. . .

f(x, y – 1) = h(x, y – 2, f(x, y – 2)) = h(x, y – 2, x + y – 2) = x + y – 1;

f(x, y) = h(x, y – 1, f(x, y – 1)) = h(x, y – 1, x + y – 1) = x + y.

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

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

Операція найменшого кореня, або операція мінімізації, дозволяє побудувати функцію f від n аргументів, якщо відома функція g, залежна від n + 1 аргумента, тобто зменшити кількість аргументів функції.

Нехай маємо функцію від n + 1 аргумента g(x₁, x₂ ... x_n, y).

Побудуємо функцію від n аргументів f(x₁, x₂ ... x_n).

Задамо значення для n аргументів функції g:

x₁ = a₁ ; x₂ = a₂ ... x_n = a_n.

Підставимо ці значення у формулу, що визначає функцію g, отримаємо: g(а₁, а₂ ... а_n, у).

Дорівняємо цей вираз до нуля і розв’яжемо рівняння відносно у:

g(a₁, a₂ ... a_n, y) = 0.

Нехай отримали y = a.

Вважатимемо це значення у за значення функції f від тих самих значень х₁ ... х_n :

f(a₁ ... a_n) = a.

Діючи так, ми можемо визначити функцію f від будь-яких значень її аргументів. Отже, функцію f побудовано.

Наприклад:

g(x, y, z) = x + y +z f(x, y) = ?

g(0, 0, z) = 0 + 0 + z = 0 z = 0 f(0, 0) = 0

g(1, 0, z) = 1 + 0 + z = 0 z = –1 f(1, 0) = –1

g(0, 1, z) = 0 + 1 + z = 0 z = –1 f(0, 1) = –1

. . .

g(5, 2, z) = 5 + 2 + z = 0 z = -7 f(5, 2) = –7

g(–6, 1, z) = –6 + 1 + z = 0 z = 5 f(–6, 1) = 5

f(x, y) = –x – y