1.2. Вимоги до алгоритмів

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

1. Кожен алгоритм має справу з даними – вхідними, проміжними, вихідними. Для того, щоб уточнити поняття даних, фіксується алфавіт вихідних символів (цифри, букви і т.п.) і вказуються правила побудови алгоритмічних об'єктів. Типовим використовуваним засобом є індуктивна побудова. Наприклад, визначення ідентифікатора в Паскалі, Сі: ідентифікатор – це або буква, або ідентифікатор, до якого приписана праворуч або буква, або цифра. Інший випадок алгоритмічних об'єктів – формули.

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

3. Алгоритм складається з окремих елементарних кроків, причому множина різних кроків, з яких складений алгоритм, скінченні. Типовий приклад множини елементарних кроків – система команд процесора.

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

5. Алгоритм повинен бути результативним, тобто зупинятися після скінченного числа кроків (залежного від вхідних даних) з видачею результату. Дана властивість іноді називають збіжністю алгоритму.

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

Вимога 1 відповідає цифровій природі ПК, вимога 2 – пам'ять ПК, вимога 3 – програмі машини, вимога 4 – її логічній природі, вимоги 5, 6 – обчислювальному пристрою та його можливостям.

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

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

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

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

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

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

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

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

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

Скінченність – кожна окрема дія, як і весь алгоритм повинні мати можливість реального виконання. Тому алгоритм має межу, тобто скінченність.

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

Придатність алгоритму до реалізації визначається об’ємом пам'яті i швидкодією комп’ютера. Обчислювальний алгоритм має ставити розумні вимоги до ресурсів комп’ютера.