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

 

Визначення алгоритму

 

Інтуїтивне визначення алгоритму не дозволяє розглядати властивості алгоритмів як властивості формальних об’єктів. Тому математичне визначення алгоритму необхідно з наступних причин:

1) тільки за наявності формального визначення алгоритму можна зробити висновок про розв’язання або нерозв’язання проблеми;

2) воно дає можливість порівнювати алгоритми, призначені для розв’язання одинакових задач;

3) воно дає можливість порівнювати різні проблеми за складністю алгоритмів їх вирішення.

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

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

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

Слово, до якого застосовується алгоритм, називається вхідним. Слово, що утворюється в результаті застосування алгоритму, називається вихідним.

Сукупність слів, до яких застосовується даний алгоритм, називається областю застосовуваності цього алгоритму.

Формальні визначення алгоритму з’явилися в 30 – 40–х роках XX століття. Можна виділити три основні типи універсальних алгоритмічних моделей, що розрізняються вихідними евристичними міркуваннями стосовно того, що таке алгоритм.

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

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

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

 

Властивості МТ як алгоритму

 

На прикладі МТ добре прослідковуються властивості алгоритмів:

1 Дискретність. МТ може перейти до (k + 1) – кроку тільки після виконання k – го кроку, так як саме k – й крок визначає, яким буде (k + 1) – й крок.

2 Детермінованість. У кожній клітині таблиці машини Тьюринга записаний лише один варіант дії. На кожному кроці результат визначається однозначно, отже, послідовність кроків розв’язання задачі визначається однозначно, тобто якщо МТ на вхід подають одне й те саме слово, то вихідне слово кожен раз буде одним і тим самим.

3 Результативність. Змістовно результати кожного кроку і всієї послідовності кроків визначаються однозначно, отже, машина Тьюринга, яка правильно розроблена, за кінцевого числа кроків перейде в стан q_k, тобто за кінцевого числа кроків буде отримано відповідь на питання, поставлене в задачі.

4 Масовість. Кожна машина Тьюринга визначена над усіма допустимими словами з алфавіту, в цьому і полягає властивість масовості. Кожна МТ призначена для розв’язання одного класу задач, тобто для кожної задачі розробляється своя (нова) машина Тьюринга.

5 Зрозумілість. На кожному кроці в клітину записується символ з алфавіту, автомат виконує один рух (вліво – Л, Left, вправо – П, Right, є нерухомим – Н, Stop), і МТ переходить в один з описаних станів [3].