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

Виконавець алгоритму

Виконавець алгоритму — це деяка абстрактна або реальна (технічна, біологічна або біотехнічна) система, здатна виконати дії, що наказують алгоритмом.

Виконавця характеризують:

·середовище;

·елементарні дії;

·система команд;

·відмови.

Середовище — це "житло" виконавця. Наприклад, для виконавця Робот зі шкільного підручника середовище — це нескінченне клітинне поле. Стіни і закрашені клітки теж частина середовища. А їх розташування і положення самого Робота задають конкретний стан середовища.

Система команд. Кожен виконавець може виконувати команди тільки з деякого строго заданого списку — системи команд виконавця. Для кожної команди мають бути задані умови застосовності (у яких станах середовища може бути виконана команда) і описані результати виконання команди. Наприклад, команда Робота "вгору" може бути виконана, якщо вище за Робота немає стіни. Її результат — зсув Робота на одну клітку вгору.

Після виклику команди виконавець здійснює відповідну елементарну дію.

Відмови виконавця виникають, якщо команда викликається при неприпустимому для неї стані середовища.

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

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

2. Дискретність (переривчатість, нарізність) — алгоритм повинен представляти процес рішення задачі як послідовне виконання простих (або раніше визначених) кроків (етапів).

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

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

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