p> У результаті тривалих теоретичних і практичних досліджень були сформульовані основні вимоги до алгоритмів:
1. Кожен алгоритм має справу з даними - Вхідними, проміжними, вихідними. Для того щоб уточнити поняття даних, фіксується кінцевий алфавіт вихідних символів (цифри, букви і т.п.) і вказуються правила побудови алгоритмічних об'єктів. Типовим використовуваним засобом є індуктивне побудова. Наприклад, визначення ідентифікатора в багатьох алгоритмічних мовах: ідентифікатор - це або буква, або ідентифікатор, до якого приписана праворуч або буква, або цифра. Слова кінцевої довжини в кінцевих алфавітах - найбільш звичайний тип алгоритмічних даних, а число символів у слові - природна міра об'єму даних. Інший випадок алгоритмічних об'єктів - формули. Прикладом можуть служити формули алгебри предикатів і алгебри висловлювань. p> 2. Алгоритм для розміщення даних вимагає пам'яті. Пам'ять зазвичай вважається однорідною і дискретної, тобто вона складається з однакових осередків, причому кожна клітинка може містити один символ даних, що дозволяє узгодити одиниці виміру обсягу даних і пам'яті.
3. Алгоритм складається з окремих елементарних кроків, причому безліч різних кроків, з яких складений алгоритм, звичайно. Типовий приклад безлічі елементарних кроків - система команд ЕОМ.
4. Послідовність кроків алгоритму детермінована, тобто після кожного кроку вказується, який крок слід виконувати далі, або вказується, коли слід роботу алгоритму вважати закінченою.
5. Алгоритм повинен володіти результативністю, тобто зупинятися після кінцевого числа кроків (Залежного від вихідних даних) з видачею результату. Дана властивість іноді називають збіжністю алгоритму.
6. Алгоритм припускає наявність механізму реалізації, який за описом алгоритму породжує процес обчислення на основі вихідних даних. Передбачається, що опис алгоритму та механізм його реалізації кінцеві.
Можна помітити аналогію з обчислювальними машинами. Вимога 1 відповідає цифровий природі ЕОМ, вимога 2 - пам'яті ЕОМ, вимога 3 - програмі машини, вимога 4 - її логічною природою, вимоги 5, 6 - обчислювальному пристрою і його можливостям.
Є також деякі риси неформального поняття алгоритму, щодо яких не досягнуто остаточної угоди. Ці риси можна сформулювати у вигляді запитань та відповідей.
1. Чи слід фіксувати кінцеву кордон для розміру вхідних даних?
2. Чи слід фіксувати кінцеву кордон для числа елементарних кроків?
3. Чи слід фіксувати кінцеву кордон для розміру пам'яті?
4. Чи слід обмежити число кроків обчислення?
На всі ці питання далі приймається відповідь В«НІВ», хоча можливі й інші варіанти відповідей, оскільки у фізично існуючих ЕОМ відповідні розміри обмежені. Проте теорія, вивчає алгоритмічні обчислення, здійсненні в принципі, не повинна рахуватися з такого роду обмеженнями, оскільки вони переборні, по крайней мірі, в принципі (наприклад, будь-який фіксований розмір пам'яті завжди можна збільшити на одну клітинку).
Таким чином, уточнення поняття алгоритму пов'язано з уточненням алфавіту даних і форми їх подання, пам'яті і розміщення у ній даних, елементарних кроків алгоритму і механізму реалізації алгоритму. Однак ці поняття самі потребують уточнення. Ясно, що їхні словесні визначення зажадають введення нових понять, для яких, у свою чергу, знову будуть потрібні уточнення і т.д. Тому в теорії алгоритмів прийнятий інший підхід, заснований на конкретній алгоритмічної моделі, в якій всі сформульовані вимоги виконуються очевидним чином. При цьому використовувані алгоритмічні моделі універсальні, тобто моделюють будь-які інші розумні алгоритмічні моделі, що дозволяє зняти можливе заперечення проти такого підходу: чи не призводить жорстка фіксація алгоритмічної моделі до втрати спільності формалізації алгоритму? Тому дані алгоритмічні моделі ототожнюються з формальним поняттям алгоритму. p> Всякому алгоритмом відповідає завдання, для вирішення якої він був побудований. Протилежне твердження в загальному випадку є невірним з двох причин: по-перше, одна і та ж завдання може вирішуватися різними алгоритмами, по-друге, можна припустити (Поки), що є завдання, для яких алгоритм взагалі не може бути побудований. p> Як вже зазначалося, термін В«алгоритмВ» з'явився в математиці досить давно і використовувався довго - Під ним розумілася процедура, що дозволяла шляхом виконання послідовності певних елементарних кроків отримувати однозначний результат, не залежний від того, хто ці кроки виконував. Таким чином, саме проведене рішення служило доказом існування алгоритму. Однак був відомий цілий ряд математичних задач, вирішити які в загальному вигляді не вдавалося. Прикладами можуть послужити три древні геометричні задачі: про трисекции кута, про квадратурі кола і про подвоєння куба - жодна з них не має спільного способу вирішення за допомогою циркуля і лінійки без поділів.
І...
