Основні поняття теорії алгоритмів - частина четверта - теорія алгоритмів

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

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

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

Формальне визначення алгоритму

Концепції алгоритмів в математичних термінах були вперше описані в 1930 - 1940 рр, коли велися пошуки умов, за допомогою яких можливо доказ проблеми розв'язання задач або, в загальному випадку, автоматичне доведення математичних теорем. Існують три основні типи алгоритмічних моделей. У першому поняття алгоритм зв'язується з обчислюваних числовими функціями. У другому алгоритм представляється як деякий універсальний пристрій, здатний виконувати набір найпростіших операцій (наприклад, машина Тьюринга). Третій тип грунтується на раніше визначених поняттях абстрактного алфавіту і відповідності між словами в такому алфавіті, що дозволяє формально описувати процеси перетворення інформації.

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

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

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

До числа інших властивостей алгоритму відносяться масовість і результативність.

Результативність алгоритму - властивість алгоритму, що забезпечує отримання результату через кінцеве число кроків. Іншими словами, якщо будь-якого з належать до області визначення слів алгоритм через кінцеве число кроків порівняє результуюче слово, то він має властивість результативності.

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

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