Тема 5.1 Алгоритм і його властивості. Способи запису алгоритму
Алгоритмом називається чіткий опис послідовності дій, які необхідно виконати для вирішення завдання. Будь-яке завдання вимагає отримання результату по заданими вихідними даними, тобто алгоритм описує послідовний процес перетворення вихідних даних в результат.
1) Дискретність. Це властивість полягає в тому, що алгоритм повинен представляти процес вирішення завдання як послідовне виконання простих (або раніше визначених) кроків. При цьому для виконання кожного етапу алгоритму потрібно певний кінцевий відрізок часу, тобто перетворення вихідних даних в результат здійснюється в часі дискретно.
2) Визначеність (або детермінованість). Це властивість полягає в тому, що кожне правило алгоритму має бути чітким, однозначним і не залишати місця для сваволі. Завдяки цій властивості виконання алгоритму носить механічний характер і не вимагає додаткових вказівок або відомостей про розв'язуваної задачі.
3) Результативність (або кінцівку). Це властивість полягає в тому, що алгоритм повинен призводити до вирішення завдання за кінцеве число кроків.
4) Масовість. Це властивість полягає в тому, що алгоритм вирішення задачі розбирається в загальному вигляді, тобто він повинен бути застосовний для деякого класу задач, що розрізняються лише вихідними даними. При цьому вихідні дані можуть вибиратися з деякою області, яка називається областю застосовності алгоритму (в окремих випадках вихідні дані можуть бути відсутніми).
Форми подання алгоритму
На практиці використовуються такі форми подання алгоритмів:
· Словесна - запис на природній мові,
· Графічна - запис у вигляді схеми (блок-схеми),
· Запис на спеціальній мові (алгоритмічній мові або псевдокоді).
Словесний спосіб являє собою опис послідовних етапів обробки даних. Алгоритм поставив у довільному викладі природною мовою.
Наприклад: записати алгоритм визначення найбільшого спільного дільника (НСД) двох натуральних чисел (алгоритм Евкліда). Алгоритм може бути наступним:
· Задати два числа;
· Якщо числа рівні, то взяти будь-який з них в якості відповіді і зупинитися, інакше продовжити виконання алгоритму;
· Визначити більше з чисел;
· Замінити більше з чисел різницею більшого і меншого з чисел;
· Повторити алгоритм з кроку 2.
Даний спосіб погано формалізуємо і практично застосовується рідко.
Графічний спосіб представлення алгоритмів є більш компактним і наочним порівняно зі словесним. При графічному поданні алгоритм зображується у вигляді послідовності пов'язаних між собою функціональних блоків, кожен з яких відповідає виконанню одного або декількох дій.
Таке графічне представлення називається схемою алгоритму або блок-схемою. У блок-схемі кожному типу дій (введення вихідних даних, обчислення значень виразів, перевірці умов, управління повторенням дій, закінчення обробки і т.п.) відповідає геометрична фігура, представлена у вигляді блочного символу. Блокові символи з'єднуються лініями переходів, визначають напрямок потоків даних.
Основні елементи блок-схеми алгоритму. Правила виконання схем і позначення для окремих операцій процесу обробки даних регламентує Державний стандарт (ГОСТ 19.701-90 «Єдина система програмної документації. Схеми алгоритмів, програм, даних і систем. Позначення умовні і правила виконання»).
Алгоритмічні мови близькі до природної мови, тому для них характерні: алфавіт, операції - слова, оператори - пропозиції, синтаксис - правила написання.
Правила побудови конструкцій в алгоритмічній мові більш «жорсткі». Це означає, що алгоритмічні мови допускають менше різноманітності для опису дій алгоритму, ніж природна мова і звична математична символіка, і машина однозначно розуміє будь-яку конструкцію мови. Наприклад, для множення двох змінних a і b загальноприйнята математична символіка допускає кілька можливих форм запису:
ab a × b a'b a * b.
Прикладом алгоритмічного мови є псевдокод, наведений в таблиці:
Загальний вигляд алгоритму:
алг назва алгоритму (аргументи і результати)
нач опис проміжних величин
| послідовність команд (тіло алгоритму)
Частина алгоритму від слова алг до слова поч називається заголовком, а частина, яка знаходиться між словами поч і кін - тілом алгоритму.
У реченні алг після назви алгоритму в круглих дужках вказуються характеристики (арг. Рез) і тип значення (цілий. Вещ. Сім. Лит або лог) всіх вхідних (аргументи) і вихідних (результати) змінних. При описі масивів (таблиць) використовується службове слово таб. доповнене граничними парами по кожному індексу елементів масиву.
Приклад запису на алгоритмічній мові: