Основні вимоги до алгоритмів

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

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

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

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

3. Алгоритм складається з окремих елементарних кроків (або дій), причому множина різних кроків, з яких складений алгоритм, скінченна. Типовий приклад множини елементарних дій - система команд процесора. Зазвичай елементарний крок має справу з фіксо­ваною кількістю символів, проте є команди, які працюють з полями пам'яті змінної довжини.

4. Послідовність кроків алгоритму детермінована; тобто після кожного кроку або вказується, який крок робити далі, або викону­ється команда зупинки, після цього робота алгоритму вважається закінченою.

5. Природно від алгоритму вимагати результативності, тобто зупинки після скінченної кількості кроків (яка залежить від почат­кових даних) з зазначенням того, що вважати результатом. Зокрема, алгоритм для обчислення функції f (x) повинен зупинятись післяскінченної кількості кроків для будь-якого х з області задання функ­ції f. У такому разі кажуть, що алгоритм збігається. Проте переві­рити результативність (збіжність) значно важче, ніж вимоги, викла­дені у пп. 1-4. На відміну від них збіжність здебільшого не вдається виявити простим прогляданням опису алгоритму Загального ж методу перевірки збіжності, придатного для довільного алгоритму А і довільних початкових даних а, взагалі не існує (див. параграф 10.4).

Потрібно розрізняти: а) опис алгоритму (інструкцію або програ­му); б) механізм реалізації алгоритму (наприклад, персональний комп'ютер), який передбачає засоби пуску, зупинки, реалізації елементарних кроків, видачі результатів і забезпечення детерміно­ваності, тобто керування перебігом обчислення; в) процес реалі­зації алгоритму, тобто послідовність кроків, яка буде породжена у разі застосування алгоритму до конкретних даних. Уважатимемо, що опис алгоритму й механізм його реалізації скінченні (пам'ять, як вже зазначалось, може бути нескінченною, але вона не входить у механізм). Вимога до скінченності процесу реалізації збігається з вимогою результативності (див. п. 5).

Отже, сформульовано основні вимоги до алгоритмів. Прості понят­тя, які використано в цих формулюваннях, самі є інтуїтивними. Тому в теорії алгоритмів використовують інший підхід: вибирають скінченний набір основних об'єктів, які називають елементарними, і скінченний набір способів побудови з них нових об'єктів. Уточненням поняття " дані" вважають множини слів у скінченних алфавітах. Для уточнення детермінізму використовують опис механізму реалізації алгоритму. Крім того, потрібно зафіксувати набір елементарних кроків і домовитись про організацію пам'яті. Після того, як це буде зроблено, одержують конкретну алгоритмічну модель.

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

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

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

Перший тип пов'язує поняття алгоритму з найтрадиційнішими поняттями математики - обчисленнями та числовими функціями (числовою називають функцію, значеннями якої та значеннями її аргументів є невід'ємні цілі числа). Найпопулярніша модель цього типу - рекурсивні функції — є історично першою формалізацією поняття алгоритму.

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

Нарешті, третій тип алгоритмічних моделей - це перетворення слів у довільних алфавітах. У цих моделях елементарними опе­раціями є підстановки, тобто заміни частини слова (підслова) іншим словом. Приклади моделей цього типу - канонічні системи Поста і нормальні алгорифми Маркова.

Ми розглянемо алгоритмічні моделі двох перших типів, і почнемо з машин Тьюрінга.