3. Основні відомості з теорії алгоритмів
3.1. Поняття алгоритму
Обробка інформації на ЕОМ полягає у виконанні низки операцій відповідно до деякого алгоритму, що в результаті призводить до отримання результату або рішення. Поняття алго-ритму немає суворого математичного визначення та її сенс абстрагується з досвіду (як і, як сенс понять «множина», «число», «відповідність» та інших.). Тому всі відомі визначення алгоритму є тією чи іншою мірою неповними. Однак для зручності можна вважати, що алгоритм - це спосіб перетворення інформації, що задається за допомогою кінцевої системи правил. Таке визначення є досить загальним.
Аналіз елементарних операцій із обробці інформації, які у реальних алгоритмах, показує, що й можна розділити на дві групи: арифметичні і логічні. Арифметичні операції виконують безпосереднє перетворення інформації, а логічні визначають напрямок процесу обробки інформації. В алгоритмах арифметичні та логічні операції чергуються у певній послідовності. Якщо виконання алгоритму зводиться до арифметичних операцій, такий алгоритм називається чисельним.
Два алгоритми вважаються рівними, якщо для деякого перетворення інформації вони встановлюють однакову відповідність між вхідними та вихідними словами та збігаються системи правил, що задають ці алгоритми. Два алгоритми називаються еквівалентними, якщо вони встановлюють однакову відповідність між вхідними та вихідними словами, але відрізняються способами їхнього завдання.
3.2. Властивості алгоритмів
Алгоритми мають властивості визначеності, масовості та результативності. Властивість визначеності висловлює той факт, що сукупність операцій, що виконуються відповідно до деякого алгоритму, не допускаєніякого свавілля щодо їх послідовності та тлумачення, тобто є детермінованим процесом. Масовість алгоритму означає можливість рішення з його допомогою цілого класу завдань з вихідними даними, що змінюються. Результативність алгоритму полягає в тому, що шуканий результат може бути отриманий за допомогою алгоритму шляхом виконання кінцевого числа операцій при всіх допустимих значеннях вихідних даних. Розглянуті властивості алгоритму є емпіричними та їх вважатимуться визначенням поняття алгоритм.
Областью застосування алгоритму називається найбільша область вихідних даних, на якій алгоритм має властивість результативності. Якщо вихідні дані не входять в область застосування алгоритму, то він не забезпечує отримання результату за кінцеве число операцій.
3.3. Алгоритмічні системи: операторні описи та граф-схеми
Загальний стандартний спосіб завдання алгоритмів називається алгоритмічною системою. У теорії та проектуванні технічних засобів ВТ для цих цілей використовуються дві алгоритмічні системи: операторні описи (ГО) та граф-схеми алгоритмів (ДСА). У ГО літерами позначаються окремі дії алгоритмів з переробки інформації - операції та логічні умови, що перевіряються. Послідовне виконання кількох операцій позначається як їх твір, причому ліва операція виконується раніше за праву. У такому лінійному записі алгоритму операція відрізняється від логічної умови тим, що після останнього ставиться стрілка, спрямована вгору та забезпечена числовим індексом. Якщо логічна умоваАвиконана (тобтоА= 1), то здійснюється перехід до операції або логічної умови, що вказується стрілкою. Якщо ж умоваАне виконано (А= 0), то здійснюєтьсяперехід до операції або логічної умови, записаної безпосередньо за умовоюА.Наприклад, операторний опис
означає, що після виконання операційВ1,В2 таВ3 необхідно перевірити логічну умовуА1.ЯкщоА1 = 0, далі необхідно переходити до операційВ4,В5 і логічному умовіА2. Якщо жА1=1, слід відразу перейти до перевіркиА2. Залежно від значенняА2 можливі два варіанти продовження алгоритму: виконати операціюВ6 (приА2 = 0) абоВ3 і далі перевіритиА1 (приА2 = 1).