Властивості та характеристики алгоритмів

Незважаючи на різноманіття алгоритмів, в них можна знайти багато спільного. Ці спільні риси називаються властивостями алгоритмів.

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

1) Скінченність.

Алгоритм має завершуватися за скінченну кількість кроків (скінченність процесу перетворення інформації).

2) Результативність (завершеність).

При коректно заданих вихідних даних виконання алгоритму завжди повинно приводити до певного результату.

3) Дискретність.

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

4) Визначеність (детермінованість або однозначність).

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

5) Формальність.

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

6) Масовість (універсальність).

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

7) Зрозумілість.

Алгоритм повинен складатися з команд, які входять до системи команд його виконавця. При цьому виконавцем алгоритму може бути людина, комп’ютер, робот тощо.

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

З поняттям алгоритму пов’язані такі поняття, як область його задання, складність, еквівалентність, алгоритмічна розв’язність та ін.

Область заданняалгоритму — це множина даних, до яких алгоритм застосовний. Якщо алгоритм завершується без отримання результату або продовжується необмежено довго, то говорять про незастосовність алгоритму до цих вхідних даних.

Під алгоритмічною розв’язністю розуміють можливість побудови алгоритму розв’язку всіх задач даного класу.

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