Тема 3. Алгоритмічні системи

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

Рис. 3.1. Склад алгоритмічних систем

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

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

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

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

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

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

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

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

3.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 і т.д.