Алгоритм

Алгоритм – правила виконання в установленому порядку певної системи дій, що дають змогу розв'язувати сукупність відповідних задач. Поняття алгоритму – одне з основних понять математики й інформатики, з'явилося в XI ст. і пов'язане з ім'ям узбецького вченого Аль-Хорезмі, який сформулював правила арифметичних дій з числами. Ці правила називали алгоритмом.

Формулюється алгоритм для конкретного виконавця, наприклад, для людини, автомата тощо. Це зрозумілий і точний припис виконавцю здійснити послідовність дій, спрямованих на досягнення певної мети або розв'язання задачі алгоритму – не просто скінченне число правил, що встановлюють послідовність виконання операцій при розв'язуванні певної специфічної задачі, він характеризується такими особливостями:

• Скінченність. Алгоритм завжди повинен закінчуватися після скінченного числа кроків.
• Визначеність. Кожен крок алгоритму повинен бути точно визначений. Дії, які необхідно виконати, мають бути строго й однозначно визначені в кожному можливому випадку й не допускати довільного трактування виконавцем. Визначеність алгоритму дає змогу доручати його виконання автомату, що не володіє «здоровим глуздом».
• Введення алгоритму має деяке (можливо, рівне нулеві) число вхідних даних, тобто величин, заданих йому до початку роботи. Ці дані беруться з деякої конкретної множини об'єктів.
• Виведення алгоритму має одну або декілька вихідних величин (результатів), які цілком визначені щодо початкових даних.
• Ефективність. Алгоритм повинен бути ефективним. Усі операції, які необхідно виконати в алгоритмі, мають бути достатньо простими, щоб їх можна було виконати точно і за скінченний проміжок часу. Названі особливості пояснюють інтуїтивне поняття алгоритму.

На практиці довгий час користувалися й задовольнялися саме цим поняттям. З появою алгоритмічне нерозв'язних задач, тобто задач, для розв'язку яких не існує алгоритму, виникла необхідність його уточнення. Але не можна було довести неможливість алгоритмічного розв'язання задачі, поки не було строго визначено поняття алгоритму. Тому виникла потреба в побудові формального означення алгоритму, яке б відповідало інтуїтивному алгоритму. Одна з причин розпливчастості інтуїтивного поняття алгоритму полягає в тому, що об'єкти алгоритму можуть мати довільну природу. Отже, побудову формального означення було почато з формалізації поняття об'єкта алгоритму. В обчислювальних алгоритмах об'єктами дії є числа, в алгоритмі виробничих процесів – дані приладів, в алгоритмі інформаційних систем – логічні та рядкові дані тощо. Але в усіх цих випадках можна вважати, що алгоритм має справу не з самими реальними об'єктами, а з їхніми зображеннями, тобто реальні об'єкти можна зображати словами в різних алфавітах. Отже, можна вважати, що об'єктами дії алгоритму можуть бути тільки слова, і алгоритм – це чітка скінченна система правил для перетворення слів з деякого алфавіту на слова певного алфавіту. Відтак слід формалізувати дії над словами (об'єктами) і порядок цих дій. Одну з перших таких формалізацій запропонував англійський математик А Тьюрінг у 1936. Він описав схему деякої абстрактної машини (машини Тьюрінга) як «виконавця» алгоритму і називав алгоритмом те, що можна виконувати на такій машині. Те, що не може бути реалізовано на машині Тьюрінга, не є алгоритмом. Майже в той самий час була запропонована інша алгоритмічна схема – машина Є. Поста. В 1954 А. Марков розробив алгоритмічну схему, яку назвав нормальним алгоритмом і сформулював тезу про те, що всякий алгоритм нормалізується. Доведено, що алгоритмічні схеми А. Маркова, Є. Поста й А. Тьюрінга еквівалентні в тому значенні, що всі алгоритми, які описуються однією з цих схем, можуть бути описані й іншою. З теорії алгоритмів відомі задачі, для яких доведено, що для їх розв'язку не існує алгоритмів. Такі задачі називають алгоритмічно нерозв'язними.

Джерело:

Економічна енциклопедія: У трьох томах. Т. 1. / Редкол.: …С. В. Мочерний (відп. ред.) та ін. – К.: Видавничий центр “Академія”, 2000. – 864 с.